记录编号	254269	评测结果	AAAAAAAAAA
题目名称	[NOI 2015]寿司晚宴	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	3.347 s
提交时间	2016-04-24 17:45:41	内存使用	2.31 MiB

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;

const int pr[8]={2,3,5,7,11,13,17,19};
const int tr[8]={1,2,4,8,16,32,64,128};
int n,i,j,k,prime[100],cnt;
int p,dp[510][510],f[2][510][510];
long long ans;
//dp[i][j]表示两人分别选i,j时的可行状态数
//f[0][i][j]表示当前0选该kind的数，i，j时的状态数 
struct number{
	int kind,se;
}num[510];
bool cmp(const number x,const number y){
	return (x.kind!=y.kind?x.kind<y.kind:x.se<y.se);
}

void prework(){
	bool hash[510]={false};
	for (i=2;i<=500;i++)
	if (!hash[i]){
		prime[++cnt]=i;
		for (j=i+i;j<=500;j+=i) hash[j]=true;
	}
}

int main()
{
	freopen("dinner.in","r",stdin);
	freopen("dinner.out","w",stdout);
	prework();
	cin>>n>>p;
	for (i=1;i<=n;i++){
		for (j=0;j<8;j++)
		if (i%pr[j]==0) num[i].se|=tr[j];
		num[i].kind=1;
		if (i>=23)
		for (j=9;j<=cnt;j++)
		if (i%prime[j]==0){
			num[i].kind=prime[j];break;
		}
	}
	
	sort(num+1,num+n+1,cmp);
	dp[0][0]=1;
	
	for (i=2;i<=n;i++){
		if (i==2||num[i].kind==1||num[i].kind!=num[i-1].kind){
			memcpy(f[0],dp,sizeof(dp));
			memcpy(f[1],dp,sizeof(dp));
		}
		for (j=255;j>=0;j--)
			for (k=255;k>=0;k--){
				if ((k&num[i].se)==0)
					f[0][j|num[i].se][k]=(f[0][j|num[i].se][k]+f[0][j][k])%p;
				if ((j&num[i].se)==0)
					f[1][j][k|num[i].se]=(f[1][j][k|num[i].se]+f[1][j][k])%p;
			}
		if (i==n||num[i].kind==1||num[i].kind!=num[i+1].kind){
			for (j=0;j<256;j++)
			for (k=0;k<256;k++)
				dp[j][k]=((f[0][j][k]+f[1][j][k]-dp[j][k])%p+p)%p;
		}
	}
	
	for (i=0;i<256;i++)
		for (j=0;j<256;j++)
			if ((i&j)==0)
			ans=(ans+dp[i][j])%p;
	cout<<ans<<endl;
	return 0;
}