记录编号	407081	评测结果	AAAAAAAAAA
题目名称	[NOI 2015]寿司晚宴	最终得分	100
用户昵称	泪寒之雪	是否通过	通过
代码语言	C++	运行时间	1.588 s
提交时间	2017-05-20 11:56:06	内存使用	1.07 MiB

#include<bits/stdc++.h>
using namespace std;
int g[10]={0,2,3,5,7,11,13,17,19};
int  b,n,q,f[256][256],i,aaa,j,k,p[2][256][256];
long long ans;
char c;
struct Node{
	int ppp,ansss; 
}aa[503],top;
inline Node getaans(int x){
	aaa=0;
	for (j=8;j>=1;j--)
	 {
	 	aaa<<=1;
	 	if (x%g[j]==0) aaa++;
		while (x%g[j]==0) x=x/g[j];	 	
	 }
	 top.ansss=x;
	 top.ppp=aaa;
	 return top;
}
inline void read (int &x){
	b=1;c=getchar();
	for (;!('0'<=c && c<='9');c=getchar()) if (c=='-') b=-1;
	for (x=0;('0'<=c && c<='9');) {
		x=x*10+c-'0';
	    c=getchar();
	} 
	x=x*b;
}
inline void read (long long &x){
	b=1;c=getchar();
	for (;!('0'<=c && c<='9');c=getchar()) if (c=='-') b=-1;
	for (x=0;('0'<=c && c<='9');) {
		x=x*10+c-'0';
	    c=getchar();
	} 
	x=x*b;
}
inline int cmp(Node a ,Node b){
	return a.ansss<b.ansss;
}
int main () {
   freopen("dinner.in","r",stdin);
   freopen("dinner.out","w",stdout);
   read(n); read(q);
   for (i=2;i<=n;i++)
     aa[i]=getaans(i);
    sort(aa+2,aa+n+1,cmp);
    f[0][0]=1; p[0][0][0]=1; p[1][0][0]=1;
   for 	(i=2;i<=n;i++)
    {
      if (aa[i].ansss==1||aa[i].ansss!=aa[i-1].ansss)
       {
         	memcpy(p[0],f,sizeof f);
         	memcpy(p[1],f,sizeof f);
	   }
    	for (j=255;j>=0;j--)
    	 for (k=255;k>=0;k--)
         {
    	  	if (!((j | aa[i].ppp) & k)) p[0][j | aa[i].ppp][k]+=p[0][j][k]; p[0][j | aa[i].ppp][k]%=q;
    	 	if (!(j & (k | aa[i].ppp))) p[1][j][k | aa[i].ppp]+=p[1][j][k]; p[1][j][k | aa[i].ppp]%=q;	
		  }
	  if (i==n||aa[i].ansss==1||aa[i].ansss!=aa[i+1].ansss)  
         {  
            for (j=0;j<=255;j++)  
              for (k=0;k<=255;k++)  
                f[j][k]=((p[1][j][k]+p[0][j][k]-f[j][k])%q+q)%q;  
         }  	
	}
   ans=0;
   for (j=0;j<=255;j++)
    	 for (k=0;k<=255;k++)
    	   if ((k & j)==0) ans+=f[j][k];
    ans=ans%q;
    printf("%lld",ans);
}