ZOJ 3688

做出这题，小有成就感

本来已打算要用那个禁位的排列公式，可是，问题在于，每个阶乘前的系数r的求法是一个难点。

随便翻了翻那本美国教材《组合数学》，在容斥原理一章的习题里竟有一道类似，虽然并无答案，但他的注意倒是提醒了我。不妨把那2*n个位置看成排成一个圆周的一列，从中选出k个不相邻的数的组合数。不过，经我验证，他上面的那道公式是错的，应该把n改成2*n才对。哈哈，问题就这样解决了。

在计组合数时，不妨使用全排列的公式，又由于100.。。0007是一个质数，所以可以使用费马小定理在处理各个阶乘除法时求得逆元。

解决。

#include <iostream>

#include <cstdio>

#include <algorithm>

#define MOD 1000000007

#define N 200005

using namespace std;

typedef long long LL;

LL f[N];

void initial(){

	f[0]=1;

	for(LL i=1;i<N;i++)

	f[i]=(f[i-1]*i)%MOD;

}

LL quick(LL p,LL r){

	LL ans=1;

	while(r){

		if(r&1)

		ans=(ans*p)%MOD;

		r>>=1;

		p=(p*p)%MOD;

	}

	return ans;

}

int main(){

	initial();

	int n;

	while(scanf("%d",&n)!=EOF){

		if(n<3){

			printf("0\n");

			continue;

		}

		LL ans=f[n];

		int s=2*n;

		for(int i=1;i<=n;i++){

			LL uper=((LL)s*f[s-i-1])%MOD;

			LL down=(f[s-2*i]*f[i])%MOD;

			down=quick(down,MOD-2);

			LL res=(((uper*down)%MOD)*f[n-i])%MOD;

			if(i&1){

				ans=((ans-res)%MOD+MOD)%MOD;

			}

			else ans=((ans+res)%MOD+MOD)%MOD;

		}

		printf("%lld\n",ans);

	}

	return 0;

}

巴特西

ZOJ 3688

最新文章

热门文章