记录编号	246407	评测结果	AAAAAAAAAA
题目名称	[NOI 2015]寿司晚宴	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	2.007 s
提交时间	2016-04-06 09:12:29	内存使用	1.13 MiB

#include <fstream>
#include <algorithm>
#include <cstring>
#define N 550
#define M 310
using namespace std;
ifstream in("dinner.in");
ofstream out("dinner.out");
int n,mod;
int prime[8]={2,3,5,7,11,13,17,19};
pair<int, int > S[N];
int f[M][M]={0};
int g[2][M][M]={0};
void read()
{
	in>>n>>mod;
}
void preinit()
{
	int i,j,temp;
	for(i=1;i<=n;i++)
	{
		temp=i;
		for(j=0;j<8;j++)
		{
			if(temp%prime[j]==0)
			{
				S[i].second|=(1<<j);
				while(temp%prime[j]==0)temp/=prime[j];
			}
		}
		S[i].first=temp;
	}
	sort(S+1,S+n+1);
	//for(i=1;i<=n;i++)out<<i<<' '<<S[i].first<<' '<<S[i].second<<endl;
	f[0][0]=1;
}
void work()
{
	int i,j,k;
	for(i=2;i<=n;i++)
	{
		if(i==2||S[i].first==1||S[i].first!=S[i-1].first)
		{
			memcpy(g[0],f,sizeof(f));
			memcpy(g[1],f,sizeof(f));
		}
		for(j=255;j>=0;j--)
		{
			for(k=255;k>=0;k--)
			{
				if((S[i].second&k)==0)(g[0][j|S[i].second][k]+=g[0][j][k])%=mod;
				if((S[i].second&j)==0)(g[1][j][k|S[i].second]+=g[1][j][k])%=mod;
				
			}
		}
		if(i==n||S[i].first==1||S[i].first!=S[i+1].first)
		{
			for(j=255;j>=0;j--)
			{
				for(k=255;k>=0;k--)
				{
					f[j][k]=((g[0][j][k]+g[1][j][k]-f[j][k])%mod+mod)%mod;
				}
			}
		}
	}
	int ans=0;
	for(j=256;j>=0;j--)
	{
		for(k=256;k>=0;k--)
		{
			if((j&k)==0)
			{
				ans+=f[j][k];
				ans%=mod;
			}
		}
	}
	out<<ans<<endl;
}
int main()
{
	read();
	preinit();
	work();
	return 0;
}