84pts求助
查看原帖
84pts求助
824941
bsjsaikou10楼主2023/11/24 09:10
#include <bits/stdc++.h>
#define mod 998244353
using namespace std;
long long f[110][2200], f2[110][2200], a[110][1100], n, m, sum[110];
long long Emiya_will_be_killed;
long long Emiya_will_binary_save;

void process() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            sum[i] = (sum[i] + a[i][j]) % mod;
        }
    }
}

long long calc_dp() {
    process();
    for (int l = 1; l <= m; l++) {
        memset(f, 0, sizeof(f));
        f[0][n] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = n - i; j <= n + i; j++) {
                f[i][j] = (f[i - 1][j] + f[i - 1][j - 1] * a[i][l] % mod + f[i - 1][j + 1] * (sum[i] - a[i][l] + mod) % mod) % mod;
            }
        }
        for (int i = 1; i <= n; i++) {
            Emiya_will_be_killed = (Emiya_will_be_killed + f[n][n + i]) % mod;
        }
    }
    f2[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            f2[i][j] = f2[i - 1][j];
            if(j>0) {
                f2[i][j] = (f2[i][j] + f2[i - 1][j - 1] * sum[i] % mod) % mod;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        Emiya_will_binary_save = (Emiya_will_binary_save + f2[n][i]) % mod;
    }
    long long Emiya_will_save = (Emiya_will_binary_save - Emiya_will_be_killed + mod) % mod;
    return (long long)Emiya_will_save;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    cout << (long long)calc_dp();
}
2023/11/24 09:10
加载中...