zoj3556 How Many Sets I-------容斥

How Many Sets I
Time Limit: 2 Seconds      Memory Limit: 65536 KB
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
[cpp] 
#include<iostream> 
#include<cstdlib> 
#include<stdio.h> 
using namespace std; 
#define mm 1000000007 
typedef long long ll; 
ll powermod(ll a,ll b) 
{ 
    ll res=1; 
    while(b) 
    { 
        if(b&1)res=(res*a)%mm;//不能寫成res*=a%mm~~~~~~~~~ 
        a=a*a; 
        a%=mm; 
        b>>=1; 
    } 
    return res%mm; 
} 
int main() 
{ 
    ll n,k; 
    while(scanf("%lld%lld",&n,&k)!=EOF) 
    { 
        ll ans=powermod(2,k); 
        ans--; 
        ans=powermod(ans,n); 
        printf("%lld\n",ans); 
    } 
}