目录
显示
题目链接
https://www.luogu.com.cn/problem/P6570
题解
容易发现本题的实质是这样的：给若干个集合，从中选择一些集合，要求被选择的集合间两两没有交集，求所有合法选择方案中被选集合的权值和。
我们设 \(f_i\) 表示选出的集合的并集为 \(i\) 的合法选择方案数，则答案为 \(\sum f_i \varphi(i+1)\)。
现在考虑如何计算 \(f_i\)。
设 \(cnt_x\) 表示 \(x\) 集合出现的次数。
则有：
$$f_x=\sum_{y \in x} f_y \times cnt_{x-y}$$
边界是 \(f_0=2^{cnt_0}\)。
设集合包含的元素的个数的最大值为 \(s\)，则时间复杂度为 \(O(3^s)\)（看起来不太能过的样子，不过事实上还是过了）。
当然可以用子集卷积的方法做到 \(O(s^2 2^s)\) 的时间复杂度，不过因为不会子集卷积就不展开讲了。
#include <iostream>
#include <algorithm>
#define MOD 1000000007
using namespace std;
int phi[400005],pri[400005],a[400005],cnt;
long long f[400005];
int fpow(int x,int y)
{
int ans=1;
for(int i=1;i<=y;i++)
ans=ans*x%MOD;
return ans;
}
int main()
{
int n,mx=0;
cin>>n;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
a[x]++;
mx=max(mx,x);
}
phi[1]=1;
int w=0;
while(mx>=(1<<w))
w++;
for(int i=2;i<=(1<<w);i++)
{
if(!phi[i])
pri[++cnt]=i,phi[i]=i-1;
for(int j=1;j<=cnt&&i*pri[j]<=(1<<w);j++)
{
if(i%pri[j]!=0)
phi[i*pri[j]]=phi[i]*phi[pri[j]];
else
{
phi[i*pri[j]]=phi[i]*pri[j];
break;
}
}
}
f[0]=fpow(2,a[0]);
int p=0;
for(int i=1;i<=mx;i++)
if(a[i])
{
p|=i;
int s=p^i;
for(int t=s;;t=(t-1)&s)
{
f[i|t]=(f[i|t]+f[t]*a[i])%MOD;
if(!t)break;
}
}
long long ans=0;
for(int i=0;i<(1<<w);i++)
ans=(ans+f[i]*phi[i+1])%MOD;
cout<<ans<<endl;
return 0;
}