p2150 [NOI2015]寿司晚宴-白红宇

p2150 [NOI2015]寿司晚宴

阅读量：7040 次

发布时间：2019-06-28

本文共 1361 字，大约阅读时间需要 4 分钟。

分析

我们发现对于大于$\sqrt(n)$的数每个数最多只会包含一个

所以我们把每个数按照大质数的大小从小到大排序

我们知道对于一种大质数只能被同一个人取

所以f1表示被A取，f2表示被B取

最终答案就是这两个的答案减去啥都不去的答案

因为啥都不去会被重复记录两次

对于小质数则直接状压转移即可

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   using namespace std;#define int long longconst int p1[] = { 0,2,3,5,7,11,13,17,19};const int cnt1 = 8;int dp[500][500],n,mod,f1[500][500],f2[500][500];struct node { int msk,ano;};node d[1100];inline void init(int x){ int res=x+1; for(int i=1;i<=cnt1;i++){ if(res==1)break; if(res%p1[i]==0)d[x].msk|=(1<<(i-1)); while(res%p1[i]==0)res/=p1[i]; } d[x].ano=res;}inline bool cmp(const node x,const node y){ return x.ano
                   
                    =0;j--) for(k=(1<<8)-1;k>=0;k--)if(!(j&k)){ int msk1=j|d[i].msk,msk2=k|d[i].msk; if(!(msk1&k))f1[msk1][k]=(f1[msk1][k]+f1[j][k])%mod; if(!(msk2&j))f2[j][msk2]=(f2[j][msk2]+f2[j][k])%mod; } if(d[i].ano==1||d[i].ano!=d[i+1].ano||i==n){ for(j=(1<<8)-1;j>=0;j--) for(k=(1<<8)-1;k>=0;k--)if(!(j&k)){ dp[j][k]=(-dp[j][k]+mod)%mod; dp[j][k]=(dp[j][k]+f1[j][k])%mod; dp[j][k]=(dp[j][k]+f2[j][k])%mod; } } } int Ans=0; for(j=0;j<(1<<8);j++) for(k=0;k<(1<<8);k++) if(!(j&k))Ans=(Ans+dp[j][k])%mod; cout<