首页 > 代码库 > ZOJ 3688
ZOJ 3688
做出这题，小有成就感
本来已打算要用那个禁位的排列公式，可是，问题在于，每个阶乘前的系数r的求法是一个难点。
随便翻了翻那本美国教材《组合数学》，在容斥原理一章的习题里竟有一道类似，虽然并无答案，但他的注意倒是提醒了我。不妨把那2*n个位置看成排成一个圆周的一列，从中选出k个不相邻的数的组合数。不过，经我验证，他上面的那道公式是错的，应该把n改成2*n才对。哈哈，问题就这样解决了。
在计组合数时，不妨使用全排列的公式，又由于100.。。0007是一个质数，所以可以使用费马小定理在处理各个阶乘除法时求得逆元。
解决。
#include <iostream>#include <cstdio>#include <algorithm>#define MOD 1000000007#define N 200005using 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
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。