Description

给定N个度数为1或2的点，求所有带标号简单无向图（无重边和自环）的方案数。

Solution

设度数为2的点有$n$个，度数为1的有$m$个。
因为只有1和2，所以图一定是由许多链和大小大于等于3的简单环构成的，于是我们可以先将度数为1的点忽略（它们只能构成链的两端，一定是两两配对的）。
先考虑环，设$F_i$表示用$1$~$i$的点组成若干个环的方案数，考虑转移，枚举新加入环的大小，由于是带标号的，我们强制把$i$放进新的环内，使得每个环具有区分性（可以理解为给每个环编号），避免算重。转移大概是这样：$F_i={\sum }_{j=3}^i\frac{1}{2}{F}_{i-j}{C}_{i-1}^{j-1}(j-1)!$
然后处理$G_i$，先设一个$g_{i,j}$表示$i$个点组成$j$条链的方案数。转移易得为$g_{i,j}=g_{i-1,j}\cdot (i-1+j)+g_{i-1,j-1}$。最后考虑编号：$G_i=\sum g_{i,j}\cdot P_{m/2}^j$
最后求出$ans=({\prod }_{i=1}^{m/2}2i-1){\sum }_{i=0}^n{F}_i\cdot G_{n-i}$

Code

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define fo(i,j,k) for(int i=j;i<=k;++i)
#define fd(i,j,k) for(int i=j;i>=k;--i)
using namespace std;
typedef long long ll;
const int N=2e3+10,mo=998244353,n2=499122177;
int cn[N];
ll g[N][N],c[N][N];
ll F[N],G[N],jc[N];
int main()
{freopen("map.in","r",stdin);freopen("map.out","w",stdout);int n,o;scanf("%d",&n);fo(i,1,n) scanf("%d",&o),cn[o]++;if(cn[1]&1) return printf("0"),0;c[0][0]=jc[0]=1;fo(i,1,n){c[i][0]=1;fo(j,1,i) c[i][j]=(c[i-1][j]+c[i-1][j-1])%mo;jc[i]=jc[i-1]*i%mo;}F[0]=1;fo(i,3,cn[2])fo(j,3,i) F[i]=(F[i]+F[i-j]*c[i-1][j-1]%mo*jc[j-1]%mo*n2%mo)%mo;g[0][0]=1;fo(i,1,cn[2])fo(j,1,min(cn[1]/2,i)) g[i][j]=(g[i-1][j]*(i+j-1)%mo+g[i-1][j-1])%mo;G[0]=1;fo(i,1,cn[2])fo(j,1,cn[1]/2) G[i]=(G[i]+g[i][j]*c[cn[1]/2][j]%mo*jc[j]%mo)%mo;ll ans=0;fo(i,0,cn[2]) ans=(ans+c[cn[2]][i]*G[i]%mo*F[cn[2]-i]%mo)%mo;ll tmp=1;fo(i,2,cn[1]/2) tmp=tmp*(i+i-1)%mo;printf("%lld",ans*tmp%mo);
}