【题解】寿司晚宴

最优解!

Posted by ethan-zhou on May 27, 2021

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

暴力

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

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

  • 状态:$dp[s1][s2]$ 表示考虑前 i 个数(i被滚动掉了),小 G 选的数的包含的质因数集合为 s1,小 W 的质因数集合为 s2 的情况数。
  • 转移: 假设 $fac_i$ 表示 i 的质因数集合,则有转移:
\[\begin{aligned} dp[s1|fac_i][s2]\leftarrow dp[s1][s2]+dp[s1|fac_i][s2]&\ &(fac_i\&s2=0)\cr dp[s1][s2|fac_i]\leftarrow dp[s1][s2]+dp[s1][s2|fac_i]&&(fac_i\&s1=0) \end{aligned}\]
  • 答案:
\[\sum _{s1,s2 \in\{x|x\ is\ prime,\ x\in[2,n]\}}{dp[s1][s2]\ (s1\&s2=0))}\]

虽然这个状态在 $n\le 30$ 时显然可以优化,但是优化了的话就没法做更大范围了,复杂度 ${\rm O}(n\times2^{20})$。

正解

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

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

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

考虑如下 dp:

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

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

小优化

截止目前,算法复杂度还是 ${\rm 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
本文为作者原创,转载请注明出处:本文链接