省选模拟（12.08） T3 圈圈圈圈圈圈圈圈

圈圈圈圈圈圈圈圈

题目背景：

12.08 省选模拟T3

分析：DP

定义f[i][j]表示枚举到第i个家族，有j个人没有被匹配，那么枚举第i + 1个家族中有多少人用于和这j个人匹配，转移方程:

f[i + 1][j + a[i + 1] - x * 2] += f[i][j] * c(j, x) * c(a[i + 1], x) * x!

意义为，从a[i + 1]个人中选出x个人，从原来剩下的j个人中选出x个人，左边x个和右边x个进行匹配，匹配的方案数是x!,直接转移就可以了，复杂度O(n⁴)信仰就好······考场上预处理组合数的时候，有一部分的c[i][0]没有初始化为1······然后GG了30分······

Source:

/*created by scarlyw
*/
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include ///*
template
inline void R(T &x) {static char c;static bool iosig;for (c = getchar(), iosig = false; !isdigit(c); c = getchar())if (c == '-') iosig = true;	for (x = 0; isdigit(c); c = getchar()) x = ((x << 2) + x << 1) + (c ^ '0');if (iosig) x = -x;
}
//*/const int MAXN = 150 + 5;
const int mod = 998244353;int n;
long long f[MAXN][MAXN * MAXN], c[MAXN * MAXN][MAXN], a[MAXN], js[MAXN];
int sum;inline void add(long long &x, long long t) {x += t, (x >= mod) ? (x -= mod) : (x); 
}int main() {freopen("c.in", "r", stdin);freopen("c.out", "w", stdout);R(n), js[0] = 1;for (int i = 0; i < MAXN * MAXN; ++i) c[i][0] = 1;for (int i = 0; i < MAXN; ++i) c[i][i] = 1;for (int i = 1; i < MAXN; ++i) js[i] = (long long)i * js[i - 1] % mod;for (register int i = 2, s = MAXN * MAXN; i < s; ++i)for (register int j = 1; j < i && j < MAXN; ++j)c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;f[0][0] = 1;for (register int i = 1; i <= n; ++i) {R(a[i]);for (register int j = 0; j <= sum; ++j) {for (register int k = 0; k <= a[i] && k <= j; ++k)f[i][j + a[i] - k * 2] = ((long long)f[i - 1][j] * c[j][k] % mod * c[a[i]][k] % mod * js[k] % mod + f[i][j + a[i] - k * 2]) % mod;}sum += a[i];}
//	for (int i = 0; i <= n; ++i, std::cout << '\n')
//		for (int j = 0; j <= sum; ++j)
//			std::cout << f[i][j] << " ";std::cout << (f[n][0] + mod) % mod;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！