首页 > 代码库 > ZOJ 3556
ZOJ 3556
终于做出来了，激动。。。。
这道题隐藏得深啊，但若推导下来，就变简单了。
首先，一个集合的子集的个数为2^n=s。注意了，题目求的是有序集合组，并且每个集合是可以重复使用的，怎么办呢?这就要想到多重集合的排列问题了。
一个多重集合有k种元素，每种元素可以无限次使用，求r-排列个数。答案为 k^r个。
这样，我们使用容斥原理：
总个数为(2^n)^k个
包含一个元素的集合有序组为 C(n,1)(2^(n-1))^k
两个的为.....C(n,2)(2^(n-2))^k
。。。。
于是二项式定理+容斥原理公式化简即为(2^k-1)^n
#include <iostream>#include <cstdio>#include <algorithm>#define MOD 1000000007using namespace std;typedef long long LL;LL quick(LL a,LL b){ a%=MOD; LL ans=1LL; while(b){ if(b&1) ans=(ans*a)%MOD; b>>=1; a=(a*a)%MOD; } return ans;}int main(){ LL n,k; while(cin>>n>>k){ LL r=quick(2,k); r=((r-1)%MOD+MOD)%MOD; r=quick(r,n); printf("%lld\n",r); } return 0;}
ZOJ 3556
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。