题目大意
猫的神经系统是一个包含$n$个点的简单无向图。其中第$i$个点的度数为$d_i$。
有一天，猫气炸了，你要帮猫冷静下来。为了帮猫冷静下来，你首先需要计算出猫的神经系统总共有多少种可能的组合方式。两种方式是不同的，当且仅当有一条边在一种方式中存在，而在另一种方式中不存在。
题目分析
Neko？
我为什么要帮Neko冷静下来？
看完题后不难写出状态。
设$f[i,x,y]$表示前$i$个点，有$x$个度为$1$的点，$y$个度为$2$的点的方案数。
不难发现转移是$O(n^3)$的，可以过$50\%$的数据。
不难发现，状态的第一维：前$i$个点是无意义的，我们去掉这一个维度依然能唯一确定一个状态。
但因为去掉了第一维，导致有序性被破坏，计数会重，故我们需要固定一个转移顺序并重新修改状态转移。
设$f[x,y]$表示有$x$个度为$1$的点，$y$个度为$2$的点的方案数。
规定先处理度为$2$的结点，后处理度为$1$的结点。
- 若$y=0$，将两个度为$1$的点连接起来，固定其中一个结点后另一个结点有$x-1$种选法，$f[x,y]=(x-1)f[x-2,y]$
- 用一个度为$2$的结点连接两个度为$1$的结点，固定度为$2$的结点，$f[x,y]+=C_x^2f[x-2,y-1]$
- 用一个度为$2$的结点连接一个度为$1$的结点和一个度为$2$的结点，固定其中一个度为$2$的结点，那么其中另一个度为$2$的结点退化为度为$1$的结点，$f[x,y]+=x(y-1)f[x,y-2]$
- 用一个度为$2$的结点连接两个度为$2$的结点，固定其中一个结点，另外两个度为$2$的结点退化为度为$1$的结点，$f[x,y]+=C_{y-1}^2f[x+2,y-3]$
注意边界，使用记忆化搜索的方式实现。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const LL mod=998244353;
LL f[2005][2005],Hash[3];
LL C(LL x) {
return (x*(x-1)/2)%mod;
}
LL Dp(int One,int Two) {
if(One<0||Two<0)return 0;
if(One==0&&Two==0)return 1;
if(f[One][Two]!=-1)return f[One][Two];
LL sum=0;
if(Two==0)sum=(One-1)*Dp(One-2,Two)%mod;
sum=(sum+C(One)*Dp(One-2,Two-1)%mod)%mod;
sum=(sum+One*(Two-1)%mod*Dp(One,Two-2)%mod)%mod;
sum=(sum+C(Two-1)*Dp(One+2,Two-3)%mod)%mod;
return f[One][Two]=sum;
}
int n;
int main() {
n=Get_Int();
for(int i=1; i<=n; i++)Hash[Get_Int()]++;
memset(f,-1,sizeof(f));
printf("%lld\n",Dp(Hash[1],Hash[2]));
return 0;
}
|
