题概：

题目描述

一个有N个元素的集合有2^N个不同子集（包含空集），现在要

在这2^N个集合中取出若干集合（至少一个），使得它们的交集

的元素个数为K，求取法的方案数，答案模1000000007。（是质数喔~）

输入格式

一行两个整数N,K

输出格式

一行为答案。

样例

样例输入

　3 2

样例输出

　6

数据范围与提示

样例说明

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

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

数据说明

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

关键字：

　　容斥定理，线性推逆元

思路：

　　ans=C(n,k)*{sigma(0,i)&&(i&1==0){C(n-k,i)*(pow(2,bin[n-i-k])-1)}

　　　　-sigma(0,i)&&(i&1==1){C(n-k,i)*(pow(2,bin[n-i-k]-1)}}

首先，能想到交集的k个数并不能确定

所以最终*C(n,k)

k个数是所有符合方案中必备的数

那末只考虑在n-k个数中选出

所有符合取不到交集的数量

很自然的可以得到

SUM=2^(2^(n-k))-1(抛去一个都不选的情况)

接下来就是kx（开心）地容斥　

考虑所谓的SUM是至少有0个

交集的方案数

以此类推

我们可以得到sum[i]为至少有i个

交集的方案数

最终为sum[0]-sum[1]+sum[2]-sum[3]+...

此时思考为什莫

直接来看是至少为0的-至少为1的

但其实会多减

因为所谓的sum[1]是在每个交集的那个数

确定时计算粗来的

所以每个数确定时都会有相同的无

交集情况，所以要用sum[2]加回来

emmm

然后就感性地用了容斥

然而证明容斥就先撂了吧

注意：

　　欧拉定理是用来阐述素数模下，指数同余的性质

　　　优化指数部分

　　　如果要取模

　　　要mod(1000000007-1)　

　　　举例：

　　　　　如计算7²²²的个位数，实际是求7²²²被10除的余数

　　　　　　7和10互素，且φ(10)=4

 

　　　　　　由欧拉定理知7⁴ Ξ 1 (MOD 10)

 

　　　　　　所以7²²² == (7⁴)⁵⁵ * (7²) Ξ 1⁵⁵ * 7² Ξ 49 Ξ 9 (mod 10)

　　　　所谓降幂模法

最后

 1 #include<iostream>
 2 #include<cstdio>
 3 #define ll long long
 4 #define MAXN 1000010
 5 using namespace std;
 6 #define mod 1000000007
 7 int n,k;//1000000
 8 ll inv[MAXN];
 9 ll inv_jc[MAXN];
10 ll jc[MAXN];
11 ll pow(ll a,ll b){
12     ll ans=1;
13     while(b){
14         if(b&1)ans=ans*a%mod;
15         b>>=1;
16         a=a*a%mod;
17     }
18     return ans%mod;
19 }
20 void init_inv(){
21     inv[1]=1;
22     inv_jc[1]=1;
23     jc[1]=1;
24     for(int i=2;i<=n;++i){
25         jc[i]=jc[i-1]*i%mod;
26         inv[i]=(mod-mod/i)*inv[mod%i]%mod;
27         inv_jc[i]=inv_jc[i-1]*inv[i]%mod;
28     }
29 }
30 ll C(int n,int m){
31     if(!m)return 1;
32     if(n==m)return 1;
33     return jc[n]*inv_jc[n-m]%mod*inv_jc[m]%mod;
34 }
35 ll res;
36 ll bin[MAXN];
37 void init_bin(){
38     bin[0]=1;
39     for(int i=1;i<=n;++i)bin[i]=(bin[i-1]<<1)%(mod-1);
40 }
41 int main(){
42     scanf("%d%d",&n,&k);
43     init_inv();
44     init_bin();
45 //    cout<<pow(2,1)<<endl;
46     for(int i=0;i<=n-k;++i){
47         switch(i&1){
48             case 1:{
49                 res=(res+mod-C(n-k,i)*(pow(2,bin[n-k-i])-1)%mod)%mod;
50                 break;
51             }
52             case 0:{
53                 res=(res+C(n-k,i)*(pow(2,bin[n-i-k])-1)%mod)%mod;
54                 break;
55             }
56         }
57 //        printf("%lld\n",res);
58     }
59     res=res*C(n,k)%mod;
60     printf("%lld\n",res%mod);
61 }

View Code