题解：AT_agc065_f [AGC065F] Always Perfect
littlez_meow
·
·
题解
过 u 的路径与 v_3 连通；然后断开 (u,v_1)，这种条件非常复杂的题目，先研究如何判定。
对一个合法的图的每个点双考虑。设 S_u 表示 u 和点双外部挂在 u 上的点的个数。
容易发现，对于所有点双中的点 u，我们有 S_u 的奇偶性相同。否则，我们必然可以找到两个点 u,v，其中 2|S_u,2\nmid S_v，满足 u,v 相邻。此时 u 已经和外面某个挂的点匹配了，v 没有。让生成树里保留边 (u,v)，v 就永远匹配不了。
如果所有 S_u 都是偶数，所有点都和外面挂着的某个点匹配，没有限制。
否则，所有点都在点双内匹配。首先点数是偶数，这是容易的。然后每个点度数 \le2，下面使用反证证明。假设 u 连了 v_1,v_2,v_3，考虑这样两棵生成树：连 (u,v_1)，v_1,v_2 用不经连 (u,v_2)。如果这两个都有完美匹配，代表以 v_3 为根时 v_1,v_2 都在自己的子树内部匹配。于是断开 v_1,v_2 连向父亲的边，连 (u,v_1),(u,v_2),(u,v_3)，这个生成树没法把 u,v_1,v_2 都匹配掉，矛盾。
综上所述，如果 S_u 都是奇数，这个点双一定是偶环或者两点一边。称这两个结构是一个新点。
根据上面的讨论，可以使用如下方式不重不漏构造出所有合法的图：初始时是若干新点；每次选择 \ge2 个连通块，每个连通块中选出一个点，连成点双；连通时停止。
这个图在新点的意义下是一个有若干点双的有标号连通图。
终于可以开始计数了。先计算 n 个点 m 个点双的连通图数量 f(n,m) 和 n 个点连通图数量 g(n)。注意区分 n,N。
先是 g(n) 的转移。可以写暴力多项式求 \ln，也可以容斥。具体地，枚举包含节点 1 的极大连通块，剩下的随意连边，有：
g(n)=2^{\binom{n}2}-\sum\limits_{i=1}^{n-1}\dbinom{n-1}{i-1}2^{\binom{n-i}2}g_i
其中 i 是极大连通块大小，\dbinom{n-1}{i-1} 是给连通块里的点分配标号，2 的幂是内部随意连边的方案数。
$$f(n,1)=g(n)-\sum\limits_{i=2}^{n-1}f(n,i)$$
接下来是 $f(n,m)$，其中 $m\ge 2$。对圆方树计数，钦定 $1$ 是根，其中 $n$ 个圆点 $m$ 个方点，设第 $i$ 个方点的儿子数是 $d_i$。把方点和其儿子视为一个整体，连成一棵树。如果现不考虑方点的存在，就是典中典 $m+1$ 个大小分别为 $1,d_1,\cdots,d_m$ 的连通块加边连成树，Prüfer 序列得到方案数是 $n^{m-1}\prod_{i=1}^m d_i$。再把方点考虑进来，最后都是方点连向父亲，每个连通块里是哪个点连的都不重要，每种方案被重复算了 $\prod\limits_{i=1}^m d_i$，除掉之后就是 $n^{m-1}$。乘上方点内部的方案数和分配标号的方案数，除掉方点无标号导致多算的系数，有：$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)=\sum\limits_{d_1+\cdots+d_m=n-1}\prod\limits_{i=1}^m\dfrac{f(d_i+1,1)}{d_i!}$。注意到 $N\ge 2$，故方点都有儿子，即 $d_i\ge 1$。有转移 $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)=\sum\limits_{d_m=1}^{n-1} h(n-d_m,m-1)h(d_m,1）$$
代回 $f$ 的转移：
$$f(n,m)=\dfrac{n^{m-1}(n-1)!h(n,m)}{m!}$$
最后统计答案。枚举初始放入的新点个数 $x$，连成的点双个数 $y$，第 $i$ 个新点的大小 $s_i$，然后式子和前面计算 $f$ 的差不多，就是总点数变成 $N$ 了。具体地，此时的贡献为 $\dfrac{N^{y-1}(x-1)!h(x,y)\prod_{i=1}^x s_i}{y!}$。
然后再做一个 $\sum\limits_{i=1}^x s_i=N$ 的背包就可以得到结果了。具体地，设 $H(n,s)$ 表示当 $x=n,\sum\limits_{i=1}^x s_i=s$ 的 $\prod_{i=1}^x s_i$，则转移为：
$$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)=1$。
其中 $[2|s_n]$ 是因为新点大小一定是偶数（偶环或两个点）。$G(x)$ 是 $x$ 个点的新点方案数，$x=2$ 是 $1$，否则是 $\dfrac{(x-1)!}2$。组合数是分配标号。
最后答案为：
$$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!}$$
后半部分是 $\ge 2$ 个新点，前面是一个新点。
看起来或许可以用神秘的在线或半在线卷积做到 $\overset{\sim}{O}(n^2)$，不过暴力做时间复杂度 $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;
}
```