考场上想到正解,极其高兴,后来估分都是说我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读入的数组开小了啊啊啊啊啊啊啊啊啊啊啊我是什么傻逼 本来挺高兴的现在觉得我就是傻逼