主题链接：

http://acm.zju.edu.cn/onlinejudge/showProblem.do?

problemId=4535

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

---

Author: QU, Zhe

Contest: ZOJ Monthly, October 2011

Submit    

problemId=4535" style="color:blue; text-decoration:none">Status

题目意思：

已知|S|=n。给定k,求S₁ ∩ S₂ ∩
... ∩ S_k = ∅,当中Si是S的子集（i<=k)的种数。

n,k<=2^31-1

解题思路：

容斥原理

反向考虑。如果S₁ ∩ S₂ ∩
... ∩ S_k 不等于 ∅。则至少存在一个元素S1。S2。...，Sk都包括。

枚举都包括的元素.总的种数为(2^n)^k=2^(nk)

假设至少都包括一个元素，则种数为C(n,1)*(2^(n-1))^k=C(n,1)*2^((n-1)k)

假设至少都包括两个元素，则种数为C(n,2)*(2^(n-2))^k=C(n,2)*2^((n-2)k)

假设至少都包括i个元素，则种数为C(n,i)*(2^(n-i))^k=C(n,i)*2^((n-i)k)

减去包括一个的加上包括两个的减去包括3个的，如此类推。能够得出一下公式：

2^(nk)+C(n,1)*2^((n-1)k)-C(n,2)*2^((n-2)k)+...(-1)^i*C(n,i)*2^((n-i)k)+.....=(2^k-1)^n
 (通过二项式公式）

所以答案转化为求(2^k-1)^n了，直接高速幂就可以。

代码：

//#include<CSpreadSheet.h>

#include<iostream>

#include<cmath>

#include<cstdio>

#include<sstream>

#include<cstdlib>

#include<string>

#include<string.h>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<stack>

#include<list>

#include<queue>

#include<ctime>

#include<bitset>

#include<cmath>

#define eps 1e-6

#define INF 0x3f3f3f3f

#define PI acos(-1.0)

#define ll __int64

#define LL long long

#define lson l,m,(rt<<1)

#define rson m+1,r,(rt<<1)|1

#define M 1000000007

//#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

LL n,k;

LL quick(LL a,LL b)

{

    LL res=1;

    while(b)

    {

        if(b&1)

            res=(res*a)%M;

        b>>=1;

        a=a*a%M;

    }

    return res;

}

int main()

{

   //freopen("in.txt","r",stdin);

   //freopen("out.txt","w",stdout);

   while(~scanf("%lld%lld",&n,&k))

   {

       LL ans=(quick(2,k)-1+M)%M;

       ans=quick(ans,n);

       printf("%lld\n",ans);

   }

   return 0;

}