[Noi2015]寿司晚宴

爱被打了一巴掌 2023-06-01 14:59 8阅读 0赞

# \[Noi2015\]寿司晚宴 #

## 题目描述 ##

为了庆祝NOI的成功开幕，主办方为大家准备了一场寿司晚宴。小G和小W作为参加NOI的选手，也被邀请参加了寿司晚宴。

在晚宴上，主办方为大家提供了n−1种不同的寿司，编号1,2,3,⋯,n-1，其中第种寿司的美味度为i+1（即寿司的美味度为从2到n）。

现在小G和小W希望每人选一些寿司种类来品尝，他们规定一种品尝方案为不和谐的当且仅当：小G品尝的寿司种类中存在一种美味度为x的寿司，小W品尝的寿司中存在一种美味度为y的寿司，而x与y不互质。

现在小G和小W希望统计一共有多少种和谐的品尝寿司的方案（对给定的正整数p取模）。注意一个人可以不吃任何寿司

## 思路 ##

比较显然的结论是：**当一个人选择一个数时，就相当于选择了它的质因数集。若用两个二进制数s1,s2表示两个人现在已经拥有哪些质因数时，一定满足s1 or s2 == 0**.

有了这个结论，\\(n<=30\\)的情况已经可以解决了.状压\\(dp\\)即可。

随后，可以知道，若\\(n<=500\\)，那么每个数最多只有一个大于等于\\(\\sqrt\{n\}\\)的质因数，那么，只需要额外考虑含有这些“大质因数”的数即可。显然，这些质因数不能同时出现在两个人手中。那么，我们将\\(dp\\)转移稍微修改一下。

我们把所有大质因数相同的数放一起算。  
\\\[ f\[0\]\[bit\],表示当前把数给小G（或不拿）的方案数 \\\]

\\\[ f\[1\]\[bit\],表示当前把数给小W（或不拿）的方案数 \\\]  
转移和之前一样，只不过\\(f\[0\]\\)只转移给\\(f\[0\]\\),\\(f\[1\]\\)只转移给\\(f\[1\]\\).每当一个大质因数算完后，再去重（不拿的情况会被算到两次）。

若没有大质因数，则每算一次都去重即可。

#include<bits/stdc++.h> #define FOR(i,l,r) for(int i=(l),i##R=(r);i<=i##R;i++) #define DOR(i,r,l) for(int i=(r),i##L=(l);i>=i##L;i--) #define loop(i,n) for(int i=0,i##R=(n);i<i##R;i++) #define mms(a,x) memset(a,x,sizeof a) using namespace std; typedef long long ll; template<typename A,typename B>inline void chkmax(A &x,const B y){if(x<y)x=y;} template<typename A,typename B>inline void chkmin(A &x,const B y){if(x>y)x=y;} const int N=505; bool mm1; int n;ll P,ans; void Add(ll &x,ll y){ x+=y; if(x>=P)x-=P; } void Mul(ll &x,ll y){ x=x*y%P; } int pri[N],ct; bool check(int x){ for(int i=2;i*i<=x;i++) if(x%i==0)return false; return true; } ll f[3][1<<10][1<<10]; //f[2]为合并后总方案 struct node{ int st,p; bool operator<(const node &A)const{ return p<A.p; } }A[N]; void solve(){ for(int i=2;i*i<=500;i++)if(check(i))pri[ct++]=i; f[2][0][0]=1; FOR(i,2,n){ int st=0,k=i; loop(j,ct)if(k%pri[j]==0){ st|=(1<<j); while(k%pri[j]==0)k/=pri[j];//预处理大质因数(1则为没有) } A[i]=(node){st,k}; } sort(A+2,A+n+1);//使大质因数相同的和一起算 FOR(i,2,n){ if(i==2||A[i].p!=A[i-1].p||A[i].p==1){//若开始计算新的大质因数，则将f[1]和f[0]设为当前答案 DOR(j,(1<<ct)-1,0)DOR(k,(1<<ct)-1,0) f[0][j][k]=f[1][j][k]=f[2][j][k]; } DOR(j,(1<<ct)-1,0)DOR(k,(1<<ct)-1,0){ if(j&k)continue; if((j&A[i].st)==0)Add(f[0][j][k|A[i].st],f[0][j][k]); if((k&A[i].st)==0)Add(f[1][j|A[i].st][k],f[1][j][k]); } if(i==n||A[i].p==1||A[i].p!=A[i+1].p){ DOR(j,(1<<ct)-1,0)DOR(k,(1<<ct)-1,0){ if(j&k)continue; f[2][j][k]=f[0][j][k]+f[1][j][k]-f[2][j][k]; f[2][j][k]=(f[2][j][k]%P+P)%P; } } } DOR(j,(1<<ct)-1,0)DOR(k,(1<<ct)-1,0) Add(ans,f[2][j][k]); printf("%lld\n",ans); } int main(){ scanf("%d%lld",&n,&P); solve(); return 0; }

转载于:https://www.cnblogs.com/Heinz/p/11466154.html