Emiya 家的饭 题解

题目分析

这道题要求统计满足特定条件的菜品搭配方案数：

1. 至少一道菜
2. 每道菜烹饪方法不同
3. 每种主要食材至多出现在一半的菜中

关键约束：

• 烹饪方法必须互不相同
• 主要食材使用次数不超过菜品数的一半
• 需要处理大规模组合计数

解题思路

核心观察

1. 容斥原理：总方案数减去不合法方案数
2. 主要矛盾：违反条件3意味着存在某种食材使用超过一半
3. 动态规划：对每种食材分别计算其超限的情况

算法设计

代码采用了容斥原理 + 动态规划的方法：

主要步骤：

1. 计算总方案数：不考虑食材限制的所有方案
2. 减去非法方案：对每种食材，计算其使用超过一半的方案数
3. 动态规划优化：使用差值DP高效计算非法方案

代码详解

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

constexpr int MAXN = 105, MAXM = 2005, MOD = 998244353;
int n, m, a[MAXN][MAXM], s[MAXN];
int f[MAXN][MAXN << 1], g[MAXN][MAXN] = {1};

signed main() {
    freopen("meal.in", "r", stdin);
    freopen("meal.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    
    cin >> n >> m;
    
    // 读入数据并计算每行的和
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            s[i] = (s[i] + a[i][j]) % MOD;
        }
    
    int ans = 0;
    
    // 计算总方案数（不考虑食材限制）
    // g[i][j] 表示前i行选j道菜的总方案数
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= n; j++)
            g[i][j] = (g[i - 1][j] + (j > 0 ? s[i] * g[i - 1][j - 1] % MOD : 0)) % MOD;
    
    // 累加所有非空方案
    for (int j = 0; j <= n; j++)
        ans = (ans + g[n][j]) % MOD;
    
    // 减去非法方案：某种食材使用超过一半
    for (int cur = 1; cur <= m; cur++) {
        memset(f, 0, sizeof(f));
        f[0][n] = 1;  // 初始状态，差值为0（用n作为偏移量）
        
        // f[i][j] 表示前i行，当前食材与其他食材的数量差为j-n的方案数
        for (int i = 1; i <= n; i++)
            for (int j = n - i; j <= n + i; j++) {
                f[i][j] = f[i - 1][j];  // 不选第i行
                // 选当前食材
                if (j > 0) f[i][j] = (f[i][j] + a[i][cur] * f[i - 1][j - 1] % MOD) % MOD;
                // 选其他食材
                f[i][j] = (f[i][j] + (s[i] - a[i][cur] + MOD) % MOD * f[i - 1][j + 1] % MOD) % MOD;
            }
        
        // 减去当前食材使用超过一半的方案
        for (int j = 1; j <= n; j++)
            ans = (ans - f[n][n + j] + MOD) % MOD;
    }
    
    // 减去空方案，输出结果
    cout << (ans - 1 + MOD) % MOD << '\n';
    return 0;
}

算法原理详解

1. 总方案数计算

g[i][j] 表示前i行选j道菜的总方案数：

• 不选第i行：g[i-1][j]
• 选第i行：s[i] * g[i-1][j-1]（s[i]是第i行所有食材方案和）

2. 非法方案计算

对于每种食材cur，计算其使用次数超过总菜数一半的方案数。

使用差值DP：f[i][j] 表示前i道菜中，食材cur的数量减去其他食材数量 = j - n。

状态转移：

• 不选第i道菜：f[i-1][j]
• 选食材cur：a[i][cur] * f[i-1][j-1]
• 选其他食材：(s[i]-a[i][cur]) * f[i-1][j+1]

3. 非法条件判断

食材cur使用超过一半 ⇔ 食材cur数量 > 其他食材数量总和
⇔ 差值 > 0 ⇔ j - n > 0 ⇔ j > n

所以非法方案数 = ∑_{j=n+1}^{2n} f[n][j]

4. 容斥原理

最终答案 = 总方案数 - 所有食材的非法方案数 - 空方案

复杂度分析

• 时间复杂度：O(n²m)，对每种食材进行O(n²)的DP
• 空间复杂度：O(n²)，DP数组大小

样例解析

样例1：

2 3
1 0 1
0 1 1

总方案数计算：

• 选1道菜：1+0+1 + 0+1+1 = 4
• 选2道菜：1×1 + 1×1 + 0×1 + ... = 3 总方案数 = 4 + 3 = 7

非法方案：检查每种食材超过一半的情况 最终答案 = 7 - 非法方案 - 1(空方案) = 3

关键技巧

1. 容斥原理：总方案减非法方案
2. 差值DP：用数量差表示状态，避免高维DP
3. 偏移量技巧：使用n作为差值0的偏移，避免负数下标
4. 模运算处理：正确处理负数和模运算

总结

这道题的解题亮点：

1. 问题转化：将复杂约束转化为容斥计数问题
2. 高效DP：使用差值DP在O(n²)时间内计算非法方案
3. 偏移技巧：巧妙处理差值可能为负的情况
4. 完整处理：考虑了所有边界情况和模运算

算法通过深入的组合数学分析和高效的动态规划设计，在O(n²m)时间内解决了这个复杂的计数问题，展示了处理组合约束问题的高级技巧。