NOIP252挂到212警戒后人
查看原帖
NOIP252挂到212警戒后人
279652
APJifengc楼主2021/12/3 12:49

考场上想到正解,极其高兴,后来估分都是说我T2 60分 我非常纳闷 以下是我的考场代码

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353, MAXN = 35, MAXM = 105;
int n, m, k;
int v[MAXN];
int f[2][MAXN][MAXN][MAXN][MAXN];
int g[MAXM][MAXN][MAXN][MAXN];
int fac[MAXN], inv[MAXN];
int qpow(int a, int b) {
	int res = 1;
	while (b){
		if (b & 1) res = 1ll * res * a % MOD;
		a = 1ll * a * a % MOD;
		b >>= 1;
	}
	return res;
}
int C(int n, int m) { return 1ll * fac[n] * inv[m] % MOD * inv[n - m] % MOD; }
#define rep(i, j, k) for (int i = j; i <= k; ++i)
int Pow[MAXM][MAXN];
signed main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 0; i <= m; i++) scanf("%d", &v[i]);
	g[0][0][0][0] = 1;
	fac[0] = inv[0] = 1;
	for (int i = 1; i <= n; i++) fac[i] = 1ll * fac[i - 1] * i % MOD;
	inv[n] = qpow(fac[n], MOD - 2);
	for (int i = n - 1; i >= 1; i--) inv[i] = 1ll * inv[i + 1] * (i + 1) % MOD;
	for (int i = 0; i <= m; i++) {
		Pow[i][0] = 1;
		for (int j = 1; j <= n; j++) {
			Pow[i][j] = 1ll * Pow[i][j - 1] * v[i] % MOD;
		}
	}
	for (int q = 1, o = 0; q <= m + 1; q++, o ^= 1) {
		memset(f[o], 0, sizeof f[o]);
		rep(a, 0, k) rep(b, 0, n) rep(c, 0, n) rep(d, b, n) {
			if (a - (b + c) % 2 >= 0) {
				f[o][a][b][c][d] = 1ll * g[q - 1][a - (b + c) % 2][c][d - b] * C(d, b) % MOD * Pow[q - 1][b] % MOD;
				// if (f[o][a][b][c][d] != 0)
				// printf("f[%d][%d][%d][%d][%d] = %d\n", q, a, b, c, d, f[o][a][b][c][d]);
				g[q][a][(b + c) / 2][d] = (g[q][a][(b + c) / 2][d] + f[o][a][b][c][d]) % MOD;
			}
		}
	}
	int ans = 0;
	rep(a, 0, k) rep(b, 0, n) rep(c, 0, n) if (a + __builtin_popcount((b + c) / 2) <= k) {
		ans = (ans + f[m % 2][a][b][c][n]) % MOD;
	}
	printf("%d\n", ans);
	return 0;
}

和第一篇题解基本一模一样)

然后我一直在学校补文化课 刚刚有机会看了看

然后我发现我的错误是:

int v[MAXN];

我tm读入的数组开小了啊啊啊啊啊啊啊啊啊啊啊我是什么傻逼 本来挺高兴的现在觉得我就是傻逼

2021/12/3 12:49
加载中...