【BZOJ5302】[HAOI2018]奇怪的背包（动态规划，容斥原理）

时间：2024-04-27 00:04:04

【BZOJ5302】[HAOI2018]奇怪的背包（动态规划，容斥原理）

题面

BZOJ

洛谷

题解

为啥泥萌做法和我都不一样啊

一个重量为\(V_i\)的物品，可以放出所有\(gcd(V_i,P)\)的重量，而多个物品也只要\(gcd\)就好了。

现在的问题转变成了有多少个集合\(S\)，满足\(S+\{P\}\)中所有数的\(gcd\)是\(w\)的因数。那么实际上就是直接令\(a[i]'=gcd(a[i],P)\)，然后选出一个集合使得它是\(gcd(P,w)\)的因数。

考虑对于\(P\)的每个因数预处理答案，不记得在哪里看到的，当\(P\)较大的时候，其约数个数是\(P^{\frac{1}{3}}\)级别，那么在这里就可以暴力把所有因数算出来之后\(O(\sigma^2)\)计算，即先统计有多少个\(a[i]'\)是当前\(d\)的倍数，那么贡献是\(2^{s}-1\)，然后容斥减去所有\(d\)的倍数的答案就是\(gcd\)为\(d\)的答案。然后再\(O(\sigma^2)\)的计算约数和就好了。

这样子复杂度大概是\(O((n+Q)logP+\sigma(P)^2)\)，前面那个\(log\)来自于\(gcd\)的复杂度。

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

#define MOD 1000000007

#define MAX 1000100

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int n,Q,P,a[MAX],bin[MAX];

const int blk=50000;

int w[blk],tot,id1[blk],id2[blk],f[blk],s[blk];

int ID(int x){return x<blk?id1[x]:id2[P/x];}

int S[blk],top;

int main()

{

	n=read();Q=read();P=read();

	for(int i=1;i<=n;++i)a[i]=__gcd(read(),P);

	bin[0]=1;for(int i=1;i<=n;++i)bin[i]=(bin[i-1]<<1)%MOD;

	for(int i=1;i*i<=P;++i)

		if(P%i==0)

		{

			w[++tot]=i;

			if(P/i!=i)w[++tot]=P/i;

		}

	sort(&w[1],&w[tot+1]);

	for(int i=1;i<=tot;++i)

		if(w[i]<blk)id1[w[i]]=i;

		else id2[P/w[i]]=i;

	for(int i=1;i<=n;++i)s[ID(a[i])]+=1;

	for(int i=tot;i;--i)

	{

		int cnt=0;top=0;

		for(int j=i;j<=tot;++j)

			if(w[j]%w[i]==0)S[++top]=j,cnt+=s[j];

		f[i]=bin[cnt]-1;

		for(int j=2;j<=top;++j)f[i]=(f[i]+MOD-f[S[j]])%MOD;

	}

	for(int i=tot;i;--i)

		for(int j=1;j<i;++j)

			if(w[i]%w[j]==0)f[i]=(f[i]+f[j])%MOD;

	while(Q--)

	{

		int d=__gcd(read(),P);

		printf("%d\n",f[ID(d)]);

	}

	return 0;

}

相关文章