比赛 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;
}