How Many Sets I（容斥定理）

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3556

How Many Sets I

---

Time Limit: 2 Seconds      Memory Limit: 65536 KB

---

Give a set S, |S| = n, then how many ordered set group (S₁, S₂, ..., S_k) satisfies S₁ ∩ S₂ ∩ ... ∩ S_k = ∅. (S_i 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 <= 2³¹-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和k 分别表示有一个元素个数为n的集合，从中选出它的k个子集，求k个不相交子集的总数
题解：数学题，容斥定理
首先，n个元素的集合的子集有2^n个，每次从中选出k个集合就是总共2^nk种情况，其中包含一个公共元素的情况有C(1,n)*2^(n-1)k,包含两个公共元素的情况有C(2,n)*2^(n-2)*k，根据容斥定理得出总数为　　所有情况-含有一个公共元素的+含有两个公共元素的-含有三个公共元素的+含有四个公共元素的……最后根据二项式公式，得出最后结果为(2^k-1)^n;
介绍一下容斥定理（加法公式）：
引入：如果被计数的事物有A、B两类，那么，A类B类元素个数总和= 属于A类元素个数+ 属于B类元素个数—既是A类又是B类的元素个数。（A∪B = A+B - A∩B)
公式介绍：


对于这道题来说，要求的是拥有公共元素个数为0的，用容斥定理的推论上式的最后一项，移向即可，现在可以。
代码：

 #include<cstdio>
 #include<cstring>
 using namespace std;
 const int M = ;
 #define ll long long
 ll f(ll a,ll b)
 {
     ll res = ;
     while(b)
     {
         if(b&) res = (res*a)%M;
         a = a*a;
         a %= M;
         b= b/;
     }
     return res%M;
 }
 int main()
 {
     ll n,k;
     while(~scanf("%lld%lld",&n,&k))
     {
         ll ans = f(,k);
         ans--;
         ans = f(ans,n);
         printf("%lld\n",ans);
     }
     return ;
 }