题目大意

给定 \(n\) 个度数为 \(\in [1,2]\) 之间的点，求能组成多少种简单无向图（可不连通，点与点之间有别）

分析

显然答案只与 \(n1,n2\) 有关

那么 \(dp\)？（我也不知道为什么）

设 \(f_{i,j}\) 表示当前状态的图用了 \(i\) 个点，目前其度数为 \(1\)；\(j\) 同理，度数为 \(2\)

四种转移：

加入两个度数为 \(1\) 的点，构成一条新链
加入度数形如 \(1-2-1\) 一条链
在某条链中插入两个度数为 \(2\) 的点
变链成环，加入三个度数为 \(2\) 的点

我也不知道为什么这么转移

然后具体统计看代码

\(Code\)

#include<cstdio>

using namespace std;

typedef long long LL;

const int N = 2005;

const LL P = 998244353;

int d[N] , n , n1 , n2;

LL ans , f[N][N];

int main()

{

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

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

	scanf("%d" , &n);

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

		scanf("%d" , &d[i]) , (d[i] == 1 ? n1++ : n2++);

	f[0][0] = 1;

	for(register int j = 0; j <= n2; j++)

		for(register int i = 0; i <= n; i++)

		{

			if (!f[i][j]) continue;

			if (!j) f[i + 2][j] = (f[i + 2][j] + f[i][j] * (i + 1)) % P;

			f[i + 2][j + 1] = (f[i + 2][j + 1] + (i + 2) * (i + 1) / 2 % P * f[i][j] % P) % P;

			f[i][j + 2] = (f[i][j + 2] + f[i][j] * i % P * (j + 1)) % P;

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

		}

	printf("%lld" , f[n1][n2]);

}

巴特西

JZOJ 5351. 【NOIP2017提高A组模拟9.7】简单无向图

题目大意

分析

\(Code\)

最新文章

热门文章