https://www.luogu.com.cn/problem/P5664
題意解讀：
Emiya 掌握 n 種烹飪方法和 m 種主要食材，用第 i 種烹飪方法和第 j 種食材可做 a[i][j]
- 每道菜的烹飪方法互不相同（即每種烹飪方法最多選 1 道菜）；
- 每種主要食材的使用次數不超過總菜數 k 的一半（即 ≤ k / 2）。
解題思路：
1、容斥思想
對於每一種烹飪方法i，一共可以做出s[i] = a[i][1] + a[i][2] + ... + a[i][m]種菜。
根據約束，每一種烹飪方法只能選一種菜，但是還有一個約束是同一食材的菜不能超過總菜數的一半，這就不好直接選。
在第一個條件滿足，第二個條件不滿足的某一種不合法方案中，只可能有一個食材的菜數量超過總菜數的一半（如果有兩個食材超過，總菜數就>k）。
因此，可以用容斥原理來計算：所有選菜的方案數 - 所有同一食材的菜超過半數的方案數
2、乘法原理計算所有選菜的方案數
當不考慮第二個約束條件，所有選菜的方案數就是在每一種烹飪方法裏選，
每一種烹飪方法都有s[i] + 1中選法（含不選該烹飪方法的任何菜），注意至少要選一個菜，因此所有選菜方案數為：
(s[1]+1) * (s[2]+1) * ... * (s[n]+1) - 1 （減一是排除一個菜都不選的情況）
3、動態規劃計算所有同一食材的菜超過半數的方案數
由於只會有一種食材的菜超量，不妨枚舉超量的食材p
設f[i][j][t]表示前i種烹飪方式，一共選了j道菜，包含食材p的菜數量為t的方案數
根據定義，對於食材p，非法的方案數為所有t>j/2時的f[i][j][t]之和
狀態轉移方程為：
第i種烹飪方式一個菜都不選：f[i][j][t] = f[i-1][j][t]
第i種烹飪方式選非食材p的菜：f[i][j][t] = f[i-1][j-1][t] * (s[i] - a[i][p])
第i種烹飪方式選食材p的菜：f[i][j][t] = f[i-1][j-1][t-1] * a[i][p]
分析一下時間複雜度：
枚舉所有的食材m，再枚舉所有烹飪方式n，再枚舉所有菜的數量n，再枚舉某個食材的菜的數量n，總體為O(mn3)，不可行。
4、差值替換優化
f[i][j][t]中j和t存在的目的是為了比較t>j/2，不妨用一個d = t - (j - t)的差值來表示，也就是對於某個食材p，
f[i][d]表示前i個烹飪方式中，選了p食材的菜與沒有選p食材的菜的數量的差值為d的方案數，
這樣所有d>0的f[i][d]都是非法的方案，
由於d的取值範圍變成了[-n, n]，可以加上n值進行修正，避免負數。
狀態轉移方程為(實際編程時注意d要加上修正值)：
第i種烹飪方式一個菜都不選：f[i][d] = f[i-1][d]
第i種烹飪方式選非食材p的菜：f[i][d] = f[i-1][d+1] * (s[i] - a[i][p])
第i種烹飪方式選食材p的菜：f[i][d] = f[i-1][d-1] * a[i][p]
f[i][d]取三種情況之和。
分析一下時間複雜度：
枚舉所有的食材m，再枚舉所有烹飪方式n，再枚舉所有選某個食材的菜的數量與沒選的差值2n，總體為O(mn2)。
100分代碼：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 105, M = 2005, MOD = 998244353, OFFSET = 100;
LL s[N], a[N][M], f[N][2 * N];
LL n, m, ans;
//計算不考慮第二個約束條件，所有選菜的方案數
LL total()
{
LL res = 1;
for(int i = 1; i <= n; i++)
res = res * (s[i] + 1) % MOD;
return res - 1;
}
//計算違反第二個約束條件的選菜方案數
LL illegal()
{
LL res = 0;
for(int p = 1; p <= m; p++) //枚舉不合法的食材
{
memset(f, 0, sizeof f);
f[0][OFFSET] = 1; //初始狀態
for(int i = 1; i <= n; i++) //枚舉烹飪方式
{
for(int d = -n; d <= n; d++) //枚舉選食材p的菜的數量與不選食材p的菜的數量之差
{
//第i種烹飪方式一個菜都不選
f[i][d + OFFSET] = (f[i][d + OFFSET] + f[i - 1][d + OFFSET]) % MOD;
//第i種烹飪方式選非食材p的菜
if(d + 1 + OFFSET >= 0 && d + 1 + OFFSET < 2 * N)
f[i][d + OFFSET] = (f[i][d + OFFSET] + f[i - 1][d + 1 + OFFSET] * (s[i] - a[i][p])) % MOD;
//第i種烹飪方式選食材p的菜
if(d - 1 + OFFSET >= 0 && d - 1 + OFFSET < 2 * N)
f[i][d + OFFSET] = (f[i][d + OFFSET] + f[i - 1][d - 1 + OFFSET] * a[i][p]) % MOD;
}
}
for(int d = 1; d <= n; d++) //統計不合法方案數
res = (res + f[n][d + OFFSET]) % MOD;
}
return res;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> a[i][j];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
s[i] = (s[i] + a[i][j]) % MOD;
ans = total() - illegal();
ans = (ans % MOD + MOD) % MOD;
cout << ans << endl;
return 0;
}