zoj3556 How Many Sets I-------容斥
How Many Sets ITime 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);
}
}
补充:软件开发 , C++ ,