专栏文章

题解：CF715E Complete the Permutations

cchenbs
CF715E题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mingla0c
此快照首次捕获于
2025/12/02 02:04
3 个月前
此快照最后确认于
2025/12/02 02:04
3 个月前
查看原文
图论建模，看成有 nn 个点，每个点有两个权值 pip_i 和 qiq_i，对于点 ii、jj，若 pi=qj≠0p_i=q_j \neq 0，则在 ii 和 jj 之间连边权位 pip_i 的边。最少操作数就是 nn 减去环的数量（自环也算）。这样就得到了一些环、链（孤立的点可以看成长度为 11 的链）。
对于现有的环，直接去掉，最后输出答案的时候再算进去就行了（记住这句话，后面要用）。
对于链，根据起点 ii，终点 jj 进行分类，可以分成四类。
  • I 类：qi>0q_i > 0，pj>0p_j > 0，换言之，这条链的开头和结尾接的边都有边权限制。
  • II 类：qi>0q_i > 0，pi=0p_i = 0，换言之，这条链只有开头接的边有边权限制。
  • III 类：qi=0q_i = 0，pi>0p_i > 0，换言之，这条链只有结尾接的边有边权限制。
  • IV 类：qi=0q_i = 0，pi=0p_i = 0，换言之，这条链可以随便接。
对于一个 I 类链，可以将 qiq_i 和 pjp_j 缩成一个点（并查集维护）。我们可以这样理解：先把其他链都排好了之后，再把 I 类链插入就行了，反正它的首尾能连的都是固定的，不影响答案。
对于一个 III 类链 aa 和 II 类链 bb，若 pa=qbp_a = q_b 也可以缩成一个 IV 类链。
再将环分成三类：只有 II 类链、只有 III 类链、有 IV 链。

只有 II 类链的环

记 c2c_2、c3c_3、c4c_4 为 II、III、IV 类链的个数，fif_i 为 II 类点恰好形成 ii 个环的方案数，则：
fi=∑j=ic2(c2j)[ji](c2−j+c4−1)!(c4−1)!f_i = \sum_{j=i}^{c_2} {c_2 \choose j} {j \brack i} \frac{(c_2 - j + c_4 - 1)!}{(c_4 - 1)!}
这条式子的组合意义是：先选出 jj 条链，放入 ii 个圆排列中，剩下的 c2−jc_2-j 条链，可以选择合并到另一条 II 类链或者 IV 类链中。
特别地，若 c4=0c_4=0，则会出现负数的阶乘无法计算，此时的答案为 fi=[c2i]f_i = {c_2 \brack i}。

只有 III 类链的环

设 gig_i 为 III 类点恰好形成 ii 个环的方案数，计算和 ff 同理，把上面的 c2c_2 换成 c3c_3 就行了。

有 IV 链的环

设 hih_i 为恰好形成 ii 个环，环中都包含 IV 类链的方案数，则：
hi=[c4i]c4!h_i = {c_4 \brack i} c_4!
这个式子看起来不是很对，并没有考虑 II 类链和 III 类链。其实是没有问题的，因为在上面已经把这些链合并到 IV 链中了。

输出答案

将三个函数卷积起来，最少操作数就是 (f∗g∗h)(n−i−cnt)(f*g*h)(n-i - \text{cnt})，cnt\text{cnt} 为一开始现有的环数。
CPP
#include<bits/stdc++.h>
using namespace std;
const int M=998244353;
int n,a[2005],b[2005],to[2005],in[2005];
int fa[2005];
int find(int x) {
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int x, int y) {
	x=find(x), y=find(y), fa[x]=y;
}
int pow(int x, int y) {
	int res=1;
	while(y) {
		if(y&1) res=1ll*res*x%M;
		x=1ll*x*x%M;
		y>>=1;
	}
	return res;
}
int vis[2005],cnt,c2,c3,c4,jc[2005],jcinv[2005],s[2005][2005];
void init() {
	jc[0]=1;
	for(int i=1; i<=2000; i++) jc[i]=1ll*jc[i-1]*i%M;
	jcinv[2000]=pow(jc[2000],M-2);
	for(int i=2000; i>=1; i--) jcinv[i-1]=1ll*jcinv[i]*i%M;
	s[0][0]=1;
	for(int i=1; i<=2000; i++)
		for(int j=1; j<=i; j++)
			s[i][j]=(s[i-1][j-1]+1ll*s[i-1][j]*(i-1))%M;
}
int C(int x, int y) {
	return 1ll*jc[x]*jcinv[x-y]%M*jcinv[y]%M;
}
int A(int x, int y) {
	return 1ll*jc[x]*jcinv[x-y]%M;
}
void init2() {
	// 缩点
	for(int i=1; i<=n; i++) fa[i]=i;
	for(int i=1; i<=n; i++) {
		if(a[i] && b[i]) {
			int x=find(a[i]), y=find(b[i]);
			if(x!=y) fa[x]=y;
			else cnt++;
		}
	}
	for(int i=1; i<=n; i++) a[i]=find(a[i]), b[i]=find(b[i]);


	for(int i=1; i<=n; i++) {
		if(a[i] && !b[i]) c2++, vis[a[i]]++; // II 类边
		if(!a[i] && b[i]) c3++, vis[b[i]]++; // III 类边
		if(!a[i] && !b[i]) c4++; // IV 类边
	}
	for(int i=1; i<=n; i++)
		if(vis[i]>=2)
			c2--,c3--,c4++;
}
int f[2005],g[2005],h[2005],fg[2005],fgh[2005];
int main() {
	init();
	cin>>n;
	for(int i=1; i<=n; i++) cin>>a[i];
	for(int i=1; i<=n; i++) cin>>b[i];
	init2();
//	printf("%d %d %d %d\n",cnt,c2,c3,c4);

	if(c4==0) {
		for(int i=0; i<=c2; i++) f[i]=s[c2][i];
		for(int i=0; i<=c3; i++) g[i]=s[c3][i];
	} else {
		for(int i=0; i<=c2; i++)
			for(int j=i; j<=c2; j++)
				f[i]=(f[i]+1ll*C(c2,j)*s[j][i]%M*A(c4+c2-j-1,c2-j))%M;
		for(int i=0; i<=c3; i++)
			for(int j=i; j<=c3; j++)
				g[i]=(g[i]+1ll*C(c3,j)*s[j][i]%M*A(c4+c3-j-1,c3-j))%M;
	}
	for(int i=0; i<=c4; i++) h[i]=1ll*s[c4][i]*jc[c4]%M;

//	for(int i=0; i<=c2; i++) cout<<f[i]<<' ';
//	cout<<'\n';
//	for(int i=0; i<=c3; i++) cout<<g[i]<<' ';
//	cout<<'\n';
//	for(int i=0; i<=c4; i++) cout<<h[i]<<' ';
//	cout<<'\n';

	for(int i=0; i<=c2; i++)
		for(int j=0; j<=c3; j++)
			fg[i+j]=(fg[i+j]+1ll*f[i]*g[j])%M;
	for(int i=0; i<=c2+c3; i++)
		for(int j=0; j<=c4; j++)
			fgh[i+j]=(fgh[i+j]+1ll*fg[i]*h[j])%M;
	for(int i=0; i<n; i++) {
		if(n-i-cnt>=0) cout<<fgh[n-i-cnt]<<' ';
		else cout<<0<<' ';
	}
	return 0;
}

评论

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

正在加载评论...