「CF585E」 Present for Vitalik the Philatelist

传送门

我们可以考虑枚举 \(S'=S\cup\{x\}\)，那么显然有 \(\gcd\{S'\}=1\)。

那么我们从里面可以选一个数出来作为 \(x\)，共有 \(|S'|\) 种可能，我们记为 \((x,S)\)。

但是这样显然会计算到一些不合法的情况，考虑统计。

对于一个集合 \(S\)，若其 \(\gcd\) 为 \(1\)，则再任意添加一个数 \(\gcd\) 仍为 \(1\)，这样的二元组显然是不合法的，共有 \(n-|S|\) 种可能。

所以对于一个 \(\gcd\) 为 \(1\) 的集合 \(S\)，其对答案的贡献就是 \(|S|-(n-|S|)=2|S|-n\)。

设给出的数的集合为 \(U\)，故答案可表示为

\[\sum_{S\subseteq U,S\neq \varnothing}[\gcd \{S\}=1](2|S|-n)
\]

显然可以考虑莫比乌斯反演，于是有

\[\sum_{d}\mu(d)\sum_{S\subseteq U\cap\{x|x=kd,k\in \mathbb{Z}\},S\neq \varnothing}(2|S|-n)
\]

令 \(T=U\cap\{x|x=kd,k\in \mathbb{Z}\}\)，我们的问题就变为了计算

\[\sum_{S\subseteq T,S\neq \varnothing}(2|S|-n)
\]

首先这个不等于空集很烦，我们可以把它加上最后再减去，变为

\[n+2\sum_{S\subseteq T}|S|-\sum_{S\subseteq T}n
\]

后面那部分很好算，共有 \(2^{|T|}\) 种集合，答案即为 \(2^{|T|}n\)。

前一部分可以考虑计算每个数对答案的贡献，枚举选某个数（共 \(|T|\) 种可能），剩下的 \(|T|-1\) 个元素都是选或不选，故答案为 \(2(2^{|T|-1}|T|)=2^{|T|}|T|\)。

然后问题就变成了如何求 \(T\)。

这个东西可以直接分解质因数，也可以用 \(\text{Dirichlet}\) 后缀和，在此不再赘述。

总复杂度大概是 \(O(V\log_2\log_2V+n)\) 的，其中 \(V\) 表示值域。

贴代码

/*---Author:HenryHuang---*/

/*---Never Settle---*/

/*---Never Enough---*/

#include<bits/stdc++.h>

#define module(x) ((x)>=p?((x)-p):(x))

using namespace std;

const int maxn=1e7+5;

const int p=1e9+7;

int pri[maxn],pp[maxn],mu[maxn],cnt;

int p2[maxn];

int sum[maxn];

void init(int mx){

	mu[1]=1;

	for(int i=2;i<=mx;++i){

		if(!pp[i]) pri[++cnt]=i,mu[i]=-1;

		for(int j=1;j<=cnt&&i*pri[j]<=mx;++j){

			pp[i*pri[j]]=1;

			if(i%pri[j]==0){

				mu[i*pri[j]]=0;

				break;

			}

			else mu[i*pri[j]]=-mu[i];

		}

	}

}

int main(){

	ios::sync_with_stdio(0);

	cin.tie(0),cout.tie(0);

	int n;cin>>n;

	p2[0]=1;

	int mx=0;

	for(int i=1;i<=n;++i){

		int x;cin>>x;mx=max(mx,x);

		++sum[x];

		p2[i]=module(p2[i-1]<<1);

	}

	init(mx);

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

		for(int j=mx/pri[i];j;--j)

			sum[j]+=sum[j*pri[i]];

	int ans=0;

	for(int i=1;i<=mx;++i){

		if(mu[i]){

			int tmp=1ll*(1ll*p2[sum[i]]*(sum[i]-n+p)+n)%p;

			if(mu[i]>0) ans=module(ans+tmp);

			else ans=module(ans-tmp+p);

		}

	}

	cout<<module(ans+p)<<'\n';

	return 0;

}

巴特西

「CF585E」 Present for Vitalik the Philatelist

「CF585E」 Present for Vitalik the Philatelist

最新文章

热门文章