题意理解
* nnn 种烹饪方法，mmm 种食材
* ai,ja_{i,j}ai,j 表示用方法 iii 和食材 jjj 能做的不同菜的数量
* 约束：
1. 至少做 1 道菜
2. 每道菜的烹饪方法互不相同（每行最多选 1 道）
3. 每种食材最多在一半的菜中使用
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
思路分析
容斥原理
合法方案 = 满足条件 1,2 的方案 - 违反条件 3 的方案
Step 1：计算满足条件 1,2 的总方案数
每行要么不选，要么选一道菜。设 sumi=sumj=1mai,jsum_i = \\sum_{j=1}^{m} a_{i,j}sumi =sumj=1m ai,j
总方案=∏i=1n(sumi+1)−1\text{总方案} = \prod_{i=1}^{n}(sum_i + 1) - 1 总方案=i=1∏n (sumi +1)−1
（减 1 是去掉一道都不选的情况）
Step 2：计算违反条件 3 的方案数
关键观察：如果某种食材超过一半，最多只有一种食材会超过一半。
所以：不合法方案 =∑j=1m= \sum_{j=1}^{m}=∑j=1m (食材 jjj 超过一半的方案数)
针对固定食材 jjj 的 DP：
设选了 kkk 道菜，其中 ccc 道使用食材 jjj。要求 c>k/2c > k/2c>k/2，即 c>k−cc > k - cc>k−c。
定义 diff=c−(k−c)diff = c - (k-c)diff=c−(k−c) = 使用食材 jjj 的菜数 - 不使用食材 jjj 的菜数
要求 diff≥1diff \geq 1diff≥1。
设 dp[i][d]dp[i][d]dp[i][d] 表示考虑前 iii 种烹饪方法，diff=ddiff = ddiff=d 的方案数。
转移：
* 不选第 iii 行：dp[i][d]+=dp[i−1][d]dp[i][d] \mathrel{+}= dp[i-1][d]dp[i][d]+=dp[i−1][d]
* 选第 iii 行的食材 jjj：dp[i][d]+=dp[i−1][d−1]×ai,jdp[i][d] \mathrel{+}= dp[i-1][d-1] \times a_{i,j}dp[i][d]+=dp[i−1][d−1]×ai,j （diff 增加 1）
* 选第 iii 行的其他食材：dp[i][d]+=dp[i−1][d+1]×(sumi−ai,j)dp[i][d] \mathrel{+}= dp[i-1][d+1] \times (sum_i - a_{i,j})dp[i][d]+=dp[i−1][d+1]×(sumi −ai,j )（diff 减少 1）
由于 ddd 可能为负，加偏移量 nnn。最终食材 jjj 的不合法方案 =∑d=1ndp[n][d+n]= \sum_{d=1}^{n} dp[n][d+n]=∑d=1n dp[n][d+n]
复杂度： O(m⋅n2)O(m \cdot n^2)O(m⋅n2)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
参考代码
