题意
在所以置换下，本质不同的各个极大连通子图均含有欧拉闭迹的\(n\)阶图个数
做法
务必先做完这题再看此题解，因为会省略大部分分析了
仍是从边入手，隔外限制：各个点度数是偶数
- 某个因子内\((m=a_i)\)
如果\(m\)是奇数，等价类的边集构成了若干个环，对度数的奇偶性不发生影响
是偶数，边\((1,1+\frac{m}{2})\)所处的等价类对各个点奇偶性都会改变，其他等价类不变 - 两个因子\((m_1=a_i,m_2=a_j,i\neq j)\)，
\(d=(m_1,m_2)\)个等价类，每个等价类\(a_i\)中的每一点连出\(\frac{m_2}{d}\)条边，中的每一点连出\(\frac{m_1}{d}\)条边
如果均为偶数，则不发生影响
如果有一方为偶数（因为一方每个点连出的边数相同，将这方当做一个大点），看作另一方能凭空\(d\)次改变奇偶性
如果两方均不为偶数，则这两大点之间连\(d\)条边
现在题目转化为
\(M\)条边的\(N\)阶图，除\(M\)条边外，每个点有\(a_i\)个环（不过每个环仅为该点度数加\(1\)），求保存一些边，使得每个点度数为偶数的方案数
然后这里求方案数有个简单结论，不是重点，就不细说了，各位去看其他题解吧
题外话
代码改了很多次，不太可看的样子（惨不忍睹）
code
#include<bits/stdc++.h>
typedef int LL;
#define pb push_back
#define opt operator
const LL maxn=60+9,mod=998244353;
LL Read(){
LL x(0),f(1); char c=getchar();
while(c<'0' || c>'9'){
if(c=='-') f=-1; c=getchar();
}
while(c>='0' && c<='9'){
x=(x<<3ll)+(x<<1ll)+c-'0'; c=getchar();
}return x*f;
}
LL T,n,ans,tot;
LL a[maxn],fa[maxn],fac2[maxn*maxn],fac[maxn],fav[maxn],sumd[maxn],sume[maxn],gcd[maxn][maxn],num[maxn],size[maxn];
LL Pow(LL base,LL b){
LL ret(1);
while(b){
if(b&1) ret=1ll*ret*base%mod; base=1ll*base*base%mod; b>>=1;
}return ret;
}
LL Find(LL x){ return fa[x]==x?x:fa[x]=Find(fa[x]); }
void Check(){
tot=0;
LL ret(1);
for(LL i=1;i<=n;++i){
for(LL j=1;j<=num[i];++j) a[++tot]=i;
}
for(LL i=1;i<=tot;++i){
if(a[i]&1) ret=1ll*ret*fac2[a[i]/2]%mod;
else ret=1ll*ret*fac2[a[i]/2-1]%mod,sumd[i]=1;
fa[i]=i; size[i]=1;
}
for(LL i=1;i<=tot;++i){
for(LL j=i+1;j<=tot;++j){
LL a1(a[i]),a2(a[j]);
LL g(gcd[a1][a2]),b1(a2/g),b2(a1/g); b1&=1; b2&=1;
LL fx(Find(i)),fy(Find(j));
if(b1 && b2){
if(fx!=fy) sume[fy]+=sume[fx],sumd[fy]+=sumd[fx],size[fy]+=size[fx];
fa[fx]=fy;
sume[fy]+=g;
}else if(b1) sumd[fx]+=g;
else if(b2) sumd[fy]+=g;
else ret=1ll*fac2[g]*ret%mod;
}
}
for(LL i=1;i<=tot;++i){
if(Find(i)==i){
ret=1ll*ret*fac2[sume[i]-size[i]+1]%mod;
if(sumd[i]) ret=1ll*ret*fac2[sumd[i]-1]%mod;
}
}
LL ret1(fac[n]);
for(LL i=1;i<=tot;++i){
ret1=1ll*ret1*fav[a[i]]%mod*fac[a[i]-1]%mod;
}
for(LL i=1;i<=n;++i) ret1=1ll*ret1*fav[num[i]]%mod;
ret=1ll*ret*ret1%mod;
for(LL i=1;i<=tot;++i) sumd[i]=sume[i]=0;
ans=(1ll*ans+ret)%mod;
}
void Dfs(LL x,LL N){
if(x==1){
num[x]=N; Check(); return;
}
for(LL i=0;i*x<=N;++i){
num[x]=i; Dfs(x-1,N-i*x);
}
}
int main(){
n=Read();
fac2[0]=1; for(LL i=1;i<=n*n;++i) fac2[i]=2ll*fac2[i-1]%mod;
fac[0]=1; for(LL i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod;
fav[n]=Pow(fac[n],mod-2); for(LL i=n;i>=1;--i) fav[i-1]=1ll*fav[i]*i%mod;
for(LL i=1;i<=n;++i) gcd[i][0]=gcd[0][i]=i;
for(LL i=1;i<=n;++i){
gcd[i][i]=i;
for(LL j=i+1;j<=n;++j){
gcd[i][j]=gcd[j][i]=gcd[i][j%i];
}
}
Dfs(n,n);
ans=1ll*ans*fav[n]%mod;
printf("%d\n",ans);
return 0;
}