比赛 |
CSP2023-S模拟赛 |
评测结果 |
AAAAAAAAAAEEEEEEEEEE |
题目名称 |
Maximized Combos |
最终得分 |
50 |
用户昵称 |
HzmQwQ |
运行时间 |
3.418 s |
代码语言 |
C++ |
内存使用 |
26.42 MiB |
提交时间 |
2023-10-17 20:27:25 |
显示代码纯文本
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define MAXN 105
using namespace std;
typedef long long ll;
const ll M = 998244353LL;
int n, m;
ll f[MAXN][MAXN][MAXN], g[MAXN][MAXN][MAXN], sumf[MAXN][MAXN][MAXN], sumg[MAXN][MAXN][MAXN];
ll dp(int s) {
for(int i = 1; i <= n; i++)
for(int j = 0; j <= m; j++)
for(int k = 0; k <= s; k++) f[i][j][k] = g[i][j][k] = sumf[i][j][k] = sumg[i][j][k] = 0LL;
f[0][0][0] = g[0][0][0] = sumf[0][0][0] = sumg[0][0][0] = 1LL;
for(int i = 1; i <= s; i++) sumf[0][0][i] = sumf[0][0][i - 1], sumg[0][0][i] = sumg[0][0][i - 1];
for(int i = 1; i <= n; i++) {
for(int j = 0; j <= m; j++) {
if(j != 0) {
for(int k = 1; k <= s; k++) f[i][j][k] = f[i - 1][j - 1][k - 1];
}
f[i][j][0] = sumf[i - 1][j][s];
sumf[i][j][0] = f[i][j][0];
for(int k = 1; k <= s; k++) sumf[i][j][k] = (sumf[i][j][k - 1] + f[i][j][k]) % M;
}
}
for(int i = 1; i <= n; i++) {
for(int j = 0; j <= m; j++) {
if(j != 0) {
for(int k = 1; k < s; k++) g[i][j][k] = g[i - 1][j - 1][k - 1];
}
g[i][j][0] = sumg[i - 1][j][s - 1];
sumg[i][j][0] = g[i][j][0];
for(int k = 1; k < s; k++) sumg[i][j][k] = (sumg[i][j][k - 1] + g[i][j][k]) % M;
}
}
ll d1 = sumf[n][m][s], d2 = sumg[n][m][s - 1];
return (d1 - d2 + M) % M;
}
int main() {
freopen("combos.in", "r", stdin);
freopen("combos.out", "w", stdout);
scanf("%d %d", &n, &m);
for(int i = 1; i <= m; i++) {
printf("%lld\n", dp(i));
}
return 0;
}