Miku

这个题很显然的可以从部分分推到正解

64
上去就是一个四维dp，dp[i][j][k][z]表示在第1行的时候第一行选了j个，第2行选了k个，第3行选了z个的

情况下的方案数，转移用手就能推。

只是有个小细节

#include<iostream>
#include<cstdio> 
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
int n,m;
int ma[101][2001];
int mod=998244353;
int dp[101][41][41][41];
int ans; 
signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            scanf("%lld",&ma[i][j]);
        }
    }
    dp[0][0][0][0]=1;
    //我是 小细节 
    for(int i=1;i<=n;++i){
        for(int j=0;j<=i;++j){
            for(int k=0;k<=i;++k){
                for(int z=0;z<=i;++z){
                    dp[i][j][k][z]=(dp[i][j][k][z]+dp[i-1][j][k][z])%mod;
                    if(j) dp[i][j][k][z]=(dp[i][j][k][z]+(dp[i-1][j-1][k][z]*ma[i][1])%mod)%mod;
                    if(k) dp[i][j][k][z]=(dp[i][j][k][z]+(dp[i-1][j][k-1][z]*ma[i][2])%mod)%mod;
                    if(z) dp[i][j][k][z]=(dp[i][j][k][z]+(dp[i-1][j][k][z-1])*ma[i][3]%mod)%mod; 
                }
            }
        }
    }
    for(int i=0;i<=n/2;++i){
        for(int j=0;j<=n/2;++j){
            for(int z=0;z<=n/2;++z){
                if((i+j)>=z&&(z+i)>=j&&(z+j)>=i){
                    ans+=dp[n][i][j][z];
                    ans%=mod;
                }
            }
        }
    }
    cout<<ans-1;
    //我也是 
    return 0;
}

64

要考虑更多的列，那何不压缩一下，改成三维，前两维一样，但是第三维改成其余行选了几个

这样的话，就要分开考虑每一列了。然后再运用一点点数学知识

显然考虑合法方案很恶心，可是scz说说过“正难则反”%%%

求出所有解减去不合法的。

#include<iostream>
#include<cstdio> 
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
int n,m;
int ma[101][2001];
int mod=998244353;
int dp[101][51][80];
int sum[101];
int ans=1; 
int simex; 
signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            scanf("%lld",&ma[i][j]);
            sum[i]+=ma[i][j];
            sum[i]%=mod;
        }
        //sum[i]%=mod;
        ans=(ans*(sum[i]+1)%mod)%mod;
    }
    //dp[0][0][0]=1;
    for(int q=1;q<=m;++q){
        memset(dp,0,sizeof(dp));
        dp[0][0][0]=1;
        for(int i=1;i<=n;++i){
            for(int j=0;j<=i;++j){
                for(int z=0;z<=i-j;++z){
                    dp[i][j][z]=(dp[i][j][z]+dp[i-1][j][z])%mod;
                    if(j){
                        dp[i][j][z]=(dp[i][j][z]+(dp[i-1][j-1][z]*ma[i][q])%mod)%mod;
                    } 
                    if(z){
                        dp[i][j][z]=(dp[i][j][z]+(dp[i-1][j][z-1]*(sum[i]-ma[i][q])%mod)%mod)%mod;
                    }
                }
            }
        }
        for(int ii=1;ii<=n;++ii){
            for(int j=0;j<=n-ii;++j){
                if(ii>j){
                    simex+=(dp[n][ii][j]);
                    simex%=mod; 
                }
            }
            simex=(simex+mod)%mod;
        } 
    }
    cout<<(ans-simex-1+mod)%mod;
    return 0;
}

100

要想拿到这个，还要再压一维。我们关心选了几个吗？不，正相反，这个差才是关心的。

又少了一位，但是差可能是个负数，最小是-n，那么就全部加上一个n。