ARTICLE · 1133880

真题解析:P5664 [CSP-S 2019] Emiya 家今天的饭(容斥补集·超标食材唯一性·差值DP·滚动数组)

发布时间：2026-10-07 11:07:30 最近访问：2026-10-07 11:07:30

题目来源：洛谷 P5664 [CSP-S 2019] Emiya 家今天的饭

题目大意

Emiya 掌握 n 种烹饪方法、会使用 m 种主要食材。用第 i 种烹饪方法和第 j 种主要食材能做出 a[i][j] 道不同的菜。一道菜恰好由一种烹饪方法和一种主要食材做成。

现在要选出一个包含 k 道菜（k ≥ 1）的搭配方案，满足：

• 每道菜的烹饪方法互不相同（即每种烹饪方法至多贡献一道菜）；
• 每种主要食材在所选菜中出现的次数不超过 ⌊k/2⌋。

求满足条件的搭配方案数，对 998244353 取模。

数据范围：n ≤ 100，m ≤ 2000，0 ≤ a[i][j] ≤ 100（答案模 998244353，是质数）。

输入输出样例

2 31 0 10 1 1

3 31 2 34 5 06 0 0

样例 1 中每种烹饪方法至多做一道菜，合法方案恰好 3 种；样例 2 答案为 190。

考点梳理

考点	在本题里的作用
容斥原理（补集思想）	合法方案 = 全部方案 − 存在食材超半数的方案
超标食材唯一性	k 道菜里不可能有两种食材同时超过 k/2，故可逐食材分开统计、直接相加
组合计数（乘法原理）	每种烹饪方法独立选择「不做菜」或「做一道」，总方案数为 ∏(1+s[i])
差值 DP	只记录「用食材 c 的菜数 − 不用食材 c 的菜数」这一差值
滚动数组	每处理一种方法只依赖上一层，空间降到 O(n)
取模安全	减法后 +MOD 再取模，s[i] − a[i][c] 可能为负

解题思路

一、先算「烹饪方法互不相同」的全部方案

只保留「每道菜烹饪方法互不相同」这一个条件时，每种烹饪方法 i 的选择是独立的：不做菜有 1 种，做一道菜有 s[i] = Σ a[i][j] 种。由乘法原理，允许全不做的总方案数为：

all = ∏(1 + s[i]) − 1

减去的 1 是「所有烹饪方法都不做菜」的空方案（题目要求 k ≥ 1）。

二、用容斥扣掉「某种食材超过半数」的非法方案

关键在于一个结构性质：超标的食材至多只有一种。设总菜数为 k，若食材 A、B 都超过 k/2，则二者之和大于 k，与总菜数恰为 k 矛盾。

所以非法方案里恰好有一种食材超标，不同食材对应的非法集合两两不相交。我们可以枚举超标食材 c，分别统计「食材 c 超标」的方案数 bad[c]，直接相加即为全部非法方案数。

三、固定食材 c，用差值 DP 统计超标方案

判断食材 c 是否超标，并不需要记录每种食材各做了多少，只需一个差值：

d =（用食材 c 的菜数）−（用其它食材的菜数）

总菜数为 k 时，「c 超过一半」等价于 count[c] > k − count[c]，即 d > 0。

设 dp[d] 表示处理完若干烹饪方法后差值为 d 的方案数，差值范围为 [−n, n]，存数组时统一加偏移量 n，初始 dp[0] = 1。对第 i 种烹饪方法，有三种转移：

• 不做菜：差值不变，方案数乘 1；
• 做食材 c 的菜：差值加一，方案数乘 a[i][c]；
• 做其它食材的菜：差值减一，方案数乘 s[i] − a[i][c]。

处理完所有方法后，所有 d > 0 的 dp[d] 之和就是 bad[c]。

四、汇总答案

把每个食材的 bad[c] 累加成 invalid，最终：

ans = (all − invalid) mod 998244353

值得注意的是，用差值 d 这一个数就完整表达了「是否超标」所需的全部信息，从而让每种食材的统计都能在 O(n²) 内完成。

参考代码

#include <bits/stdc++.h>using namespace std;const long long MOD = 998244353;const int N = 105, M = 2005;int n, m;long long a[N][M];long long s[N];long long dp[2 * N + 5];long long ndp[2 * N + 5];int main(){    scanf("%d%d", &n, &m);    for (int i = 1; i <= n; i++)        for (int j = 1; j <= m; j++) {            scanf("%lld", &a[i][j]);            a[i][j] %= MOD;            s[i] = (s[i] + a[i][j]) % MOD;        }    // 全部非空方案：prod(1 + s[i]) - 1    long long total = 1;    for (int i = 1; i <= n; i++) total = total * ((1 + s[i]) % MOD) % MOD;    total = (total - 1 + MOD) % MOD;    // 减去不合法的：某种食材出现次数超过一半    long long invalid = 0;    int off = n;    for (int c = 1; c <= m; c++) {        memset(dp, 0, sizeof(dp));        dp[off] = 1;        for (int i = 1; i <= n; i++) {            long long ac = a[i][c];            long long other = (s[i] - ac + MOD) % MOD;            memset(ndp, 0, sizeof(ndp));            for (int d = -i; d <= i; d++) {                int idx = off + d;                long long v = dp[idx];                if (v == 0) continue;                ndp[idx] = (ndp[idx] + v) % MOD;                if (idx + 1 <= 2 * off) ndp[idx + 1] = (ndp[idx + 1] + v * ac) % MOD;                if (idx - 1 >= 0) ndp[idx - 1] = (ndp[idx - 1] + v * other) % MOD;            }            memcpy(dp, ndp, sizeof(dp));        }        for (int d = 1; d <= n; d++) invalid = (invalid + dp[off + d]) % MOD;    }    long long ans = (total - invalid + MOD) % MOD;    printf("%lld\n", ans);    return 0;}

复杂度分析

• 时间：外层枚举超标食材 O(m)，每个食材内做 O(n) 种方法、每种方法枚举 O(n) 个差值，单食材 O(n²)，总复杂度 O(n²m)。n ≤ 100、m ≤ 2000 时约为 2 × 10⁷ 次操作。
• 空间：滚动数组只需 O(n) 存差值状态，加上 a 矩阵（105 × 2005）与 s 数组，整体约 O(nm + n)。