[2019.1.6]BZOJ4197 [Noi2015]寿司晚宴

古城微笑少年丶 2021-12-23 22:37 162阅读 0赞

首先如果\\(n\\le22\\)那么大家都会了。

因为22以内只有8个质数,所以我们可以状压一个8位二进制数表示一个数的质因子集合。

那么要求就是两人吃的寿司的质因子集合交集为空集。

怎么状压应该都会了吧。

那么\\(n\\le500\\)呢?

发现\\(\\lfloor\\sqrt\{500\}\\rfloor=22\\),也就是500以内的数至多有1个大于22的质因子。

那么我们可以将这个质因子相同的数排在一起,每次使最多一个人选择大质因子相同的数,其他相同就好了。

那么我们在每段大质因子相同的数中记录\\(dp1\\)表示这个质因子给第一个人,\\(dp2\\)表示给第二个人。

段外记录\\(dp\\)表示这段结束时的种类数。

注意这里需要滚存,而且如果开两个数组滚存会很麻烦(别问我我怎么知道的),建议用一个数组滚。

每次进入一个新的段,使\\(dp1=dp2=dp\\)。

每次离开一个段,使\\(dp\_\{i,j\}=dp1\_\{i,j\}+dp2\_\{i,j\}-dp\_\{i,j\}\\),因为上一段的\\(dp\_\{i,j\}\\)被记录了两次。

具体转移见代码。

code:

#include<bits/stdc++.h> using namespace std; const int sqt=22; int n,p[510],sz,dmx[510],st[510],upd[510]; long long P,dp[(1<<8)+11][(1<<8)+11],dp1[(1<<8)+11][(1<<8)+11],dp2[(1<<8)+11][(1<<8)+11],ans; bool cmp(int x,int y){ return dmx[x]<dmx[y]; } int main(){ for(int i=2;i<=500;i++){ if(!p[i])p[++sz]=i; dmx[i]=sz; for(int j=sz;j>8&&i%p[j];j--,dmx[i]=j);if(dmx[i]<9)dmx[i]=0; for(int j=1;j<=sz&&j<=8;j++)st[i]|=(i%p[j]==0)<<j-1; for(int j=1;j<=sz&&i*p[j]<=500;j++){ p[i*p[j]]=1; if(i%p[j]==0)break; } } scanf("%d%lld",&n,&P); for(int i=1;i<n;i++)upd[i]=i+1; sort(upd+1,upd+n,cmp); dp[0][0]=1; for(int i=1;i<n;i++){ if(!dmx[upd[i]]||dmx[upd[i]]!=dmx[upd[i-1]])memcpy(dp1,dp,sizeof(dp1)),memcpy(dp2,dp,sizeof(dp2)); for(int j=(1<<8)-1;j>=0;j--)for(int k=(1<<8)-1;k>=0;k--){ if((j&k)||(dp1[j][k]|dp2[j][k])==0)continue; if((st[upd[i]]&k)==0)dp1[st[upd[i]]|j][k]=(dp1[st[upd[i]]|j][k]+dp1[j][k])%P; if((st[upd[i]]&j)==0)dp2[j][st[upd[i]]|k]=(dp2[j][st[upd[i]]|k]+dp2[j][k])%P; } if(!dmx[upd[i]]||dmx[upd[i]]!=dmx[upd[i+1]]||i==n-1)for(int j=0;j<(1<<8);j++)for(int k=0;k<(1<<8);k++)dp[j][k]=(dp1[j][k]+dp2[j][k]-dp[j][k]+P+P)%P; } for(int i=0;i<(1<<8);i++)for(int j=0;j<(1<<8);j++)ans=(ans+dp[i][j])%P; printf("%lld",ans); return 0; }

转载于:https://www.cnblogs.com/xryjr233/p/BZOJ4197.html