专栏文章

题解：P11802 【MX-X9-T6】『GROI-R3』Graph

ggeorge0929
P11802题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@min9vsa3
此快照首次捕获于
2025/12/01 22:56
3 个月前
此快照最后确认于
2025/12/01 22:56
3 个月前
查看原文
模拟赛赛时认为 gcd⁡\gcd 必须等于 11，爆零了/ll。
看来考试时要把发现结论的依据写一写（周期结论）。
首先由题意，GG 上任意一个点能走到他自己，因此 GG 是若干环的并。
得到 gcd⁡=1\gcd=1 的错误结论是由于周期结论的直觉，让我们仔细想想这个结论能带给我们什么信息。
对于 GG 上一个长为 lenlen 的环，我们从一个点出发，每次走 kk 步，能得到 gcd⁡(k,len)\gcd(k,len) 个长为 lengcd⁡(k,len)\frac{len}{\gcd(k,len)} 的环。
因此，我们还可以选择把若干个相同长度的环在 GG 中拼在一起。
具体地，用若干个长度为 ii 的环拼成长为 i×ti\times t 的大环，则有：
itgcd⁡(k,len)=it=gcd⁡(k,it)gcd⁡(kt,i)=1\frac{it}{\gcd(k,len)}=i \\ t=\gcd(k,it) \\ \gcd(\frac{k}{t},i)=1
因此，设 cntloopicntloop_i 表示环长为 ii 的环数，找到最小的 tt 使得 gcd⁡(kt,i)=1\gcd(\frac{k}{t},i)=1，则 t∣cntloopit|cntloop_i。这个条件是充要的。
考虑计数 DP。
按链 id DP要记录每个环长的 cntcnt，不可接受。
因此考虑按需要记录的值 DP，这样的好处是我们可以在进行 i→i+1i\to i+1 的转移时顺便判断 ii 是否合法。
令 fi,j,kf_{i,j,k} 表示当前处理长度 ii，长度为 ii 的链有 jj 个，有 kk 个剩余孤点（记录长度 ≤j\leq j 的链个数不容易保证不重不漏，因此选择 == 的定义）。
有一个技巧：我们可以把没有闭合的链各加上一个孤点，以保证 ii 增加时链长 =i=i 的定义。
然而 ww 个孤点在环上的贡献为 w!w!，这要求了我们不能实时计算这个贡献，只能在最后计算。
具体地，我们在转移时不区分孤点，最后乘上孤点个数的阶乘，根据组合意义，这个方法在不存在全是孤点组成的环时正确。
在孤点成环时，我们发现是阶乘和圆排列的区别。
具体地，对于一个 xx，设长为 xx 的全孤点环为 yy 个，则我们多算了 xyy!x^y y! 倍，因为我们要：
  • 除掉圆排列的循环。
  • 当孤点都相同时，这些环没有顺序之分，除掉【最后乘上孤点个数的阶乘】对这些环顺序的错误贡献。
