专栏文章

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

PPJM2008
P9896题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mioohwec
此快照首次捕获于
2025/12/02 22:33
3 个月前
此快照最后确认于
2025/12/02 22:33
3 个月前
查看原文
在 @aSunnyDay 大佬的帮助下终于调出来了，感觉此题推导公式的过程比较有趣，遂作文以记之。
平凡情形：m>nm>n 时答案为 00，m=nm=n 时为 (𝑛−1)!2\frac{(𝑛−1)!}{2}。
当 m<nm<n 时，观察到 nn 点 mm 边的“半环”图为 n−mn-m 条不交的链之并（链可以为孤立点）。
我们考虑将链重组为一条长度为 nn 的链，对重组的方法数进行算两次。
一方面，对于每条 nn 个顶点的链，有多少种方法将其拆分为 n−mn-m 条链？
不妨设链为 1−2−...−n1-2-...-n。 设拆分的 n−mn-m 条链分别为 [1,r1],[r1+1,r2],...,[rn−m−1+1,n][1,r_1],[r_1+1,r_2],...,[r_{n-m-1}+1,n]。有 1≤𝑟1<𝑟2<...<𝑟𝑛−𝑚−1≤𝑛−11≤𝑟_1<𝑟_2<...<𝑟_{𝑛−𝑚−1}≤𝑛−1。故方法数为 (n−1n−m−1)=(n−1m)\tbinom{n-1}{n-m-1}=\tbinom{n-1}{m}。
另一方面，对于 n−mn-m 条（短）链，有多少种方法拼装为一条（长）链？
n−mn-m 条链顺序可任意排列，有 (n−m)!(n-m)! 种；每条短链可进行翻转，有 2n−m2n-m 种；每条长链被计算两次（其和翻转各被计算两次）。
故拼装方法数为 (n−m)!⋅2n−m2=(n−m)!⋅2n−m−1\frac{(n-m)! \cdot 2^{n-m}}{2}=(n-m)! \cdot 2^{n-m-1}？？
错误之处在于若某条短链为孤立点，将其翻转后所得长链相同，计算出现重复。
解决方法：枚举孤立点个数，对其余点构成的短链（长度至少为 11）重组为长链并进行算两次。
设孤立点个数为 n−kn-k，选出方法数为(nk)\tbinom{n}{k}。 算两次计算其余 kk 点划分为 k−mk-m 条链，每条链长度均至少为 11 的方法数。
一方面，对于每条 kk 个顶点的链，有多少种方法将其拆分为 k−mk-m 条长度（边数）均至少为 11 的链？类似地，不妨设链为 1−2−...−k1-2-...-k。设拆分的 k−mk-m 条链分别为 [1,r1],[r1+1,r2],...,[rk−m−1+1,k][1,r_1],[r_1+1,r_2],...,[r_{k-m-1}+1,k]。有 1<𝑟1<𝑟2<...<𝑟k−𝑚−1<𝑛−11<𝑟_1<𝑟_2<...<𝑟_{k−𝑚−1}<𝑛−1，且 ∀𝑖=1,2,...,𝑘−𝑚−2,𝑟𝑖+1−𝑟𝑖>1∀𝑖=1,2,...,𝑘−𝑚−2,𝑟_{𝑖+1}−𝑟_𝑖>1。
作变换 𝑟𝑖→𝑟𝑖’=𝑟𝑖−𝑖𝑟_𝑖→𝑟_𝑖^’=𝑟_𝑖−𝑖。有 1≤𝑟1’<𝑟2’<...<𝑟𝑘−𝑚−1’≤𝑚−11≤𝑟_1^’<𝑟_2^’<...<𝑟_{𝑘−𝑚−1}^’≤𝑚−1。故方法数为 (m−1k−m−1)=(m−12m−k)\tbinom{m-1}{k-m-1}=\tbinom{m-1}{2m-k} 为定值。
另一方面，对于 k−mk-m 条长度至少为 11 的短链，有多少种方法将其拼装为一条 kk 点长链？类似地，k−mk-m 条链顺序可任意排列，有 (k−m)!(k-m)! 种；每条短链可进行翻转，有 2k−m2k-m 种；每条长链被计算恰两次（其和翻转各被计算两次）。故拼装方法数为 (k−m)!⋅2k−m2=(k−m)!⋅2k−m−1\frac{(k-m)! \cdot 2^{k-m}}{2}=(k-m)! \cdot 2^{k-m-1}。
由算两次原理知 kk 个点的由 k−mk-m 条长度均至少为 11 的不交链构成的图的个数为
12k!⋅(m−1k−m−1)(k−m)!⋅2k−m−1=(m−1)!⋅k!(k−m−1)!⋅(k−m)!⋅(2m−k)!⋅2k−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}}。
易知 kk 的取值范围为 𝑚+1≤𝑘≤min⁡(2𝑚,𝑛)𝑚+1≤𝑘≤\min(2𝑚,𝑛)。
故最终答案为 ∑k=m+1min⁡(2m,n)(m−1)!⋅k!(k−m−1)!⋅(k−m)!⋅(2m−k)!⋅2k−m−1⋅(nk)=∑k=m+1min⁡(2m,n)(m−1)!⋅n!(k−m−1)!⋅(k−m)!⋅(2m−k)!⋅(n−k)!⋅2k−m−1\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,...,1050,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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...