目录
显示
题目链接
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; }