记录编号	309318	评测结果	AAAAAAAAAA
题目名称	[NOI 2015]寿司晚宴	最终得分	100
用户昵称	甘罗	是否通过	通过
代码语言	C++	运行时间	1.849 s
提交时间	2016-09-19 13:56:21	内存使用	1.06 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 510
using namespace std;

int n,i,j,P=0,t;
long long ans;
int p[10]={2,3,5,7,11,13,17,19,0,0};
int f[300][300];   //f[i][j]表示A拿了i的质因数，B拿了j的质因数的方案数
int g[2][300][300];
struct Marvolo{
	int x,y;   //x表示该数的质因数的二进制，1表示有，0表示无
}a[N];   //y表示大于19的质因数包含情况

inline bool cmp(const Marvolo a,const Marvolo b){return (a.y!=b.y)?a.y<b.y:a.x<b.x;}
inline void DP(){
	int i=0,j=0,k=0,all=1<<8;
	sort(a+2,a+n+1,cmp);	f[0][0]=1;
	for (i=2;i<=n;i++){
		if (i==2||a[i].y==1||a[i].y!=a[i-1].y){
			memcpy(g[0],f,sizeof(f));	memcpy(g[1],f,sizeof(f));}
			for (j=all-1;j>=0;j--)
				for (k=all-1;k>=0;k--){
				if (!(j&a[i].x)) g[1][j][k|a[i].x]=(g[1][j][k|a[i].x]+g[1][j][k])%P;
                if (!(k&a[i].x)) g[0][j|a[i].x][k]=(g[0][j|a[i].x][k]+g[0][j][k])%P;
			}
		if (i==n||a[i].y==1||a[i].y!=a[i+1].y)	{
			for (j=0;j<all;j++)
				for (k=0;k<all;k++)
					f[j][k]=((g[0][j][k]+g[1][j][k]-f[j][k])%P+P)%P;
		}
	}
	for (i=0;i<all;i++)
		for (j=0;j<all;j++)
			if (!(i&j))	ans=(ans+f[i][j])%P;
	return;
}

int main(){
	freopen("dinner.in","r",stdin);
	freopen("dinner.out","w",stdout);	
	scanf("%d%d",&n,&P);
	for (i=2;i<=n;i++){
		t=i;
		for (j=0;j<=7;j++)
		if (!(t%p[j]))	{
			a[i].x|=1<<j;	for (;!(t%p[j]);t/=p[j]);
		}
		a[i].y=t;
	}
	DP();	printf("%lld\n",ans);
	return 0;
}