1 条题解

  • 0
    @ 2024-12-24 9:53:35

    C++ :

    #include <iostream>
    #include <cstring>
    using namespace std;
    #define int long long
    const int MOD = 998244353;
    const int maxn = 107,maxm = 2007;
    int dp1[maxn][2*maxn]; //
    int dp2[maxn][maxn];
    int linesum[maxn]; //s1表示
    int a[maxn][maxm];
    int n, m;
    signed main() {
    	cin >> n >> m;
    	for(int i = 1;i <= n;++i) {
    		for(int j = 1;j <= m;++j) {
    			cin >> a[i][j];
    			a[i][j] %= MOD;
    			linesum[i] = ( linesum[i] + a[i][j] ) % MOD;
    		}
    	}
    	int ans = 0;
    	for(int t = 1;t <= m;++t) {
    		memset(dp1,0,sizeof(dp1));
    		dp1[0][0 + 100] = 1;
    		for(int i = 1;i <= n;++i) {
    			for(int j = -i + 100;j <= i + 100;++j) {
    				dp1[i][j] = dp1[i-1][j];
    				dp1[i][j] += (dp1[i-1][j-1] * a[i][t]) % MOD;//取
    				dp1[i][j] += (dp1[i-1][j+1] * ((linesum[i] - a[i][t] + MOD) % MOD)) % MOD;//不取
    				dp1[i][j] %= MOD;
    			}
    		}
    		for(int j = 1;j <= n;++j) {
    			ans = (ans - dp1[n][j + 100]) % MOD;
    		}
    	}
    	dp2[0][0] = 1;
    	for(int i = 1;i <= n;++i) {
    		for(int j = 0;j <= i;++j) {
    			dp2[i][j] = dp2[i-1][j];
    			for(int k = 1;k <= m;++k) {
    				dp2[i][j] += dp2[i-1][j-1] * a[i][k] % MOD;
    				dp2[i][j] %= MOD;
    			}
    		}
    	}
    	for(int j = 1;j <= n;++j)
    		ans = (ans + dp2[n][j]) % MOD;
    
    	cout << ans << endl;
    	return 0;
    }
    
    
    • 1

    信息

    ID
    1038
    时间
    3000ms
    内存
    128MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者