专栏文章

题解：AT_agc065_f [AGC065F] Always Perfect

llittlez_meow
AT_agc065_f题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miqi3ql2
此快照首次捕获于
2025/12/04 05:10
3 个月前
此快照最后确认于
2025/12/04 05:10
3 个月前
查看原文
过 uu 的路径与 v3v_3 连通；然后断开 (u,v1)(u,v_1)，这种条件非常复杂的题目，先研究如何判定。
对一个合法的图的每个点双考虑。设 SuS_u 表示 uu 和点双外部挂在 uu 上的点的个数。
容易发现，对于所有点双中的点 uu，我们有 SuS_u 的奇偶性相同。否则，我们必然可以找到两个点 u,vu,v，其中 2∣Su,2∤Sv2|S_u,2\nmid S_v，满足 u,vu,v 相邻。此时 uu 已经和外面某个挂的点匹配了，vv 没有。让生成树里保留边 (u,v)(u,v)，vv 就永远匹配不了。
如果所有 SuS_u 都是偶数，所有点都和外面挂着的某个点匹配，没有限制。
否则，所有点都在点双内匹配。首先点数是偶数，这是容易的。然后每个点度数 ≤2\le2，下面使用反证证明。假设 uu 连了 v1,v2,v3v_1,v_2,v_3，考虑这样两棵生成树：连 (u,v1)(u,v_1)，v1,v2v_1,v_2 用不经连 (u,v2)(u,v_2)。如果这两个都有完美匹配，代表以 v3v_3 为根时 v1,v2v_1,v_2 都在自己的子树内部匹配。于是断开 v1,v2v_1,v_2 连向父亲的边，连 (u,v1),(u,v2),(u,v3)(u,v_1),(u,v_2),(u,v_3)，这个生成树没法把 u,v1,v2u,v_1,v_2 都匹配掉，矛盾。
综上所述，如果 SuS_u 都是奇数，这个点双一定是偶环或者两点一边。称这两个结构是一个新点。
根据上面的讨论，可以使用如下方式不重不漏构造出所有合法的图：初始时是若干新点；每次选择 ≥2\ge2 个连通块，每个连通块中选出一个点，连成点双；连通时停止。
这个图在新点的意义下是一个有若干点双的有标号连通图。
终于可以开始计数了。先计算 nn 个点 mm 个点双的连通图数量 f(n,m)f(n,m) 和 nn 个点连通图数量 g(n)g(n)。注意区分 n,Nn,N。
先是 g(n)g(n) 的转移。可以写暴力多项式求 ln⁡\ln，也可以容斥。具体地，枚举包含节点 11 的极大连通块，剩下的随意连边，有：
g(n)=2(n2)−∑i=1n−1(n−1i−1)2(n−i2)gig(n)=2^{\binom{n}2}-\sum\limits_{i=1}^{n-1}\dbinom{n-1}{i-1}2^{\binom{n-i}2}g_i
其中 ii 是极大连通块大小，(n−1i−1)\dbinom{n-1}{i-1} 是给连通块里的点分配标号，22 的幂是内部随意连边的方案数。
f(n,1)f(n,1) 也可以容斥出来，即：
f(n,1)=g(n)−∑i=2n−1f(n,i)f(n,1)=g(n)-\sum\limits_{i=2}^{n-1}f(n,i)
接下来是 f(n,m)f(n,m)，其中 m≥2m\ge 2。对圆方树计数，钦定 11 是根，其中 nn 个圆点 mm 个方点，设第 ii 个方点的儿子数是 did_i。把方点和其儿子视为一个整体，连成一棵树。如果现不考虑方点的存在，就是典中典 m+1m+1 个大小分别为 1,d1,⋯ ,dm1,d_1,\cdots,d_m 的连通块加边连成树，Prüfer 序列得到方案数是 nm−1∏i=1mdin^{m-1}\prod_{i=1}^m d_i。再把方点考虑进来，最后都是方点连向父亲，每个连通块里是哪个点连的都不重要，每种方案被重复算了 ∏i=1mdi\prod\limits_{i=1}^m d_i，除掉之后就是 nm−1n^{m-1}。乘上方点内部的方案数和分配标号的方案数，除掉方点无标号导致多算的系数，有：f(n,m)=nm−1m!∑d1+⋯+dm=n−1(n−1d1,⋯ ,dm)∏i=1mf(di+1,1)=nm−1(n−1)!m!∑d1+⋯+dm=n−1∏i=1mf(di+1,1)di!f(n,m)=\dfrac{n^{m-1}}{m!}\sum\limits_{d_1+\cdots+d_m=n-1}\dbinom{n-1}{d_1,\cdots,d_m}\prod\limits_{i=1}^m f(d_i+1,1)=\dfrac{n^{m-1}(n-1)!}{m!}\sum\limits_{d_1+\cdots+d_m=n-1}\prod\limits_{i=1}^m\dfrac{f(d_i+1,1)}{d_i!}。
后面是典型的背包卷积，于是设 h(n,m)=∑d1+⋯+dm=n−1∏i=1mf(di+1,1)di!h(n,m)=\sum\limits_{d_1+\cdots+d_m=n-1}\prod\limits_{i=1}^m\dfrac{f(d_i+1,1)}{d_i!}。注意到 N≥2N\ge 2，故方点都有儿子，即 di≥1d_i\ge 1。有转移 h(n,m)=∑dm=1n−1h(n−dm,m−1)f(dm+1,1)dm!h(n,m)=\sum\limits_{d_m=1}^{n-1}\dfrac{h(n-d_m,m-1)f(d_m+1,1)}{d_m!}，整理下：
h(n,m)=∑dm=1n−1h(n−dm,m−1)h(dm,1）h(n,m)=\sum\limits_{d_m=1}^{n-1} h(n-d_m,m-1)h(d_m,1）
代回 ff 的转移：
f(n,m)=nm−1(n−1)!h(n,m)m!f(n,m)=\dfrac{n^{m-1}(n-1)!h(n,m)}{m!}
最后统计答案。枚举初始放入的新点个数 xx，连成的点双个数 yy，第 ii 个新点的大小 sis_i，然后式子和前面计算 ff 的差不多，就是总点数变成 NN 了。具体地，此时的贡献为 Ny−1(x−1)!h(x,y)∏i=1xsiy!\dfrac{N^{y-1}(x-1)!h(x,y)\prod_{i=1}^x s_i}{y!}。
然后再做一个 ∑i=1xsi=N\sum\limits_{i=1}^x s_i=N 的背包就可以得到结果了。具体地，设 H(n,s)H(n,s) 表示当 x=n,∑i=1xsi=sx=n,\sum\limits_{i=1}^x s_i=s 的 ∏i=1xsi\prod_{i=1}^x s_i，则转移为：
H(n,s)=∑sn=2s[2∣sn]snH(n−1,s−sn)(s−1sn−1)G(sn)H(n,s)=\sum\limits_{s_n=2}^{s}[2|s_n]s_n H(n-1,s-s_n)\dbinom{s-1}{s_n-1}G(s_n)
初值 H(0,0)=1H(0,0)=1。
其中 [2∣sn][2|s_n] 是因为新点大小一定是偶数（偶环或两个点）。G(x)G(x) 是 xx 个点的新点方案数，x=2x=2 是 11，否则是 (x−1)!2\dfrac{(x-1)!}2。组合数是分配标号。
最后答案为：
G(N)+∑x=1N∑y=1x−1Ny−1(x−1)!h(x,y)H(x,N)y!G(N)+\sum\limits_{x=1}^N\sum\limits_{y=1}^{x-1}\dfrac{N^{y-1}(x-1)!h(x,y)H(x,N)}{y!}
后半部分是 ≥2\ge 2 个新点，前面是一个新点。
看起来或许可以用神秘的在线或半在线卷积做到 O∼(n2)\overset{\sim}{O}(n^2)，不过暴力做时间复杂度 O(n3)O(n^3) 已经足够了。
一定一定想好转移顺序再写。

代码

CPP
#include<bits/stdc++.h>
#define File(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define ll long long
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define R(i,a,b) for(int i(a),i##i##end(b);i>=i##i##end;--i)
using namespace std;
const int MAXN=505;
int N,MOD;
inline ll qpow(ll base,int expo){
	ll res(1);
	while(expo){
		(expo&1)&&(res=res*base%MOD);
		base=base*base%MOD,expo>>=1;
	}
	return res;
}
ll fact[MAXN],inv[MAXN];
inline ll C(int x,int y){
	return x>=y?fact[x]*inv[y]%MOD*inv[x-y]%MOD:0;
}
inline ll G(int x){
	return x==2?1:fact[x-1]*inv[2]%MOD;
}
ll f[MAXN][MAXN],g[MAXN],h[MAXN][MAXN],H[MAXN][MAXN];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>N>>MOD;
	fact[0]=1;
	F(i,1,N) fact[i]=fact[i-1]*i%MOD;
	inv[N]=qpow(fact[N],MOD-2);
	R(i,N,1) inv[i-1]=inv[i]*i%MOD;
	g[1]=1;
	F(n,2,N){
		g[n]=qpow(2,n*(n-1)/2);
		F(i,1,n-1) g[n]=(g[n]-C(n-1,i-1)*qpow(2,(n-i)*(n-i-1)/2)%MOD*g[i]%MOD+MOD)%MOD;
	}
	F(n,2,N){
		F(m,2,n-1) f[n][m]=qpow(n,m-1)*fact[n-1]%MOD*h[n][m]%MOD*inv[m]%MOD;
		f[n][1]=g[n];
		F(i,2,n) (f[n][1]-=f[n][i])<0&&(f[n][1]+=MOD);
		h[n][1]=f[n][1]*inv[n-1]%MOD;
		F(m,2,N) F(dm,1,n-1) h[n+1][m]=(h[n+1][m]+h[n+1-dm][m-1]*h[dm+1][1])%MOD;
	}
	H[0][0]=1;
	F(n,1,N) F(s,1,N) if(!(s&1)) F(sn,2,s) if(!(sn&1)) H[n][s]=(H[n][s]+sn*H[n-1][s-sn]%MOD*C(s-1,sn-1)%MOD*G(sn))%MOD;
	ll ans=G(N);
	F(x,1,N) F(y,1,x-1) ans=(ans+qpow(N,y-1)*fact[x-1]%MOD*h[x][y]%MOD*H[x][N]%MOD*inv[y])%MOD;
	cout<<ans;
	return 0;
}

评论

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

正在加载评论...