為了慶祝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取模）。注意一個人可以不吃任何壽司。

Solution

題意：有1-n-1這些數，把他們分給兩個人（可以不分），使得從兩個人各自任意拿出一個數，它們都是互質的。

注意到n是500，范圍內小質數較少，可以考慮狀壓小質數。

但是大質數怎么處理?

我們可以設計狀態為dp[i][j]表示做到了第i個大質數，當前小質數的選擇情況為j時的方案數。

因為每個大質數只能給一個人，所以我們dp的階段就是每個大質數。

最后統計答案時要注意，我們把都沒選的情況考慮了兩次，把多余的部分減去就可以了。

Code

#include<iostream> #include<cstdio> #include<algorithm> #define N 509 #define R register using namespace std; int prime[N],mdiv[N],n,k,size,ma; long long g[2][1<<9][1<<9],f[1<<9][1<<9],mod,ans; struct aaa {int a,b; }ji[N]; bool cmp(aaa a,aaa b) {return a.b<b.b; } int main() {scanf("%d%lld",&n,&mod);for(R int i=2;i<=n;++i){if(!mdiv[i])mdiv[i]=i,prime[++prime[0]]=i;for(R int j=1;j<=prime[0]&&((k=prime[j]*i)<=n);++j){mdiv[k]=prime[j];if(i%prime[j]==0)break;}}size=min(prime[0],9);for(R int i=2;i<=n;++i){int tmp=i;for(R int j=1;j<=size;++j)if(!(tmp%prime[j])){while(!(tmp%prime[j]))tmp/=prime[j];ji[i].a|=(1<<j-1);}ji[i].b=tmp;}sort(ji+2,ji+n+1,cmp);ma=(1<<size)-1;f[0][0]=1; for(R int i=2;i<=n;++i){if((ji[i].b==1)||(ji[i].b!=ji[i-1].b)){for(R int j=0;j<=ma;++j)for(R int k=0;k<=ma;++k)g[0][j][k]=g[1][j][k]=f[j][k];}for(R int j=ma;j>=0;--j)for(R int k=ma;k>=0;--k)if(!(j&k)){if(!(ji[i].a&j))(g[0][j][k|ji[i].a]+=g[0][j][k])%=mod;if(!(ji[i].a&k))(g[1][j|ji[i].a][k]+=g[1][j][k])%=mod;}if((ji[i].b==1)||(ji[i].b!=ji[i+1].b))for(R int j=0;j<=ma;++j)for(R int k=0;k<=ma;++k)if(!(j&k))f[j][k]=(g[0][j][k]+g[1][j][k]-f[j][k]+mod)%mod;}for(R int i=0;i<=ma;++i)for(R int j=0;j<=ma;++j)if(!(i&j))(ans+=f[i][j])%=mod;cout<<ans;return 0; }

?

轉載于:https://www.cnblogs.com/ZH-comld/p/9698442.html

新人創作打卡挑戰賽發博客就能抽獎！定制產品紅包拿不停！

總結

以上是生活随笔為你收集整理的[NOI2015]寿司晚宴（状压dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。