题解：P9896 [ICPC 2018 Qingdao R] Sub-cycle Graph
PJM2008
·
·
题解
在 @aSunnyDay 大佬的帮助下终于调出来了，感觉此题推导公式的过程比较有趣，遂作文以记之。
平凡情形：m>n 时答案为 0，m=n 时为 \frac{(𝑛−1)!}{2}。
当 m<n 时，观察到 n 点 m 边的“半环”图为 n-m 条不交的链之并（链可以为孤立点）。
我们考虑将链重组为一条长度为 n 的链，对重组的方法数进行算两次。
一方面，对于每条 n 个顶点的链，有多少种方法将其拆分为 n-m 条链？
不妨设链为 1-2-...-n。 设拆分的 n-m 条链分别为 [1,r_1],[r_1+1,r_2],...,[r_{n-m-1}+1,n]。有 1≤𝑟_1<𝑟_2<...<𝑟_{𝑛−𝑚−1}≤𝑛−1。故方法数为 \tbinom{n-1}{n-m-1}=\tbinom{n-1}{m}。
另一方面，对于 n-m 条（短）链，有多少种方法拼装为一条（长）链？
故拼装方法数为 $\frac{(n-m)! \cdot 2^{n-m}}{2}=(n-m)! \cdot 2^{n-m-1}$？？
错误之处在于若某条短链为孤立点，将其翻转后所得长链相同，计算出现重复。
解决方法：枚举孤立点个数，对其余点构成的短链（长度至少为 $1$）重组为长链并进行算两次。
设孤立点个数为 $n-k$，选出方法数为$\tbinom{n}{k}$。
算两次计算其余 $k$ 点划分为 $k-m$ 条链，每条链长度均至少为 $1$ 的方法数。
一方面，对于每条 $k$ 个顶点的链，有多少种方法将其拆分为 $k-m$ 条长度（边数）均至少为 $1$ 的链？类似地，不妨设链为 $1-2-...-k$。设拆分的 $k-m$ 条链分别为 $[1,r_1],[r_1+1,r_2],...,[r_{k-m-1}+1,k]$。有 $1<𝑟_1<𝑟_2<...<𝑟_{k−𝑚−1}<𝑛−1$，且 $∀𝑖=1,2,...,𝑘−𝑚−2,𝑟_{𝑖+1}−𝑟_𝑖>1$。
作变换 $𝑟_𝑖→𝑟_𝑖^’=𝑟_𝑖−𝑖$。有 $1≤𝑟_1^’<𝑟_2^’<...<𝑟_{𝑘−𝑚−1}^’≤𝑚−1$。故方法数为 $\tbinom{m-1}{k-m-1}=\tbinom{m-1}{2m-k}$ 为定值。
另一方面，对于 $k-m$ 条长度至少为 $1$ 的短链，有多少种方法将其拼装为一条 $k$ 点长链？类似地，$k-m$ 条链顺序可任意排列，有 $(k-m)!$ 种；每条短链可进行翻转，有 $2k-m$ 种；每条长链被计算恰两次（其和翻转各被计算两次）。故拼装方法数为 $\frac{(k-m)! \cdot 2^{k-m}}{2}=(k-m)! \cdot 2^{k-m-1}$。
由算两次原理知 $k$ 个点的由 $k-m$ 条长度均至少为 $1$ 的不交链构成的图的个数为
$\frac{\frac{1}{2}k! \cdot \tbinom{m-1}{k-m-1}}{(k-m)! \cdot 2^{k-m-1}}=\frac{(m-1)! \cdot k!}{(k-m-1)! \cdot (k-m)! \cdot (2m-k)! \cdot 2^{k-m-1}}$。
易知 $k$ 的取值范围为 $𝑚+1≤𝑘≤\min(2𝑚,𝑛)$。
故最终答案为 $\sum_{k=m+1}^{\min(2m,n)} \frac{(m-1)! \cdot k!}{(k-m-1)! \cdot (k-m)! \cdot (2m-k)! \cdot 2^{k-m-1}}\cdot\tbinom{n}{k}=\sum_{k=m+1}^{\min(2m,n)} \frac{(m-1)! \cdot n!}{(k-m-1)! \cdot (k-m)! \cdot (2m-k)! \cdot (n-k)! \cdot 2^{k-m-1}}$。
预处理 $0,1,...,10^5$ 的阶乘及乘法逆元即可。
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
ll t,m,n,inv[200009],f[200009],rf[200009],ans,p;
int main(){
f[0]=rf[0]=inv[1]=f[1]=rf[1]=1;
for(ll i=2;i<=200000;i++){
inv[i]=mod-mod/i*inv[mod%i]%mod;
f[i]=f[i-1]*i%mod;rf[i]=rf[i-1]*inv[i]%mod;
}
cin>>t;
while(t--){
cin>>n>>m;
if(m>n){cout<<0<<endl;continue;}
if(m==n){cout<<f[n-1]*(mod+1)/2%mod<<endl;continue;}
if(m==0){cout<<1<<endl;continue;}
ans=0;p=1;
for(ll k=m+1;k<=min(2*m,n);k++){
p*=(mod+1)/2;p%=mod;ans+=f[m-1]*f[n]%mod*rf[k-m-1]%mod*rf[k-m]%mod*rf[2*m-k]%mod*rf[n-k]%mod*p%mod;
ans%=mod;
}
cout<<ans<<endl;
}
return 0;
}
```