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 1000000007

using 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

最新文章

热门文章