[洛谷 6570][NOI Online #3 提高组]优秀子序列

题目链接

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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据