我们尝试用分步的思想来推导 DP 转移方程。
  • 加入原图上的长为 ii 的链，这一步是模拟题意。fi,j,k→fi,j+cntlinki,k′f_{i,j,k}\to f'_{i,j+cntlink_i,k}（cntlinkicntlink_i 指原图上长为 ii 的链个数）。
  • 求出最小的 tt 使得 gcd⁡(kt,i)=1\gcd(\frac{k}{t},i)=1，加入一些环，满足长为 ii 的总环数是 tt 的倍数，形成环有如下两种方式：
    • 选出若干孤点构成环。
    • 将已有的链闭合形成环。
    即枚举 c,lc,l，fi,j,k′(jl)icc!→fi,j−l,k−ic′′\frac{f'_{i,j,k}\binom{j}{l}}{i^c c!}\to f''_{i,j-l,k-ic}，转移条件是 (cntloopi+l+c) mod t=0(cntloop_i+l+c)\bmod t=0。
  • 把没有闭合的链加上一个孤点，fi,j,k′′→fi+1,j,k−jf''_{i,j,k}\to f_{i+1,j,k-j}。
记孤点个数为 cnt1cnt1，答案即为 fn+1,0,0×cnt1!f_{n+1,0,0}\times cnt1!。
分析复杂度，有 ij≤n,ic≤k≤n,l≤jij\leq n,ic\leq k\leq n,l\leq j。
ij,ic,ilij,ic,il 各贡献 ∑ni\sum \frac{n}{i}，kk 贡献 nn。
总复杂度 O(n∑n3i3)=O(n4∑1i3)=O(n4)O(n\sum\frac{n^3}{i^3})=O(n^4\sum\frac{1}{i^3})=O(n^4)。
在推导时，我们发现没有转移条件时完全可以把【选出若干孤点构成环】和【将已有的链闭合形成环】分步转移做到 O(n3)O(n^3)。
把条件改成 −cntloopi−l=c(modt)-cntloop_i-l=c\pmod t 仍然可以分步转移，枚举 cntloopi+l mod tcntloop_i+l\bmod t 的值做若干遍即可。
O(n3)O(n^3) 卡卡就过 n=1000n=1000 了（逃。
CPP
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const ll mod=998244353;
ll ksm(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b/=2;
	}
	return res;
}
int n,k,a[1005],vis[1005],in[1005];
int C[1005][1005],fac[1005];
int f[2][1005][1005];
int f1[1005][1005];
int f2[1005][1005];
int getmint(int i){
	int ki=k;
	for(int j=1;j*j<=k;j++){
		if(j!=1&&i%j==0){
			while(ki%j==0) ki/=j;
		}
		if(k/j!=1&&i%(k/j)==0){
			while(ki%(k/j)==0) ki/=(k/j);
		}
	}
	return k/ki;
}
int cntloop[1005],cntlink[1005],cnt1;
void upd(int &x,int y){
	x=(x+y)%mod;
}
int inv[1005][1005];
int f1x[1005][1005];
void solve(){
	cin>>n>>k;
	for(int i=1;i<=n;i++) in[i]=vis[i]=cntloop[i]=cntlink[i]=0;
	for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) f[0][i][j]=f[1][i][j]=f1[i][j]=f1x[i][j]=f2[i][j]=0;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) if(a[i]!=-1) in[a[i]]=1;
	cnt1=0;
	for(int i=1;i<=n;i++){
		if(vis[i]||in[i]) continue;
		int now=i,sz=1;
		vis[now]=1;
		while(1){
			if(a[now]==-1) break;
			now=a[now];
			vis[now]=1;
			sz++;
		}
		if(sz==1&&a[i]==-1){
			cnt1++;
			continue;
		}
		cntlink[sz]++;
	}
	for(int i=1;i<=n;i++){
		if(vis[i]) continue;
		int now=i,sz=1;
		vis[now]=1;
		while(1){
			if(a[now]==-1) break;
			now=a[now];
			if(vis[now]){
				break;
			}
			vis[now]=1;
			sz++;
		}
		cntloop[sz]++;
	}
	f[1][0][cnt1]=1;
	for(int i=1;i<=n;i++){
		int t=getmint(i);
		int now=i&1;
		int nxt=1-now;
		for(int j=0;i*j<=n;j++) for(int k=0;k<=cnt1;k++){
			f[nxt][j][k]=0;
			f1[j][k]=f1x[j][k]=f2[j][k]=0;
		}
		for(int j=0;i*j<=n&&j+cntlink[i]<=n;j++){
			for(int k=0;k<=cnt1;k++){
				upd(f1[j+cntlink[i]][k],f[now][j][k]);
			}
		}
		for(int mdt=0;mdt<t;mdt++){
			if(i*mdt>cnt1) continue;
			for(int j=0;i*j<=n;j++){
				for(int k=i*mdt;k<=cnt1;k++){
					if(!f1[j][k]) continue;
					for(int c=mdt;i*c<=k;c+=t){
						upd(f1x[j][k-i*c],1ll*f1[j][k]*inv[i][c]%mod);
					}
				}
			}
			for(int j=0;i*j<=n;j++){
				for(int k=0;k<=cnt1-i*mdt;k++){
					if(!f1x[j][k]) continue;
					for(int l=((t-cntloop[i]-mdt)%t+t)%t;l<=j;l+=t){
						upd(f2[j-l][k],1ll*f1x[j][k]%mod*C[j][l]%mod);
					}
					f1x[j][k]=0;
				}
			}
		}
		for(int j=0;i*j<=n;j++){
			for(int k=j;k<=cnt1;k++){
				upd(f[nxt][j][k-j],f2[j][k]);
			}
		}
	}
	cout<<1ll*f[(n+1)&1][0][0]*fac[cnt1]%mod<<"\n";
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	C[0][0]=1;
	fac[0]=1;
	for(int i=1;i<=1000;i++){
		fac[i]=1ll*fac[i-1]*i%mod;
		C[i][0]=C[i][i]=1;
		for(int j=1;j<i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod; 
	}
	for(int i=0;i<=1000;i++){
		for(int j=0;j<=1000;j++){
			inv[i][j]=ksm(1ll*ksm(i,j)*fac[j]%mod,mod-2);
		}
	}
	solve();
}

评论

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

正在加载评论...