记录编号	411301	评测结果	AAAAAAAAAA
题目名称	[NOI 2015]寿司晚宴	最终得分	100
用户昵称	Imone NOI2018Au	是否通过	通过
代码语言	C++	运行时间	1.252 s
提交时间	2017-06-04 19:53:40	内存使用	2.76 MiB

#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAXN 505
#define ll long long

const int prime[] = {2, 3, 5, 7, 11, 13, 17, 19};

int NumSet[MAXN][MAXN], NumN[MAXN], N;
ll dp[2][1<<8][1<<8], F[1<<8][1<<8], MOD;

int main() {
	freopen("dinner.in", "rt", stdin);
	freopen("dinner.out", "wt", stdout);
	
	scanf("%d%lld", &N, &MOD);
	
	int i, x, k, set, SA, SB, bigfac;
	for(i=2;i<=N;i++) { //for number i
		x = i; set = 0;
		for(k=0;k<8;k++) if(!(x % prime[k])) {
			set |= 1 << k;
			while(!(x % prime[k])) x /= prime[k];
		}
		bigfac = x;
		//!!!
		//Num[bigfac][NumN[bigfac]] = i;
		NumSet[bigfac][NumN[bigfac]] = set;
		NumN[bigfac]++;
	}
	
	F[0][0] = 1;
	//special i == 1
	for(k=0;k<NumN[1];k++) {
		//put to None :: orig, keep
		set = NumSet[1][k];
		for(SA=255;SA>=0;SA--) {
			for(SB=255;SB>=0;SB--) {
				if(!(SB & set)) F[SA | set][SB] = (F[SA | set][SB] + F[SA][SB]) % MOD;
				if(!(SA & set)) F[SA][SB | set] = (F[SA][SB | set] + F[SA][SB]) % MOD;
			}
		}
	}

	//other
	for(i=2;i<=N;i++) if(NumN[i]) {
		memcpy(dp[0], F, sizeof(F));
		memcpy(dp[1], F, sizeof(F));

		for(k=0;k<NumN[i];k++) {
			//put to None :: orig, keep
			set = NumSet[i][k];
			
			//put to SA
			for(SA=255;SA>=0;SA--) {
				for(SB=255;SB>=0;SB--) {
					if(!(SB & set)) dp[0][SA | set][SB] = (dp[0][SA | set][SB] + dp[0][SA][SB]) % MOD;
					if(!(SA & set)) dp[1][SA][SB | set] = (dp[1][SA][SB | set] + dp[1][SA][SB]) % MOD;
				}
			}
		}
	
		//calc F
		for(SA=255;SA>=0;SA--) {
			for(SB=255;SB>=0;SB--) if(!(SA & SB)) F[SA][SB] = ((dp[0][SA][SB] + dp[1][SA][SB] - F[SA][SB]) % MOD + MOD) % MOD;
		}
	}
	
	ll Ans = 0;
	for(SA=0;SA<=255;SA++) {
		for(SB=0;SB<=255;SB++) if(!(SA & SB)) Ans = (Ans + F[SA][SB]) % MOD;
	}
	printf("%lld", Ans);
}