1

【题解】寿司晚宴

 2 years ago
source link: https://blog-e.tk/2021/05/27/%E9%A2%98%E8%A7%A3-%E5%AF%BF%E5%8F%B8%E6%99%9A%E5%AE%B4/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
【题解】寿司晚宴 - Blog E

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

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

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

  • 状态：dp[s1][s2] 表示考虑前 i 个数（i被滚动掉了），小 G 选的数的包含的质因数集合为 s1，小 W 的质因数集合为 s2 的情况数。
  • 转移： 假设 faci 表示 i 的质因数集合，则有转移。 dp[s1|faci][s2]←dp[s1][s2]+dp[s1|faci][s2] (faci&s2=0)dp[s1][s2|faci]←dp[s1][s2]+dp[s1][s2|faci](faci&s1=0)
  • 答案： ∑s1,s2∈{x|x为n以内质数}dp[s1][s2] (s1&s2=0))

虽然这个状态在 n≤30 时显然可以优化，但是优化了的话就没法做更大范围了，复杂度 O(n×220)。

n≤500，则小于 n 的质数大概有一百个了，仿佛就无法状压了。但经过仔细观察（看题解），发现每个数只可能有一个大于 √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 选或不被选的情况数
    • 转移： t1[s1|faci][s2]←t1[s1|faci][s2]+t1[s1][s2] (faci&s2=0)t2[s1][s2|faci]←t2[s1][s2|faci]+t2[s1][s2](faci&s1=0)
  • 这个连续段结束之后，再用 t1，t2 中的值更新 dp 值： dp[s1][s2]←t1[s1][s2]+t2[s1][s2]−dp[s1][s2] 为什么要减去 dp[s1][s2] 呢？因为这一段中所有数都不选的情况被算了两次（t1，t2 各一次）。

截止目前，算法复杂度还是 O(n×48) 的，但是不难发现对于一个合法状态，是要求 s1，s2 交为空的。因此真正有用的状态数只有 38 量级。 所以我们可以如下枚举 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
本文为作者原创，转载请注明出处：本文链接

阅读量 75

来发评论吧~
Powered By Valine
v1.4.4

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK