这题在考场上只会O(n^3 m),拿了84分。。
先讲84分，考虑容斥，用总方案减去不合法方案，也就是枚举每一种食材，求用它做超过(lfloor frac{k}{2} floor) 道菜的方案数，从总方案中减去。
先枚举一种食材x，设f[i][j][k]为前i种烹饪方法中，做j道菜，其中k道是食材x做的的方案数，转移考虑第i种烹饪方案 不做菜/做食材x的菜/做其他食材的菜 三种情况。最后所有f[n][j][j/2+1 ~ n]的和即是不合法情况。
考虑怎么优化，设一种方案中有k道菜，其中t道菜是x食材做的，那么当且仅当(t>lfloor frac{k}{2} floor)时方案不合法，也即(2t-k>0)时不合法。那么我们在dp时就只需要记录方案中(2t-k)的值，最后取大于0的状态的方案数即可。即设f[i][j]为只考虑前i种烹饪方法，方案中(2t-k)的值为j的方案数。转移考虑以上三种情况分别转移到 f[i+1][j]/f[i+1][j+1]/f[i+1][j-1] 即可。
代码：
#include<bits/stdc++.h>
using namespace std;
#define N 107
#define M 2007
#define ll long long
const ll mod=998244353;
ll a[N][M],sum[N],f[N][N<<1];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%lld",&a[i][j]);
sum[i]=(sum[i]+a[i][j])%mod;
}
ll ans=0;
for(int now=1;now<=m;now++)
{
memset(f,0,sizeof(f));
f[0][N]=1;
for(int i=1;i<=n;i++)
{
for(int j=N-n;j<=N+n;j++)
{
f[i][j]=(f[i][j]+f[i-1][j])%mod;
f[i][j]=(f[i][j]+f[i-1][j-1]*a[i][now])%mod;
f[i][j]=(f[i][j]+f[i-1][j+1]*(sum[i]+mod-a[i][now]))%mod;
}
}
for(int i=1;i<=n;i++)
ans=(ans+f[n][N+i])%mod;
}
ll res=1;
for(int i=1;i<=n;i++)
res=res*(sum[i]+1)%mod;
res=(res+mod-1)%mod;
res=(res+mod-ans)%mod;
printf("%lld
",res);
return 0;
}