T2-20 Emiya 家今天的饭

题意理解

• $n$ 种烹饪方法，$m$ 种食材
• $a_{i,j}$ 表示用方法 $i$ 和食材 $j$ 能做的不同菜的数量
• 约束：
  1. 至少做 1 道菜
  2. 每道菜的烹饪方法互不相同（每行最多选 1 道）
  3. 每种食材最多在一半的菜中使用

---

思路分析

容斥原理

合法方案 = 满足条件 1,2 的方案 - 违反条件 3 的方案

Step 1：计算满足条件 1,2 的总方案数

每行要么不选，要么选一道菜。设 $sum_i = \\sum_{j=1}^{m} a_{i,j}$

$$\text{总方案} = \prod_{i=1}^{n}(sum_i + 1) - 1$$

（减 1 是去掉一道都不选的情况）

Step 2：计算违反条件 3 的方案数

关键观察：如果某种食材超过一半，最多只有一种食材会超过一半。

所以：不合法方案 $= \sum_{j=1}^{m}$ (食材 $j$ 超过一半的方案数)

针对固定食材 $j$ 的 DP：

设选了 $k$ 道菜，其中 $c$ 道使用食材 $j$。要求 $c > k/2$，即 $c > k - c$。

定义 $diff = c - (k-c)$ = 使用食材 $j$ 的菜数 - 不使用食材 $j$ 的菜数

要求 $diff \geq 1$。

设 $dp[i][d]$ 表示考虑前 $i$ 种烹饪方法，$diff = d$ 的方案数。

转移：

• 不选第 $i$ 行：$dp[i][d] \mathrel{+}= dp[i-1][d]$
• 选第 $i$ 行的食材 $j$：$dp[i][d] \mathrel{+}= dp[i-1][d-1] \times a_{i,j}$（diff 增加 1）
• 选第 $i$ 行的其他食材：$dp[i][d] \mathrel{+}= dp[i-1][d+1] \times (sum_i - a_{i,j})$（diff 减少 1）

由于 $d$ 可能为负，加偏移量 $n$。最终食材 $j$ 的不合法方案 $= \sum_{d=1}^{n} dp[n][d+n]$

复杂度： $O(m \cdot n^2)$

---

参考代码

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;  // 模数
const int MAXN = 105;       // 烹饪方法数上限
const int MAXM = 2005;      // 食材数上限

int n, m;                   // 烹饪方法数、食材数
long long a[MAXN][MAXM];    // a[i][j]表示方法i食材j的菜数
long long sum[MAXN];        // sum[i]表示第i种方法的所有菜数之和
long long dp[MAXN][MAXN * 2];  // dp[i][d+n]表示前i行diff=d的方案数

int main() {
    cin >> n >> m;  // 读入烹饪方法数和食材数
    
    for (int i = 1; i <= n; i++) {  // 读入每种方法每种食材的菜数
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            sum[i] = (sum[i] + a[i][j]) % MOD;  // 计算每行的总和
        }
    }
    
    // Step 1: 计算满足条件1,2的总方案数
    long long total = 1;
    for (int i = 1; i <= n; i++) {  // 每行可选可不选
        total = total * (sum[i] + 1) % MOD;
    }
    total = (total - 1 + MOD) % MOD;  // 减去一道都不选的情况
    
    // Step 2: 计算违反条件3的方案数（用容斥）
    long long bad = 0;
    
    for (int j = 1; j <= m; j++) {  // 枚举超过一半的食材j
        memset(dp, 0, sizeof(dp));  // 清空DP数组
        dp[0][n] = 1;  // 初始状态：diff=0（加偏移量n）
        
        for (int i = 1; i <= n; i++) {  // 枚举烹饪方法
            long long other = (sum[i] - a[i][j] + MOD) % MOD;  // 第i行不选食材j的菜数
            
            for (int d = 0; d <= 2 * n; d++) {  // 枚举diff（加偏移后的范围）
                dp[i][d] = dp[i - 1][d];  // 不选第i行
                if (d > 0) {  // 选第i行的食材j，diff增加1
                    dp[i][d] = (dp[i][d] + dp[i - 1][d - 1] * a[i][j]) % MOD;
                }
                if (d < 2 * n) {  // 选第i行的其他食材，diff减少1
                    dp[i][d] = (dp[i][d] + dp[i - 1][d + 1] * other) % MOD;
                }
            }
        }
        
        for (int d = 1; d <= n; d++) {  // diff >= 1 表示食材j超过一半
            bad = (bad + dp[n][d + n]) % MOD;  // 累加不合法方案
        }
    }
    
    // 合法方案 = 总方案 - 不合法方案
    long long ans = (total - bad + MOD) % MOD;
    cout << ans << endl;
    
    return 0;
}