首页 > 代码库 > [容斥原理] zoj 3556 How Many Sets I
[容斥原理] zoj 3556 How Many Sets I
题目链接:
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4535
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
Author: QU, Zhe
Contest: ZOJ Monthly, October 2011
题目意思:
已知|S|=n,给定k,求S1 ∩ S2 ∩ ... ∩ Sk = ?,其中Si是S的子集(i<=k)的种数。
n,k<=2^31-1
解题思路:
容斥原理
反向考虑,假设S1 ∩ S2 ∩ ... ∩ Sk 不等于 ?,则至少存在一个元素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; }