Description

为了庆祝 NOI 的成功开幕,主办方为大家准备了一场寿司晚宴。小 G 和小 W 作为参加 NOI 的选手,也被邀请参加了寿司晚宴。

在晚宴上,主办方为大家提供了 $n−1$ 种不同的寿司,编号 $1,2,3,…,n−1$,其中第 $i$ 种寿司的美味度为 $i+1$ (即寿司的美味度为从 $2$ 到 $n$)。

现在小 G 和小 W 希望每人选一些寿司种类来品尝,他们规定一种品尝方案为不和谐的当且仅当:小 G 品尝的寿司种类中存在一种美味度为 $x$ 的寿司,小 W 品尝的寿司中存在一种美味度为 $y$ 的寿司,而 $x$ 与 $y$ 不互质。

现在小 G 和小 W 希望统计一共有多少种和谐的品尝寿司的方案(对给定的正整数 $p$ 取模)。注意一个人可以不吃任何寿司。

Input

输入文件的第 1 行包含 2 个正整数 $n,p$,中间用单个空格隔开,表示共有 n 种寿司,最终和谐的方案数要对 $p $取模。

Output

输出一行包含 1 个整数,表示所求的方案模 $p$ 的结果。

Solution

考虑状压DP,我们只将$\sqrt{n}$以内的质因子的情况压入状态,对所有数按其大于$\sqrt{n}$的因数分组,若没有大于$\sqrt{n}$的因数则单独分组。对于小于$\sqrt{n}$的因子实际上有3种状态,即某一个人选或者都不选,但这样不是很方便,简单起见我们用$f[i][j]$表示第一个人取的状态为 $i$ ,第二个人取的状态为 $j$ 的方案数。然后一开始就去掉无效状态加以优化(其实不优化也行).    然后对于每一组数,显然某个人只要选了其中的一个,另外一个人就一个也不能选,于是我们每次将f复制到 $dp[][]$,转移也就不难推了。处理完一组后再令$f[u][v] = dp[u][v] + dp[v][u] - f[i][j]$,表示某一个人选或不选这一组数,由于这两种情况都包含了两人都不选的情况,所以还需要减掉重复.    由于小于$\sqrt{n}$的质数最多只有8个,所以复杂度为$O(n * 3^8)$。

Source

#include <cstdio>
#include <cstring>
#include <algorithm>

#define For(i,j,k) for(int i = j;i <= k;i++)
#define Forr(i,j,k) for(int i = j;i >= k;i--)

const int N = 256;
const int Prime[] = {1, 2, 3, 5, 7, 11, 13, 17, 19};

using namespace std;

struct Num{
	int fac, s;

	bool operator < (const Num& A) const{
		return fac < A.fac;
	}

}A[N<<1];

typedef long long LL;

LL f[N][N], dp[N][N], Mod;
int n, Begin[N], Next[N * N], to[N * N], e;

int main(){
	scanf("%d%lld", &n, &Mod);
	For(i,1,n-1){
		int t = i + 1;
		For(j,1,8) while(t % Prime[j] == 0) 
			t /= Prime[j], A[i].s |= 1 << (j - 1);
		A[i].fac = t;
	}
	For(u,0,255) 
		For(v,0,255) 
			if(!(u & v)){
				Next[++e] = Begin[u];
				Begin[u] = e;
				to[e] = v;
			}
	sort(A + 1, A + n);
	f[0][0] = dp[0][0] = 1;
	int l = 1;
	while(l < n){
		int r = l;
		while(A[r+1].fac == A[l].fac && A[l].fac != 1) ++r;
		For(i,l,r)
			Forr(u,255,0) for(int j = Begin[u];j;j = Next[j]){
				int v = to[j];
				if(!(A[i].s & u)) dp[u][v|A[i].s] = 
					(dp[u][v|A[i].s] + dp[u][v]) % Mod;
			}
		For(u,0,255) 
			for(int j = Begin[u];j;j = Next[j]){
				int v = to[j];
				f[u][v] = 
					(dp[u][v] + dp[v][u] - f[u][v] + Mod) % Mod;
			}
		For(u,0,255)
			for(int j = Begin[u];j;j = Next[j]) 
				dp[u][to[j]] = f[u][to[j]];
		l = r + 1;
	}
	LL Ans = 0;
	For(u,0,255) For(v,0,255) Ans = (Ans + f[u][v]) % Mod;
	printf("%lld\n", Ans);
	return 0;
}