ZOJ-4069
解题思路:
1.n个点组成环的不同种类数是(n-1)!/2;n个点组成一条链的不同种类数是n!/2,特别的n==1时种类数为1。
用指数型生成函数表示k个点形成链的种类: 1/2(2x+2!x2/2!+3!*x3/3!+4!x4/4!+..+n!*xn/n!) = 1/2(2*x+x2+x3+x4+..+xn) = S
xS = 1/2(2x2+x3+x4+..+x(n+1)),xS - S = 1/2(x2+x(n+1)-2x),S = 1/2(x2+x(n+1)-2x)/(x-1) = 1/2x*(x+x^n-2)/(x-1)。
当|x|<1时,n->∞时,x^n->0,S = 1/2x(x-2)/(x-1) = x*(1-x/2)/(1-x)
同理用上诉方法当|x|<1,n->∞时可以求得1+x+x2+x3+...+x^n = 1/(1-x)。(这个不就是上面式子的分母吗?下面会说他的作用)
2.如果在n个点中只给你m条边，那么最后形成的图肯定是由n-m条链组成的,令k = n - m。
3.那么要求n个点组成k条链的不同方案数就是求S^k = (x*(1-x/2)/(1-x))k的多项式展开的第n项的系数，也就是a[n]*xn/n!,a[n]就是我们要求的,不过最后还要除以k!，因为k条链不需要分先后顺序。
4.S^k = (x(1-x/2)/(1-x))^k = xk*(1-x/2)k(1/(1-x))k,此处(1-x/2)k可以用二项式展开，那么1/(1-x)该如何处理呢,这就用到了上面已经求出的1/(1-x)的多项式,这个多项式所以系数都是1，那么与此多项式相乘得到第n项的系数不就是原多项式的0到n项系数的和吗？
所以(1-x/2)^k的多项式乘一次1/(1-x)得到新的系数，就是求n前系数前缀和，乘k次就是求k次。
5.在k次求前缀和中我们可以直接算出原多项式((1-x/2)^k)的每一项系数对最终结果的贡献。此处列举第1项的系数的贡献T，当k=1时显然T = 1,k = 2时此时所有1到n的项第1项都加上了一次，所以T = k,这个结果就可以想到用组合求解。所以对于求k次前缀和之后原第i项对最终第j项(j>=i)的贡献次数是C(j-i+k-1,k-1)。可以用(C(m,m)+C(m+1,m)+C(m+2,m)+C(m+3,m)+...+C(n,m)==C(n+1,m+1))去推。
6.最后记得乘上(1-x/2)k上的-1/2的幂啊!求个逆元就行了，还有此多项式的第i项系数就是C(k,i)*(-1/2)i。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int mx = 1e5 + 10;
ll fac[mx],inv[mx];
ll n ,m;
void init()
{
inv[0] = fac[0] = inv[1] = 1;
for(int i=1;i<mx;i++) fac[i] = fac[i-1]*i%mod;
for(int i = 2;i<mx;++i) inv[i] = (mod-mod/i)*inv[mod%i] % mod;
for(int i=2;i<mx;i++) inv[i] = inv[i]*inv[i-1]%mod;
}
ll C(int x,int y)
{
return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int main()
{
int t;
init();
scanf("%d",&t);
while(t--){
scanf("%lld%lld",&n,&m);
if(m>n){
puts("0");
continue;
}
if(m==n){
printf("%lld
",fac[n-1]*inv[2]%mod);
continue;
}
ll ans = 0,base = 1;
int k = n - m,cnt = min(m,n-m);
for(int i=0;i<=cnt;i++){
ans = (ans + C(k,i)*base%mod*C(m-i+k-1,k-1))%mod;
base = base * -inv[2]%mod;
}
ans = (ans+mod)%mod;
printf("%lld
",ans*fac[n]%mod*inv[n-m]%mod);
}
return 0;
}