Give a set S, |S| = n, then how many ordered set group (S1, S2, ..., Sk) satisfies S1 ∩ S2 ∩ ... ∩ Sk = ∅. (Si is a subset of S, (1 <= i <= k))
Input
The input contains multiple cases, each case have 2 integers in one line represent n and k(1 <= k <= n <= 231-1), proceed to the end of the file.
Output
Output the total number mod 1000000007.
Sample Input
1 1 2 2
Sample Output
1 9
思路:容斥原理;
推公式;
个数为n的集合的子集有2^n个,从中选出K个使得他们的交集为空的个数。
由于集合可以重复被选,所以总的数目是2^(kn)
然后选中的集合都包含x这个数的数目是c(n,1)*2^(n-1)k
选中的集合包含x1,x2的数目是c(n,2)*2^(n-2)k
……
所以满足的集合的个数res=2^kn-c(n,1)*2^(n-1)k+c(n,2)*2(n-2)k-……
推出的公式为(2^k-1)^n
上面的讲解来自http://blog.csdn.net/qiqijianglu/article/details/7932226;
1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<string.h> 5 #include<queue> 6 #include<stack> 7 #include<map> 8 #include<math.h> 9 using namespace std; 10 typedef long long LL; 11 LL quick(LL n,LL m); 12 LL N=1e9+7; 13 int main(void) 14 { 15 int i,j,k; 16 LL n,m; 17 while(scanf("%lld %lld",&n,&m)!=EOF) 18 { 19 LL cc=quick(2,m); 20 cc-=1; 21 cc=((cc%N)+N)%N; 22 LL dd=quick(cc,n); 23 printf("%lld ",dd); 24 } 25 return 0; 26 } 27 LL quick(LL n,LL m) 28 { 29 LL ans=1; 30 while(m) 31 { 32 if(m&1) 33 { 34 ans=(ans*n)%N; 35 } 36 n=n*n%N; 37 m/=2; 38 } 39 return ans; 40 }