[CSP-S 2019] Emiya 家今天的饭

GitHub 跳转原题关系图返回列表

先算每种做法任选或不选的总方案数，再按食材枚举严格多数者，用差值 DP 统计坏方案并从总数中扣掉。

OJ: luogu

题目 ID: P5664

难度:提高+/省选-

标签:动态规划容斥组合计数计数dp思维

日期: 2026-06-20 07:35

题意

我们要从这些菜里选出一个方案。

因为同一种烹饪方法不能重复，所以每一行最多选一道菜；如果选了第 i 行的第 j 列，就有 a[i][j] 种不同的具体菜可选。

设最终一共选了 k 道菜，那么题目的限制是：每种食材出现次数都不能超过 floor(k/2)。
换句话说，不能存在某种食材严格超过一半。

需要统计所有合法方案数，答案对 998244353 取模。

思路

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

const int MAXN = 15;
const int MAXM = 15;
const i64 MOD = 998244353LL;

int n, m;
int a[MAXN][MAXM];
int cnt[MAXM];
i64 ans;

// 朴素暴力：
// 每种做法枚举“不选”或“选哪一种食材”，
// 到叶子时再检查是否存在某种食材超过了一半。
void dfs(int row, int chosen, i64 ways) {
    if (row > n) {
        if (chosen == 0) {
            return;
        }

        for (int j = 1; j <= m; j++) {
            if (cnt[j] * 2 > chosen) {
                return;
            }
        }

        ans += ways;
        ans %= MOD;
        return;
    }

    dfs(row + 1, chosen, ways);

    for (int j = 1; j <= m; j++) {
        if (a[row][j] == 0) {
            continue;
        }

        cnt[j]++;
        dfs(row + 1, chosen + 1, ways * a[row][j] % MOD);
        cnt[j]--;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }

    dfs(1, 0, 1);
    cout << ans << '\n';

    return 0;
}

这个暴力会逐行枚举：

不选这一行
或者选这一行的某一种食材

最后统计每种食材出现次数，检查是否合法。它适合做小数据对拍，但显然不能处理 n=100,m=2000。

所以我们换个角度：先数总方案，再扣掉坏方案。

不考虑“某种食材不能超过一半”时，第 i 行有：

1 种不选
sum_j a[i][j] 种选法

因此总方案数就是：

prod_i (1 + sum_j a[i][j]) - 1

这里减一是去掉空方案。

接下来只需要统计坏方案：也就是存在某种食材 p 出现次数严格大于一半。

注意一个关键事实：严格多数的食材至多只有一种。
因为如果两种食材都超过一半，它们的出现次数和就会大于总菜数，矛盾。

所以可以直接枚举哪一种食材是“严格多数者”，分别计数后求和。

固定一种食材后的三种选择

这张表把“固定食材 p 后的一行转移”压成了三类：

对第 `i` 行的处理	方案数	差值 `diff` 的变化
不选	`1`	`0`
选食材 `p`	`a[i][p]`	`+1`
选其它食材	`sum_j a[i][j] - a[i][p]`	`-1`

其中我们定义：

diff = 选了多少道食材 p - 选了多少道其它食材

最后只要 diff > 0，就说明食材 p 比其它所有食材加起来还多，也就是它严格超过了一半。

于是可以做一维 DP：

dp[d] 表示当前差值为 d 的方案数
每一行按上表做三种转移
最后把所有 diff > 0 的状态加起来，就是“食材 p 成为严格多数”的坏方案数

把所有食材的坏方案数加起来，再从总方案数里减掉，就是答案。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

const int MAXN = 105;
const int MAXM = 2005;
const int MAXD = MAXN * 2 + 5;
const i64 MOD = 998244353LL;

int n, m;
int a[MAXN][MAXM];
int row_sum[MAXN];
i64 dp[MAXD], ndp[MAXD];

void add_mod(i64 &x, i64 y) {
    x += y;
    if (x >= MOD) {
        x -= MOD;
    }
}

i64 count_bad_for_food(int food) {
    int offset = n + 1;
    int left = offset;
    int right = offset;

    memset(dp, 0, sizeof(dp));
    dp[offset] = 1;

    for (int i = 1; i <= n; i++) {
        memset(ndp, 0, sizeof(ndp));

        int same = a[i][food];
        int other = row_sum[i] - same;
        if (other < 0) {
            other += MOD;
        }

        for (int d = left; d <= right; d++) {
            i64 cur = dp[d];
            if (cur == 0) {
                continue;
            }

            // 第 i 种做法不选。
            add_mod(ndp[d], cur);

            // 选一个食材是 food 的菜，差值 +1。
            if (same != 0) {
                add_mod(ndp[d + 1], cur * same % MOD);
            }

            // 选一个食材不是 food 的菜，差值 -1。
            if (other != 0) {
                add_mod(ndp[d - 1], cur * other % MOD);
            }
        }

        left--;
        right++;
        memcpy(dp, ndp, sizeof(dp));
    }

    i64 ans = 0;
    for (int d = offset + 1; d <= right; d++) {
        add_mod(ans, dp[d]);
    }

    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            row_sum[i] += a[i][j];
            if (row_sum[i] >= MOD) {
                row_sum[i] -= MOD;
            }
        }
    }

    // 不考虑“某种食材不能超过一半”时：
    // 每种做法要么不选，要么任选一种食材做一道菜。
    i64 total = 1;
    for (int i = 1; i <= n; i++) {
        total = total * (row_sum[i] + 1LL) % MOD;
    }
    total = (total - 1 + MOD) % MOD; // 去掉空方案

    // 枚举哪一种食材成为“严格多数”，把所有坏方案扣掉。
    i64 bad = 0;
    for (int food = 1; food <= m; food++) {
        add_mod(bad, count_bad_for_food(food));
    }

    i64 ans = (total - bad) % MOD;
    if (ans < 0) {
        ans += MOD;
    }

    cout << ans << '\n';

    return 0;
}

