首页 > 代码库 > zoj How Many Sets I(组合计数)
zoj How Many Sets I(组合计数)
http://acm.zju.edu.cn/onlinejudge/showProblem.do?
problemId=4535
一个集合s有n个元素,求满足这种集合序列{s1,s2....sk}使S1 ∩ S2 ∩ ... ∩ Sk = ?。si是s的子集。
从每一个元素考虑会使问题变得简单。
首先n个元素是相互独立的,单独考虑第i个元素,它在k个子集的全部情况是2^k,当中有一种情况是k个子集都有第i个元素,这一种情况正好不是我们想要的,所以合法的应该是2^k-1。那么n个元素就是( 2^k-1 )^n。
#include <stdio.h> #include <iostream> #include <map> #include <set> #include <bitset> #include <list> #include <stack> #include <vector> #include <math.h> #include <string.h> #include <queue> #include <string> #include <stdlib.h> #include <algorithm> //#define LL __int64 #define LL long long #define ULL unsigned long long #define eps 1e-9 #define PI acos(-1.0) using namespace std; const LL mod = 1000000007; LL Pow(LL a, LL b) { LL res = 1; while(b) { if(b&1) res = (res*a)%mod; b >>= 1; a = (a*a)%mod; } return res; } int main() { LL n,k; while(~scanf("%lld %lld",&n,&k)) { LL res = Pow((LL)2,k); res -= 1; res = Pow(res,n); printf("%lld\n",res); } return 0; }
zoj How Many Sets I(组合计数)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。