记录编号	274759	评测结果	AAAAAAAAAA
题目名称	[NOI 2015]寿司晚宴	最终得分	100
用户昵称	小一米	是否通过	通过
代码语言	C++	运行时间	0.426 s
提交时间	2016-06-29 17:28:25	内存使用	1.07 MiB

#include<cstdio>
#include<iostream>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
int n,mo,ans;
int f[256][256],g[256][256],h[256][256],p[9]={0,2,3,5,7,11,13,17,19};
struct node{
	int k,fac;
}a[502];
bool cmp(node a,node b){return a.k<b.k;}
void cal(node &x,int num)
{
	for (int i=1;i<=8;i++)
		if (num%p[i]==0)
		{
			x.fac|=1<<i-1;
			while (num%p[i]==0) num/=p[i];
		}
	x.k=num;
}
main()
{
		freopen("dinner.in","r",stdin);
	freopen("dinner.out","w",stdout);
	scanf("%d%d",&n,&mo);
	for (int i=2;i<=n;i++)
		cal(a[i],i);
	sort(a+2,a+n+1,cmp);
	f[0][0]=1;
	for (int v=2;v<=n;v++)
	{
		if (a[v].k!=a[v-1].k||a[v].k==1)
			for (int i=255;i>=0;i--)
				for (int j=255;j>=0;j--)
				if (!(i&j)) g[i][j]=h[i][j]=f[i][j];
		for (int i=255;i>=0;i--)
			for (int j=255;j>=0;j--)
			if (!(i&j))
			{
					if (!(a[v].fac&j)) g[i|a[v].fac][j]=(g[i][j]+g[i|a[v].fac][j])%mo;
					if (!(a[v].fac&i)) h[i][j|a[v].fac]=(h[i][j]+h[i][j|a[v].fac])%mo;
			}
		if (a[v].k!=a[v+1].k||a[v].k==1)
			for (int i=255;i>=0;i--)
				for (int j=255;j>=0;j--)
					if (!(i&j)) f[i][j]=((g[i][j]+h[i][j])%mo-f[i][j])%mo;
	}
	for (int i=255;i>=0;i--)
		for (int j=255;j>=0;j--)
			if (!(i&j))
				ans=(ans+f[i][j])%mo;
	printf("%d",(ans%mo+mo)%mo); 
}