Description
Input
Output
Solution
这题有好几个做法，这里介绍两个
Solution 1
（这似乎是网上的正解）
From zsjzliziyang
设f[ i ][ j ]表示度数为1、2的点个数分别为i，j时答案。
分为下面的4种情况
1：当t2为0时我们新增若干条长度为2的链，我们将不会在这些链中间加其他任何点
2：新增形如1-2-1的一条新链
3：在条链的一个位置加入两个为2的点
4：把某一条链拆掉，将其中度数为2的点与3个新的点构成一个新的环
这个方法最关键的地方就是它是把一条链中间的度数为2的点和3个新的点构成一个环，很大程度上避免了在环中间加入新的数导致很难搞重复的窘境
然后进行DP即可
但因为本题有更快的方法，所以作者未打出来
详情可转至zsjzliziyang的文章
Solution 2
这解法我还是打了的[小庆幸]
Mentality
由于点的度数只有1,2两种，图的组成一定是若干条链与若干个环，设度数为1,2点的个数分别为c1,c2。
一条链两端有两个度数为1的点，于是链的条数k确定了k=c1/2（c1为奇数则无解）。
首先考虑c1个点两两匹配的方案数，考虑将c1个点放到左右两边对齐的方案，即A(c1,c1/2)，然后对齐的一对点互相交换是同一种方案，即每种方案算重复2(c1/2)次。综上c1个点两两匹配方案数为A(c1,c1/2)/(2(c1/2))。
然后考虑c2个点怎么分配。枚举x表示分配x个点组成链，c2-x个点组成环，先乘上系数C(c2,x)。
设f[i]表示i个点插进k条链的方案，只需考虑i有几个位置可插。之前已经插入i-1个点，因此有i-1+k个位置可插，递推式：
f[0]=1
f[i]=f[i-1]*(i-1+k)
设g[i]表示i个点组成若干环的方案，分两种情况：1.i与前面两点新建三元环 2.i插入到之前某个环 递推式：
g[0]=1
g[i]=g[i-3]C(i-1,2)+g[i-1](i-1)
最终答案即为：
sigma(f[x]g[c2-x]C(c2,x))
预处理阶乘逆元，组合数可以O(1)算出，f,g可以O(n)递推，答案也可O(n)计算，总复杂度O(n)
Code
#include <cstdio>
#include <algorithm>
#define MO 998244353
#define N 2001
#define open(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
using namespace std;
int i,n,a;
long long ans,t,tot,p[3],f[N],g[N],inv[5001],inc[5001];
long long ksm(long long x,int y)
{
long long sum=1;
while (y)
{
if (y&1)sum=sum*x%MO;
x=x*x%MO;
y>>=1;
}
return sum;
}
long long C(long long x,long long y)
{
return inv[x]*inc[y]%MO*inc[x-y]%MO;
}
int main()
{
open("graph");
inv[1]=inv[0]=1;
for (i=2;i<=5000;i++)
inv[i]=inv[i-1]*i%MO;
inc[5000]=ksm(inv[5000],MO-2);
for (i=4999;i>=0;i--)
inc[i]=inc[i+1]*(i+1)%MO;
scanf("%d",&n);
for (i=1;i<=n;i++)
{
scanf("%d",&a);
p[a]++;
}
tot=p[1]/2;
if (p[1]%2!=0)
{
printf("0");
return 0;
}
t=inc[tot]*inv[p[1]]%MO*ksm(ksm(2,tot),MO-2)%MO;
f[0]=g[0]=1;
for (i=1;i<=p[2];i++)
{
f[i]=f[i-1]*(i-1+tot)%MO;
g[i]=g[i-1]*(i-1)%MO;
if (i>=3) g[i]=(g[i]+g[i-3]*C(i-1,2))%MO;
}
for (i=0;i<=p[2];i++)
ans=(ans+f[i]*g[p[2]-i]%MO*C(p[2],i)%MO)%MO;
printf("%lld",t*ans%MO);
return 0;
}