复杂度

枚举行和列读入： $O(nm)$
枚举每种食材做差值 DP： $O(mn^2)$
空间复杂度： $O(nm)$

总结

这题最关键的两步是：

把“每种食材都不能超过一半”改写成“不能存在严格多数食材”
固定一个候选多数食材后，把所有其它食材合并成一类，只维护两边数量差

一旦做到这一步，原本看起来像多维计数的问题，就被压成了一个很规整的一维 DP。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P5664 [CSP-S 2019] Emiya 家今天的饭

题目描述

Emiya 是个擅长做菜的高中生，他共掌握 $n$ 种烹饪方法，且会使用 $m$ 种主要食材做菜。为了方便叙述，我们对烹饪方法从 $1 \sim n$ 编号，对主要食材从 $1 \sim m$ 编号。

Emiya 做的每道菜都将使用恰好一种烹饪方法与恰好一种主要食材。更具体地，Emiya 会做 $a_{i,j}$ 道不同的使用烹饪方法 $i$ 和主要食材 $j$ 的菜（ $1 \leq i \leq n$ 、 $1 \leq j \leq m$ ），这也意味着 Emiya 总共会做 $\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m} a_{i,j}$ 道不同的菜。

Emiya 今天要准备一桌饭招待 Yazid 和 Rin 这对好朋友，然而三个人对菜的搭配有不同的要求，更具体地，对于一种包含 $k$ 道菜的搭配方案而言：

Emiya 不会让大家饿肚子，所以将做至少一道菜，即 $k \geq 1$
Rin 希望品尝不同烹饪方法做出的菜，因此她要求每道菜的烹饪方法互不相同
Yazid 不希望品尝太多同一食材做出的菜，因此他要求每种主要食材至多在一半的菜（即 $\lfloor \frac{k}{2} \rfloor$ 道菜）中被使用

这里的 $\lfloor x \rfloor$ 为下取整函数，表示不超过 $x$ 的最大整数。

这些要求难不倒 Emiya，但他想知道共有多少种不同的符合要求的搭配方案。两种方案不同，当且仅当存在至少一道菜在一种方案中出现，而不在另一种方案中出现。

Emiya 找到了你，请你帮他计算，你只需要告诉他符合所有要求的搭配方案数对质数 $998,244,353$ 取模的结果。

输入格式

第 1 行两个用单个空格隔开的整数 $n,m$ 。

第 2 行至第 $n + 1$ 行，每行 $m$ 个用单个空格隔开的整数，其中第 $i + 1$ 行的 $m$ 个数依次为 $a_{i,1}, a_{i,2}, \cdots, a_{i,m}$ 。

输出格式

仅一行一个整数，表示所求方案数对 $998,244,353$ 取模的结果。

输入输出样例 #1

输入 #1

text

输出 #1

text

输入输出样例 #2

输入 #2

text

输出 #2

text

输入输出样例 #3

输入 #3

text

输出 #3

text

说明/提示

【样例 1 解释】

由于在这个样例中，对于每组 $i, j$ ，Emiya 都最多只会做一道菜，因此我们直接通过给出烹饪方法、主要食材的编号来描述一道菜。

符合要求的方案包括：

做一道用烹饪方法 1、主要食材 1 的菜和一道用烹饪方法 2、主要食材 2 的菜
做一道用烹饪方法 1、主要食材 1 的菜和一道用烹饪方法 2、主要食材 3 的菜
做一道用烹饪方法 1、主要食材 3 的菜和一道用烹饪方法 2、主要食材 2 的菜

因此输出结果为 $3 \bmod 998,244,353 = 3$ 。需要注意的是，所有只包含一道菜的方案都是不符合要求的，因为唯一的主要食材在超过一半的菜中出现，这不满足 Yazid 的要求。

【样例 2 解释】

Emiya 必须至少做 $2$ 道菜。

做 $2$ 道菜的符合要求的方案数为 $100$ 。

做 $3$ 道菜的符合要求的方案数为 $90$ 。

因此符合要求的方案数为 $100 + 90 = 190$ 。

【数据范围】

::cute-table{tuack}

测试点编号	$n=$	$m=$	$a_{i,j}<$
$1$	$2$	$2$	$2$
$2$	^	$3$	^
$3$	$5$	$2$	^
$4$	^	$3$	^
$5$	$10$	$2$	^
$6$	^	$3$	^
$7$	$10$	$2$	$1000$
$8$	^	$3$	^
$9\sim 12$	$40$	$2$	^
$13\sim16$	^	$3$	^
$17\sim21$	^	$500$	^
$22\sim25$	$100$	$2000$	$998,244,353$

对于所有测试点，保证 $1 \leq n \leq 100$ ， $1 \leq m \leq 2000$ ， $0 \leq a_{i,j} \lt 998,244,353$ 。

[CSP-S 2019] Emiya 家今天的饭

目录

题意

思路

固定一种食材后的三种选择

代码

复杂度

总结

一图流解析