64pts $O(n^4)$

状态表示 我们可以设一个 ( dp )，建立 ( m ) 个维度存下每种物品选了几次：

• ( f[i][A][B][C] ) 表示前 ( i ) 种烹饪方法，第 ( 1/2/3 ) 种主要食材各自选了 ( A, B, C ) 道菜的方案数。

状态转移：根据题意，每种烹饪方法最多选一道菜。

• 不做菜 ( f[i][A][B][C] += f[i-1][A][B][C] )
• 做 1 道第一种主要食材的菜：( f[i][A][B][C] += f[i-1][A-1][B][C] \times a_{i,1} )
• 做 1 道第二种主要食材的菜：( f[i][A][B][C] += f[i-1][A][B-1][C] \times a_{i,2} )
• 做 1 道第三种主要食材的菜：( f[i][A][B][C] += f[i-1][A][B][C-1] \times a_{i,3} )

答案： $ \sum_{A=0}^{n}\sum_{B=0}^{n}\sum_{C=0}^{n} f[n][A][B][C] \quad \text{（满足} \max(A,B,C) \leq \lfloor \frac{A+B+C}{2} \rfloor \text{且} A+B+C > 0 \text{）} $

#include<bits/stdc++.h>
using namespace std;
const int N = 45, M = 6, P = 998244353;
int n, m, a[N][M];
typedef long long LL;
LL f[N][N][N][N];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) scanf("%d", &a[i][j]);

    f[0][0][0][0] = 1;
    for(int i=1;i<=n;i++)
    {
        for(int A=0;A<=i;A++)
        {
            for(int B=0;B<=i;B++)
            {
                for(int C=0;C<=(m==3?i:0);C++)
                {
                    f[i][A][B][C]=f[i-1][A][B][C];
                    if(A&&a[i][1]) f[i][A][B][C]=f[i][A][B][C]+f[i-1][A-1][B][C]*a[i][1];
                    if(B&&a[i][2]) f[i][A][B][C]=f[i][A][B][C]+f[i-1][A][B-1][C]*a[i][2];
                    if(m==3&&C&&a[i][3]) f[i][A][B][C]=f[i][A][B][C]+f[i-1][A][B][C-1]*a[i][3];
                    f[i][A][B][C]%=P;
                }
            }
        }
    }
    LL ans=0;
    for(int A=0;A<=n;A++)
    {
        for(int B=0;B<=n;B++)
        {
            for(int C=0;C<=n;C++)
            {
                int s=A+B+C;
                if(s>0&&max({A,B,C})<=s/2)  ans=(ans+f[n][A][B][C])%P;
            }
        }
    }
    cout<<ans;
    return 0;
}

100pts $n^2m$

我们考虑补集的思想,使用f[i][j]表示前i中烹饪方法做了j道菜的方案数,g[i][j]表示前i中烹饪方法，第k中食材和其它食材差值为j的方案数

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=110,M=2010,MOD=998244353;
int n,m;
LL a[N][M],s[N];
LL f[N][N],g[N][N*2];
//f[i][j]表示前i中烹饪方法做了j道菜的方案数,g[i][j]表示前i中烹饪方法，第k中食材和其它食材差值为j的方案数
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
            s[i]=(s[i]+a[i][j])%MOD;
        }
    }
    f[0][0]=1;//初始化
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=i;j++)
        {
            f[i][j]=f[i-1][j];//不用第i中烹饪方案
            if(j)
            {
                f[i][j]=(f[i][j]+f[i-1][j-1]*s[i])%MOD;
            }
        }
    }
    LL res=0;
    for(int i=1;i<=n;i++)
    {
        res=(res+f[n][i])%MOD;//累加所有n中烹饪方式中选择i中菜的方案数
    }
    for(int k=1;k<=m;k++) //枚举当前食材
    {
        memset(g,0,sizeof g);
        g[0][N]=1;//初始化(加上偏移量)
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j+1<N*2;j++)
            {
                g[i][j]=(g[i-1][j]+g[i-1][j-1]*a[i][k])%MOD;
                //不用第i中烹饪方案,用了第i中烹饪方法且用了食材k
                g[i][j]=(g[i][j]+g[i-1][j+1]*(s[i]-a[i][k]))%MOD;
                //累加用了烹饪方法i,且没有用食材k的方案数
            }
        }
        for(int i=1;i<=n;i++) //减去非法方案
        {
            res=(res-g[n][N+i])%MOD;
        }
    }
    cout<<(res+MOD)%MOD;
    return 0;
}