算法

【题解】寿司晚宴

最优解！

upd 2021.6.18: 修改公式符号，更加形式化，添加 $50$ 分做法

upd 2022.7.30: 修改转移方程的笔误，修改公式符号

介绍一种 $O(n \times 3^8)$ 的做法，目前是所有非打表代码中的最优解，其实只是把其他题解中的算法优化了一下。

定义

  • $fac_i$ 表示 $i$ 的质因数集合
  • $P=\{x\mid x\ \text{is prime},\ x\le n\}$

暴力 1

这题的暴力有很多种，在此只介绍可以优化成正解的暴力。

两个数互质，等效于他们没有共同的质因子，所以只需把每个数都分解质质因数，如下 dp：

  • 状态：$dp(s_1,s_2)$ 表示考虑前 $i$ 个数（$i$ 被滚动掉了），小 G 选的数的包含的质因数集合为 $s_1$，小 W 的质因数集合为 $s_2$ 的情况数。
  • 转移：
$$ \begin{aligned} dp(s_1\cup fac_i,s_2)\leftarrow dp(s_1,s_2)+dp(s_1\cup fac_i,s_2)&\ &(fac_i\cap s_2=\varnothing)\cr dp(s_1,s_2\cup fac_i)\leftarrow dp(s_1,s_2)+dp(s_1,s_2\cup fac_i)&&(fac_i\cap s_1=\varnothing) \end{aligned} $$
  • 答案：
$$ \sum _{s_1,s_2 \subset P}{dp(s_1,s_2)\ (s_1\cap s_2=0))} $$

复杂度 $O(n\times2^{20})$，能得 $30$ 分。

暴力 2

（该部分分对正解启发不大，一笔带过）

$dp(s)$ 表示在 前 $i$ 个数中，选的数质因数集合恰好为 $s$ 的情况数。然后再算出 $dp$ 的子集和，即 $f(s)=\sum_{i \subset s} dp(i)$ ，答案便是 $\sum _{i\subset P}dp(i)f(P \setminus i)$。

仅仅这样还是不够的，因为小于一百的质数有 $25$ 个，但是发现大于 $50$ 的每个质因数只可能出现一次，所以我们可以只考虑剩下的小于等于 $50$ 的 $15$ 个质数，最后将答案乘以 $3^{\pi(n)-\pi(50)}$ 即可，可得 $50$ 分。

正解

$n \le 500$，则小于 $n$ 的质数大概有一百个了，仿佛就无法状压了。但经过仔细观察（看题解），发现每个数只可能有一个大于 $\sqrt{500}$ 的质因数，也就是说，每个数除了这个最大质因数之外，剩下的质因数都小于 $19$。

小于 $19$ 的质因数只有 $8$ 个，不难状压，所以我们只要考虑如何排除那些大质因数的干扰。

考虑将这些数按其大质因数排序，则大质因数相同的一个连续段中的每个数要么只被小 G 选或不被选，要么只被小 W 选或不被选。

考虑如下 dp：

  • $dp(s_1,s_2)$ 含义与暴力 1 中的差不多，只不过这里的 $s_1$，$s_2$ 只状压了前 8 个质数的状态。

  • 每次进入一个新的连续段，把 $dp$ 中的值复制到 $t_1，t_2$ 中。

    • 用 $t_1(s_1,s_2)$ 表示这个连续段中的数只被小 G 选或不被选的情况数
    • 用 $t_2(s_1,s_2)$ 表示这个连续段中的数只被小 W 选或不被选的情况数
    • 转移：
    $$\begin{aligned} t_1(s_1\cup fac_i,s_2)\gets t_1(s_1\cup fac_i,s_2)+t_1(s_1,s_2)&\ &(fac_i\cap s_2=\varnothing)\cr t_2(s_1,s_2\cup fac_i)\gets t_2(s_1,s_2\cup fac_i)+t_2(s_1,s_2)&&(fac_i\cap s_1=\varnothing)\cr \end{aligned}$$

  • 这个连续段结束之后，再用 $t_1$，$t_2$ 中的值更新 $dp$ 值：

$$ dp(s_1,s_2)\gets t_1(s_1,s_2)+t_2(s_1,s_2)-dp(s_1,s_2) $$

为什么要减去 $dp(s_1,s_2)$ 呢？因为这一段中所有数都不选的情况被算了两次（$t_1$，$t_2$ 各一次）。

小优化

截止目前，算法复杂度还是 $O(n \times 4^8)$ 的，但是不难发现对于一个合法状态，是要求 $s_1$，$s_2$ 交为空的。因此真正有用的状态数只有 $3^8$ 量级。 所以我们可以如下枚举 $s_1$ 和 $s_2$：

1
2
3
4
5
6
7

int ALL=1<<8;
for(int s1=ALL-1;~s1;s1--){//因为是滚动数组，所以集合必须从大到小枚举
	int tmp=(ALL-1)^s1;//s2 必定是 tmp 的子集
	for(int s2=tmp;s2;s2=(s2-1)&tmp)
		//blabla...
	//单独处理 s2=0 的情况
}

代码 

 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

#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
typedef pair<int,int> pi;

const int MXPRI=8;
const int ALL=1<<MXPRI;
const int MXN=505;
const int pri[]={2,3,5,7,11,13,17,19};

int n,p,dp[ALL][ALL],t1[ALL][ALL],t2[ALL][ALL];
pi arr[MXN];
inline int mod(int x){return x<p?x:x-p;}

int main(){
	scanf("%d%d",&n,&p);
	for(int i=2,j;i<=n;i++)
		for(arr[i].fi=i,j=0;j<MXPRI;j++)
			while(arr[i].fi%pri[j]==0)
				arr[i].fi/=pri[j],arr[i].se|=1<<j;
	sort(arr+2,arr+n+1);
	t1[0][0]=1;
	for(int i=2;i<=n;i++){
		if(arr[i].fi==1 || arr[i].fi!=arr[i-1].fi)
			for(int s1=ALL-1;~s1;s1--){
				int tmp=(ALL-1)^s1;
				for(int s2=tmp;s2;s2=(s2-1)&tmp)
					t1[s1][s2]=t2[s1][s2]=dp[s1][s2]=mod(p-dp[s1][s2]+mod(t1[s1][s2]+t2[s1][s2]));
				t1[s1][0]=t2[s1][0]=dp[s1][0]=mod(p-dp[s1][0]+mod(t1[s1][0]+t2[s1][0]));
			}

		for(int s1=ALL-1,fac=arr[i].se;~s1;s1--){
			int tmp=(ALL-1)^s1;
			for(int s2=tmp;s2;s2=(s2-1)&tmp){
				if(!(fac&s2))t1[s1|fac][s2]=mod(t1[s1|fac][s2]+t1[s1][s2]);
				if(!(fac&s1))t2[s1][s2|fac]=mod(t2[s1][s2|fac]+t2[s1][s2]);
			}
			t1[s1|fac][0]=mod(t1[s1|fac][0]+t1[s1][0]);
			if(!(fac&s1))t2[s1][fac]=mod(t2[s1][fac]+t2[s1][0]);
		}
	}
	int ans=0;
	for(int s1=ALL-1;~s1;s1--){
		int tmp=(ALL-1)^s1;
		for(int s2=tmp;s2;s2=(s2-1)&tmp)
			ans=mod(ans+mod(p-dp[s1][s2]+mod(t1[s1][s2]+t2[s1][s2])));
		ans=mod(ans+mod(p-dp[s1][0]+mod(t1[s1][0]+t2[s1][0])));
	}
	printf("%d\n",ans);
	return 0;
}