p2150 [NOI2015]寿司晚宴

传送门

分析

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

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

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

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

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

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

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

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
#define int long long
const 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<y.ano;}
signed main(){
    int i,j,k,p,q;
    scanf("%lld%lld",&n,&mod);
    n--;
    for(i=1;i<=n;i++)init(i);
    sort(d+1,d+n+1,cmp);
    dp[0][0]=1;
    for(i=1;i<=n;i++){
      if(d[i].ano==1||d[i].ano!=d[i-1].ano){
          memcpy(f1,dp,sizeof(f1));
          memcpy(f2,dp,sizeof(f2));
      }
      for(j=(1<<8)-1;j>=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<<Ans;
    return 0;
}