「LOJ 2131」「NOI2015」寿司晚宴

发表于

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

在晚宴上，主办方为大家提供了 n−1n-1 种不同的寿司，编号 1,2,3,⋯,n−11,2,3,\cdots ,n-1 ，其中第 ii 种寿司的美味度为 i+1i+1 （即寿司的美味度为从 22 到 nn ）。

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

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

Constraints

2≤n≤5002\leq n \leq 500 ， 0<p≤10000000000 < p \leq 1000000000

Solution

可以观察到选择一种寿司等价于选择它所有的质因子，又因为 nn 以内的数最多只有一个大于 n\sqrt{n} 的质因子，小于 n\sqrt{n} 的质因子有 88 个，所以我们可以把每个数包含的质因子压成一个 282^8 的状态，单独记录那个大于 n\sqrt{n} 的质因子。

然后进行状压 dp ，大于 n\sqrt{n} 的质因子相同的部分要放在一起处理，且只能由其中一个人选择。

令 f[i][j]f[i][j] 表示小 G 已选择的质因子集合为 jj ，小 W 已选择的质因子集合为 kk 的方案数；令 g[0/1][j][k]g[0/1][j][k] 表示当前块由小 G / 小 W 选择且小 G 已选择的质因子集合为 jj ，小 W 已选择的质因子集合为 kk 的方案数，可以得到转移方程：

g[0][j∣ai][k]=(g[0][j∣ai][k]+g[0][j][k])modpg[0][j|a_i][k]=(g[0][j|a_i][k]+g[0][j][k]) \bmod p

g[1][j][k∣ai]=(g[1][j][k∣ai]+g[1][j][k])modpg[1][j][k|a_i]=(g[1][j][k|a_i]+g[1][j][k]) \bmod p

在一个块开始时初始化 g[0/1][j][k]=f[j][k]g[0/1][j][k]=f[j][k] 。

在一个块结束时减去被多算的两个人都不选的方案并更新 ff ：

f[j][k]=(g[0][j][k]+g[1][j][k]−f[j][k])modpf[j][k]=(g[0][j][k]+g[1][j][k]-f[j][k]) \bmod p

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
using namespace std;
const int N=505;
const int pri[8]={2,3,5,7,11,13,17,19};
int n,mod,t,ans,mx=1<<8;
int f[N][N],g[2][N][N];
struct node{int p,mx;}a[N];
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
bool cmp(node a,node b){return a.mx==b.mx?a.p<b.p:a.mx<b.mx;}
void Mod(int& a,int b){a+=b;if(a>=mod)a-=mod;}
int main()
{
	n=read();mod=read();
	for(int i=2;i<=n;i++)
	{
		t=i;
		for(int j=0;j<8;j++)
		{
			if(t%pri[j])continue;
			a[i].p|=(1<<j);
			while(t%pri[j]==0)t/=pri[j];
		}
		a[i].mx=t;
	}
	sort(a+2,a+n+1,cmp);
	f[0][0]=1;
	for(int i=2;i<=n;i++)
	{
		if(i==2||a[i].mx==1||a[i].mx!=a[i-1].mx)
			memcpy(g[0],f,sizeof(f)),memcpy(g[1],f,sizeof(f));
		for(int j=mx-1;j>=0;j--)
			for(int k=mx-1;k>=0;k--)
			{
				if(!(j&a[i].p))Mod(g[1][j][k|a[i].p],g[1][j][k]);
				if(!(k&a[i].p))Mod(g[0][j|a[i].p][k],g[0][j][k]);
			}
		if(i==n||a[i].mx==1||a[i].mx!=a[i+1].mx)
			for(int j=0;j<mx;j++)
				for(int k=0;k<mx;k++)
					f[j][k]=((g[0][j][k]+g[1][j][k]-f[j][k])%mod+mod)%mod;
	}
	for(int i=0;i<mx;i++)
		for(int j=0;j<mx;j++)
			if(!(i&j))Mod(ans,f[i][j]);
	printf("%d",ans);
	return 0;
}