【题解】寿司晚宴

最优解!

Posted by ethan-zhou on May 27, 2021

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

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

定义

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

暴力 1

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

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

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

复杂度 $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。

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

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

考虑如下 dp:

  • $dp(s1,s2)$ 含义与 暴力 1 中的差不多,只不过这里的 s1,s2 只状压了前 8 个质数的状态。
  • 每次进入一个新的连续段,把 dp 中的值复制到 t1,t2 中。
    • 用 $dp(s1,s2)$ 表示这个连续段中的数只被小 G 选或不被选的情况数
    • 用 $dp(s1,s2)$ 表示这个连续段中的数只被小 W 选或不被选的情况数
    • 转移:
    \[\begin{aligned} dp(s1\cup fac_i,s2)\gets dp(s1\cup fac_i,s2)+dp(s1,s2)&\ &(fac_i\cap s2=\varnothing)\cr dp(s1,s2\cup fac_i)\gets dp(s1,s2\cup fac_i)+dp(s1,s2)&&(fac_i\cap s1=\varnothing)\cr \end{aligned}\]
  • 这个连续段结束之后,再用 t1,t2 中的值更新 dp 值:
\[dp(s1,s2)\gets dp(s1,s2)+dp(s1,s2)-dp(s1,s2)\]

为什么要减去 $dp(s1,s2)$ 呢?因为这一段中所有数都不选的情况被算了两次(t1,t2 各一次)。

小优化

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

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 的情况
}

代码

#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;
}

作者:@ethan-enhe
本文为作者原创,转载请注明出处:本文链接



icon