Description：

有 $n$ 个点，每个点的度数都是 $1$ 或 $2$ ，给出每个点的度数，问有多少种合法的图。

$1\le n \le 2000$

Solution：

统计一下度数为 $1/2$ 的节点个数，分别记为 $s1/s2$ ，然后开始背题解：

设 $f[i][j]$ 表示有 $i$ 个度数为 $1$ ， $j$ 个度数为 $2$ 的节点的方案数，有四个转移：

$f[i+1][j]+=f[i-1][j]\times i$ ：把两个度数为 $1$ 的点连在一起，如果当前有 $i$ 个度数为 $1$ 的点，那么这次转移有 $i$ 种选法，剩下部分的方案数相当于有 $i-1$ 个度数为 $1$ 的点，度数为 $2$ 的点个数不变的方案数。

$f[i][j + 1] += f[i-2][j]\times C_i^2$ ：把一个度数为 $2$ 的点和两个度数为 $1$ 的点连起来，有 $C_i^2$ 种选法，剩下部分相当于剩 $i-2$ 个度数为 $1$ 的点。

$f[i][j+1]+=f[i + 2][j - 2]\times C_j^2$ ：把一个度数为 $2$ 的点和两个度数为 $2$ 的点连起来，有 $C_j^2$ 种选法，剩下两个度数为 $2$ 的点只有了一个度，相当于两个度数为 $1$ 的点。

$f[i][j+1]+=f[i][j-1]\times i\times j$ ：把一个度数为 $2$ 的点和一个度数为 $1$ ，一个度数为 $2$ 的点连起来，有 $i\times j$ 种方案。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 2010

#define MOD 998244353

int s1 = 0,s2 = 0;

long long f[MAXN][MAXN];

int main()

{

	freopen("map.in","r",stdin);

	freopen("map.out","w",stdout);

	scanf("%d",&n);

	int k;

	for(int i = 1;i <= n;++i)

	{

		scanf("%d",&k);

		if(k == 1)++s1;

		else ++s2;

	}

	f[0][0] = 1;

	for(int tot = 1;tot <= n;++tot)

	{

		for(int i = tot;i >= 0;--i)

		{

			int j = tot - i;

			if(j < 0)continue;

			if(j == 0 && i)f[i + 1][j] = (f[i + 1][j] + f[i - 1][j] * i % MOD) % MOD;

			if(i >= 2)f[i][j + 1] = (f[i][j + 1] + f[i - 2][j] * (i * (i - 1) / 2 % MOD) % MOD) % MOD;

			if(j >= 2)f[i][j + 1] = (f[i][j + 1] + f[i + 2][j - 2] * (j * (j - 1) / 2 % MOD) % MOD) % MOD;

			if(j >= 1)f[i][j + 1] = (f[i][j + 1] + f[i][j - 1] * i % MOD * j % MOD) % MOD;

		}

	}

	cout << f[s1][s2] << endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}