题解：P9896 [ICPC2018 Qingdao R] Sub-cycle Graph

· · 题解

其实是很笨蛋的一个题啦，不知道为什么大家都在 GF，其实压根不用的呢。

需要求的就是链的方案数，考虑把链分成单点和大于等于 2 的链。

我们先枚举不是单点的链的个数，同时也知道了单点链的个数。计算出这样的链长度之和是容易的，所以可以求出有序的链的方案数。然后往这些不是单点的链之间插入单点，得到了标号是 1 到 n 的方案数。

现在考虑有标号。对于每一次枚举，先对之前的方案数乘上一个 n 的阶乘，那么需要考虑的就是去重。考虑对于每一种情况而言，重复的次数正好就是对于所有不是单点的段翻转的方案数乘上所有段重排的方案数，因此乘上这个数即可。

由上得出答案为

\sum_{i=1}^{n-m}\dfrac{\binom{n-(x-i)-i-1}{i-1}\binom{x}{i}n!}{2^ix!}

其中 x 为链的段数。

柿子中前面两个组合数就是一开始所需要求的方案数，其他的即为后面计算并去重的过程。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL n,i,j,k,m,t;
LL val[1000005],invval[1000005];
LL ans[1000005],p2[1000005],invp2[1000005];
const LL mod=1e9+7;
LL qpow(LL x,LL y){
    LL sum=1;
    while(y){
        if(y&1) sum*=x,sum%=mod;
        x*=x,x%=mod;
        y>>=1;
    }
    return sum;
}
LL inv(LL x){
    return qpow(x,mod-2);
}
LL C(LL x,LL y){
    return val[x]*invval[y]%mod*invval[x-y]%mod;
}
int main(){
    val[0]=1,invval[0]=1,p2[0]=1,invp2[0]=1;
    for(i=1;i<=100000;i++)
      val[i]=val[i-1]*i%mod,invval[i]=inv(val[i]),p2[i]=p2[i-1]*2%mod,invp2[i]=inv(p2[i]);
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&n,&m);
        if(n<m){
            printf("0\n");
            continue;
        }
        if(n==m){
            printf("%lld\n",val[n-1]*inv(2)%mod);
            continue;
        }
        if(m==0){
            printf("1\n");
            continue;
        }
        LL num=n-m,ans=0;
        for(i=1;i<=num;i++){
            LL tmp=num-i;
            ans+=val[n]*C(n-tmp-i-1,i-1)%mod*C(num,i)%mod*invp2[i]%mod*invval[num]%mod,ans%=mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}