[BZOJ2839]集合计数

清疚 2021-12-16 09:41 222阅读 0赞

# 集合计数 #

#### 题目描述 ####

一个有N个元素的集合有2^N个不同子集（包含空集），现在要在这2^N个集合中取出若干集合（至少一个），使得它们的交集的元素个数为K，求取法的方案数，答案模1000000007。（是质数喔~）

#### 输入格式 ####

一行两个整数N,K

#### 输出格式 ####

一行为答案。

#### 样例 ####

#### 样例输入 ####

3 2

#### 样例输出 ####

#### 数据范围与提示 ####

#### 样例说明 ####

假设原集合为\{A,B,C\}

则满足条件的方案为：\{AB,ABC\},\{AC,ABC\},\{BC,ABC\},\{AB\},\{AC\},\{BC\}

#### 数据说明 ####

对于100%的数据，1≤N≤1000000；0≤K≤N；

![1729058-20190705111932728-1255129966.png][]咱也不知道为啥BZOJ上这题长这样

我是一个分不清交并集的人，对不起数学老师，如有错误，欢迎指正

**基本思路**

依旧一道数论题，组合数学，既然交集要定k，那最先想到的肯定是Ckn(我也不知道为啥我的C长这样)，把它摆在这，显然不对，既然交集已经定下来了，我们就需要考虑用谁跟这些交集并，组成集合，交集定好为k了，那么就必须保证跟交集拼的这部分元素一定没有交集，然后的然后咱也不知道大佬们怎么就想到了容斥这个神奇的东西，对，这题需要容斥

要求剩下的为空集那肿么斥呢，都告诉你容斥了，那就好想了，其实

Φ=随便选的方法数-交集>=1的方法数+交集>=2的方案数……以此类推

这样的话最终答案就是Ckn\*Φ的方案数

接下来就是解决这个交集数>=i的方案数怎么求，我们用f\[i\]表示交集>=i的方案数，还是先定下Cin，但是此时并不需要剩下的一定为空集，那剩下的集合就随便拼就好了，那方案数就是22^(n-i)(我垃圾，我搞不出来人家都搞得出来的连续往上加幂，只能这样了，就是2的2的n-i次幂，自己应该可以想到，就是先拼成集合，再把集合拼成集合)，但是要注意这么拼出来可能会是空集拼上空集，这显然不符合题意，所以要-1，故最终

f\[i\]=Cin\*(22^(n-i)\-1)

关于一加一减那一块，你可以选择直接判i的奇偶或者加一个(-1)i就好了

提问：在求f\[i\]中的n是输入的n吗？我大概在这死了一节多课

答：并不是

思考一下，你拼空集的时候还剩下n个元素吗？显然不是，因为你前面已经定下了k个元素作为交集，那此时再选元素，显然不能同一个元素选两次，所以**现在的n实际上应该是n-k**

到此这题就搞出来了，然后就来讲讲我都WA过些啥

![1729058-20190705115512440-700120675.png][]

**WA70**

是我高看了取模这种东西，要知道取模之后不一定严格遵守取模之前的大小关系，所以就会出现全集的方案数小于后面某一的个方案数，这样的话，ans就会出负数了，然后磕了一节课，最后的解决方案是如果答案为负，加一个模数就好了

**WA90**

我更像个zz了，我数组开的1000000，然后就WA了

**几点注意**

关于那个22^(n-i)的求法，给2n-i取模肯定就死翘翘了，不取模数据大了依旧死翘翘，那怎么解决呢？换个不影响结果的模数，这个时候就用到我不会的玩意了

![1729058-20190705120513152-2141849994.png][]

图片截取自https://blog.csdn.net/doyouseeman/article/details/51863382我不会直接加链接

而我依旧zz，1000000007的欧拉函数怎么求？他是个质数，是个质数，那他的欧拉函数就是1000000006！！！！！！！！

long long记得开，求逆元可以用线性的

1 #include<iostream>
     2 #include<cstdio>
     3 #include<cmath>
     4 #define ll long long
     5 #define maxn 1000100
     6 const long long mod1=1000000007;
     7 const long long mod2=1000000006;
     8 using namespace std;
     9 int n,k;
    10 ll ny[maxn],jc[maxn],f[maxn];
    11 ll ksm(ll a,ll b,ll c)
    12 {
    13     ll ans=1;
    14     a=a%c;
    15     while(b>0)
    16     {
    17         if(b&1)  ans=(ans*a)%c;
    18         b=b>>1;
    19         a=(a*a)%c;
    20     }
    21     return ans%c;
    22 }
    23 ll c(int n,int m)
    24 {
    25     if(n<m)  return 0;
    26     if(n<mod1&&m<mod1)  return ((jc[n]*ny[m])%mod1*ny[n-m])%mod1;
    27     return (c(n/mod1,m/mod1)*c(n%mod1,m%mod1))%mod1;
    28 }
    29 int main()
    30 {
    31     //freopen("3.in","r",stdin);
    32     //freopen("WA.out","w",stdout);
    33     scanf("%d%d",&n,&k);
    34     jc[0]=1;
    35     for(int i=1;i<=n;++i)  jc[i]=(jc[i-1]*i)%mod1;
    36     ny[n]=ksm(jc[n],mod1-2,mod1);
    37     for(int i=n;i>=1;--i)  ny[i-1]=(ny[i]*i)%mod1;
    38     int ls=n-k;
    39     for(int i=0;i<=ls;++i)
    40     {
    41         ll mi=ksm(2,ls-i,mod2);
    42         ll ch;
    43         if(i&1)  ch=-1;
    44         else  ch=1;
    45         f[i]=(c(ls,i)*(ksm(2,mi,mod1)-1))%mod1;
    46         f[i]*=ch;
    47     }
    48     ll tot=0;
    49     for(int i=0;i<=ls;++i)
    50     {
    51         tot+=f[i];
    52         tot=tot%mod1;
    53     }
    54     ll ans=(c(n,k)*tot)%mod1;
    55     while(ans<0)  ans+=mod1;
    56     printf("%lld\n",ans);
    57     return 0;
    58 }

转载于:https://www.cnblogs.com/hzjuruo/p/11137556.html

[1729058-20190705111932728-1255129966.png]: /images/20211214/afc55368687b44aeaea9d66178a540d5.png
[1729058-20190705115512440-700120675.png]: /images/20211214/904236eff4bf4fc4aebd5a480263f62b.png
[1729058-20190705120513152-2141849994.png]: /images/20211214/34e137a51b7b432ea01f851bddcc0c40.png