简要题意：
对每种菜有对应的若干种烹饪方法，用二维矩阵表示。求：每种食材用不超过 (lfloor frac{k}{2} floor) 次，至少炒一道菜，烹饪方法互不相同的个数。
算法一
注意到，对于 (32 \%) 的数据，(n leq 10)，(m leq 3).
这部分我们可以试试暴力。
暴力的注意点是，烹饪方法是独立的，因此对每个烹饪方法进行分别计算。
具体见代码。
时间复杂度：(O((m+1)^n)).
实际得分：(32pts).
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+1;
const int MOD=998244353;
typedef long long ll;
inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
int h[N],n,m; //h[i] 表示烹饪方法的选择种数
ll ans=0; int a[N][N];
inline void dfs(int dep,int sum,int x,int y) {
// dep 是正在决策的一行（即烹饪方法），sum 是方案数，x 是要选的行数，y 是已选的行数
if(x==y) {
ans=(ans+sum)%MOD; return;
} if(dep>n) return;
for(int i=1;i<=m;i++)
if(h[i]+1<=x/2) { //要求不超过一半
h[i]++;
dfs(dep+1,(1ll*sum*a[dep][i])%MOD,x,y+1); //乘法原理
h[i]--; //注意减回去，不要影响回溯
} dfs(dep+1,sum,x,y); //否则不选
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) a[i][j]=read();
if(n<=10) {
for(int i=2;i<=n;i++) dfs(1,1,i,0); //对每个烹饪方法分别计算
printf("%lld
",ans); return 0;
} //第一档部分分
return 0;
}
算法二
注意到，(m=2) 且 (n=40) 是一个部分分。
这时，每种烹饪方法只有 (3) 种：不选，选第 (1) 个，选第 (2) 个。（不可以都选，因为不能超过 (lfloor frac{m}{2} floor)）.
此时这就是背包。
即把 (a_{i,j}) 当成价值，然后有 (2) 个物品，(40) 种选法即可。
用 (f_{i,j,k}) 表示前 (i) 种烹饪方法，第一个物品选了 (j) 种，第二个选了 (k) 种的方案数。
则：
[f_{i,j,k} = f_{i-1,j,k} + f_{i-1,j-1,k} imes a_{i,1} + f_{i-1,j,k-1} imes a_{i,2}
]
注意处理取模，负下标的细节。
时间复杂度：(O(n^3)).
实际得分：(48pts).
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int N=1e2+1;
const int MOD=998244353;
typedef long long ll;
inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
int h[N],n,m; //h[i] 表示烹饪方法的选择种数
ll ans=0; int a[N][N];
ll f[N][N][N];
inline void dfs(int dep,int sum,int x,int y) {
// dep 是正在决策的一行（即烹饪方法），sum 是方案数，x 是要选的行数，y 是已选的行数
if(x==y) {
ans=(ans+sum)%MOD; return;
} if(dep>n) return;
for(int i=1;i<=m;i++)
if(h[i]+1<=x/2) { //要求不超过一半
h[i]++;
dfs(dep+1,(1ll*sum*a[dep][i])%MOD,x,y+1); //乘法原理
h[i]--; //注意减回去，不要影响回溯
} dfs(dep+1,sum,x,y); //否则不选
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) a[i][j]=read();
if(n<=10) {
for(int i=2;i<=n;i++) dfs(1,1,i,0); //对每个烹饪方法分别计算
printf("%lld
",ans); return 0;
} //第一档部分分
if(n<=40 && m<=2) {
f[0][0][0]=1; ans=0;
for(int i=1;i<=n;i++)
for(int j=0;j<=i;j++)
for(int k=0;k<=i;k++) {
f[i][j][k]=f[i-1][j][k]; //首先考虑不选
if(j) f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k]*a[i][1])%MOD; //选第一个
if(k) f[i][j][k]=(f[i][j][k]+f[i-1][j][k-1]*a[i][2])%MOD; //选第二个
} for(int i=1;i<=n/2;i++) ans=(ans+f[n][i][i])%MOD;
//因为都不能超过 n/2，所以只能都等于；如果小于 n/2 则另一个大于 n/2，不可以
printf("%lld
",ans); return 0;
}
return 0;
}
算法三
然后我们发现，(n=40)，(m=3) 本质和 (m=2) 区别不大。
此时 (lfloor frac{3}{2} floor = 1)，因此还是最多只能选一个。
同样的，用 (g_{i,j,k,l}) 表示前 (i) 种烹饪方法，第一个物品选了 (j) 种，第二个选了 (k) 种，第三个选了 (l) 种。
则：
[g_{i,j,k,l}=g_{i-1,j,k,l} + g_{i-1,j-1,k,l} imes a_{i,1} + g_{i-1,j,k-1,l} imes a_{i,2} + g_{i-1,j,k,l-1} imes a_{i,3}
]
仍然注意处理取模，负下标的问题。
时间复杂度：(O(n^4)).
实际得分：(64pts).
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int N=4e1+1;
const int MOD=998244353;
typedef long long ll;
inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
int h[N],n,m; //h[i] 表示烹饪方法的选择种数
ll ans=0; int a[N][N];
ll f[N][N][N];
ll g[N][N][N][N];
inline void dfs(int dep,int sum,int x,int y) {
// dep 是正在决策的一行（即烹饪方法），sum 是方案数，x 是要选的行数，y 是已选的行数
if(x==y) {
ans=(ans+sum)%MOD; return;
} if(dep>n) return;
for(int i=1;i<=m;i++)
if(h[i]+1<=x/2) { //要求不超过一半
h[i]++;
dfs(dep+1,(1ll*sum*a[dep][i])%MOD,x,y+1); //乘法原理
h[i]--; //注意减回去，不要影响回溯
} dfs(dep+1,sum,x,y); //否则不选
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) a[i][j]=read();
if(n<=10) {
for(int i=2;i<=n;i++) dfs(1,1,i,0); //对每个烹饪方法分别计算
printf("%lld
",ans); return 0;
} //第一档部分分
if(n<=40 && m==2) {
f[0][0][0]=1; ans=0;
for(int i=1;i<=n;i++)
for(int j=0;j<=i;j++)
for(int k=0;k<=i;k++) {
f[i][j][k]=f[i-1][j][k]; //首先考虑不选
if(j) f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k]*a[i][1])%MOD; //第一个
if(k) f[i][j][k]=(f[i][j][k]+f[i-1][j][k-1]*a[i][2])%MOD; //第二个
} for(int i=1;i<=n/2;i++) ans=(ans+f[n][i][i])%MOD;
//因为都不能超过 n/2，所以只能都等于；如果小于 n/2 则另一个大于 n/2，不可以
printf("%lld
",ans); return 0;
}
if(n<=40 && m==3) {
g[0][0][0][0]=1; ans=0;
for(int i=1;i<=n;i++)
for(int j=0;j<=i;j++)
for(int k=0;k<=i;k++)
for(int l=0;l<=i;l++) {
g[i][j][k][l]=g[i-1][j][k][l]; //首先考虑不选
if(j) g[i][j][k][l]=(g[i][j][k][l]+g[i-1][j-1][k][l]*a[i][1])%MOD; //第一个
if(k) g[i][j][k][l]=(g[i][j][k][l]+g[i-1][j][k-1][l]*a[i][2])%MOD; //第二个
if(l) g[i][j][k][l]=(g[i][j][k][l]+g[i-1][j][k][l-1]*a[i][3])%MOD; //第三个
} for(int i=0;i<=n/2;i++) //这时三个没有大小关系，不确定，因此需要枚举
for(int j=0;j<=n/2;j++)
for(int k=0;k<=n/2;k++) {
if(i>j+k || j>i+k || k>i+j) continue; //超过另外两个说明大于 n/2 （类似于三角形三边）
ans=(ans+g[n][i][j][k])%MOD;
} printf("%lld
",ans-1); return 0; //此时 g[n][0][0][0] 被算了一次，需要减去
}
return 0;
}
算法四
下面是满分算法。（如果想看 (84pts) 的部分分，下面也有说明）
考虑容斥，把所有方案加上，然后 ( exttt{dp}) 求出不合法的方案数。
这时我们需要抛开所有的前面所说。
用 (f_{i,j,k}) 表示前 (i) 种菜选 (j) 种烹饪方法，且当前烹饪方法选 (k) 次的方案数。
但是这样显然不能得到满分，考虑状态的简化。
限制为 (k > lfloor frac{j}{2} floor)，推一步等到：
(2k + n - j > n). （为什么要同时 (+n)？后面你就明白了）
而 (n-j) 正是该方法不选的哪些菜。所以考虑简化。
对于每种烹饪方法，选它时当做选 (2) 次，不做当做选 (1) 次。最后的方案数，就是被选超过 (n) 次的方案。
这个转移很妙，此时我们就不用枚举前 (i) 种菜选的烹饪方法，只考虑当前方法即可。
所以 (j) 这一维被省略（降维）。
时间复杂度：(O(n^2 imes m)).
实际得分：(100pts).
#include<bits/stdc++.h>
using namespace std;
const int N=200,M=3000,MOD=998244353;
typedef long long ll;
inline ll read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
ll x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
int n,m;
ll ans=1,s[N],a[N][M],f[N][M];
// s[i] 是第 i 中烹饪方法的方案和
// 如果不降掉第二维，则只有 84 分
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
a[i][j]=read();
s[i]=(s[i]+a[i][j])%MOD;
} ans=(ans*(s[i]+1))%MOD;
} ans=(ans+MOD-1)%MOD; //所有方案，减去全部不选
for(int i=1;i<=m;i++) {
memset(f,0,sizeof(f)); f[0][0]=1;
for(int j=1;j<=n;j++)
for(int k=0;k<=((j-1)<<1);k++) {
f[j][k]=(f[j][k]+f[j-1][k]*(s[j]-a[j][i]))%MOD; //不选当前列，继承前面的列
f[j][k+1]=(f[j][k+1]+f[j-1][k])%MOD; //不选当前烹饪方法，继承上一个方法
f[j][k+2]=(f[j][k+2]+f[j-1][k]*a[j][i])%MOD; //选 a[j][i] 这个点
}
for(int j=n+1;j<=(n<<1);j++) ans=(ans+MOD-f[n][j])%MOD; //减去答案，注意取模
} printf("%lld",ans);
return 0;
}