记录编号	276706	评测结果	AAAAAAAAAA
题目名称	[NOI 2015]寿司晚宴	最终得分	100
用户昵称	粘粘自喜	是否通过	通过
代码语言	C++	运行时间	0.960 s
提交时间	2016-07-04 11:33:21	内存使用	1.70 MiB

    #include<iostream>  
    #include<cstdio>  
    #include<cstring>  
    #include<algorithm>  
    using namespace std;  
    int f[301][301],p[3][301][301],pp,ans;  
    int prime[8]={2,3,5,7,11,13,17,19},n;  
    struct use{  
        int kind,se;  
    }s[600];  
    bool cmp(use a,use b)  
    {  
        if (a.kind!=b.kind) return a.kind<b.kind;  
        else return a.se<b.se;  
    }  
    int main()  
    {  
        freopen("dinner.in","r",stdin);  
        freopen("dinner.out","w",stdout);  
        scanf("%d%d",&n,&pp);  
        for (int i=1;i<=n;i++)  
          {  
            int temp;  
            temp=i;  
            for (int j=0;j<8;j++)  
             if (temp%prime[j]==0)  
               {  
                 s[i].se|=1<<j;  
                 while (temp%prime[j]==0) temp/=prime[j];  
               }  
             s[i].kind=temp;    
          }  
        sort(s+2,s+n+1,cmp);  
        f[0][0]=1;  
        for (int i=2;i<=n;i++)  
         {  
            if (s[i].kind==1||s[i].kind!=s[i-1].kind)  
              {  
                 memcpy(p[1],f,sizeof f );  
                 memcpy(p[2],f,sizeof f );  
             }  
             for (int j=255;j>=0;j--)  
               for (int k=255;k>=0;k--)  
                 {  
                    if ((k&s[i].se)==0) p[1][j|s[i].se][k]=(p[1][j|s[i].se][k]+p[1][j][k])%pp;  
                    if ((j&s[i].se)==0) p[2][j][k|s[i].se]=(p[2][j][k|s[i].se]+p[2][j][k])%pp;  
                 }  
           if (s[i].kind==1||s[i].kind!=s[i+1].kind)  
             { 
                for (int j=0;j<=255;j++)  
                  for (int k=0;k<=255;k++)  
                    f[j][k]=((p[1][j][k]+p[2][j][k]-f[j][k])%pp+pp)%pp;  
             }  
         }  
         ans=0;  
         for (int i=0;i<=255;i++)  
           for (int j=0;j<=255;j++)  
             if ((i&j)==0) ans=(ans+f[i][j])%pp;  
        cout<<ans<<endl;  

    }