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

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

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

OJ: luogu

题目 ID: P5664

难度:提高+/省选-

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

创建: 2026-06-20 07:35

更新: 2026-10-07 10:45

形式化题目

给定一个 $n \times m$ 的非负整数矩阵 $a$ ， $a_{i,j}$ 表示第 $i$ 种烹饪方法、第 $j$ 种食材能做的不同菜的数量。

要求选出一个非空方案，满足：

每种烹饪方法至多选一道菜（每行至多选一个）
设最终选了 $k$ 道菜，则每种食材出现的次数都不超过 $\lfloor k/2 \rfloor$

统计所有合法方案数，对 $998\,244\,353$ 取模。

暴力解法

思路

逐行枚举：对第 $i$ 行，要么不选，要么选某一种食材 $j$ （有 $a_{i,j}$ 种具体菜）。

枚举完所有行后，检查是否存在某种食材出现次数严格超过一半。若没有，则把该方案的方案数累入答案。

代码

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-06-20 07:35
 * update_at: 2026-10-01 20:09
 */
// brute.cpp：小数据暴力解，逐行枚举"不选"或"选某一种食材"，
// 到叶子节点检查是否存在某种食材严格超过一半。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

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

int n, m;
int a[MAXN][MAXM]; // 输入矩阵
int cnt[MAXM];     // cnt[j]：当前方案中食材 j 被选了多少次
ll ans;

// 模意义下加法
void add_mod(ll &x, ll y) {
    x += y;
    if (x >= MOD) {
        x -= MOD;
    }
}

// 检查当前方案是否合法：没有任何食材严格超过一半
bool check(int chosen) {
    for (int j = 1; j <= m; j++) {
        if (cnt[j] * 2 > chosen) {
            return false;
        }
    }
    return true;
}

// 逐行枚举：第 row 行要么不选，要么选食材 j（j 从 1 到 m）
void dfs(int row, int chosen, ll ways) {
    if (row > n) {
        if (chosen == 0) {
            return;
        }

        if (check(chosen)) {
            add_mod(ans, ways);
        }
        return;
    }

    // 不选第 row 行
    dfs(row + 1, chosen, ways);

    // 选第 row 行的食材 j
    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;
}

复杂度

时间： $O(2^n \cdot m)$ ，每行有"不选"和"选食材 $j$ "共 $m+1$ 种选择
空间： $O(m)$ ，只记录每种食材被选次数

瓶颈

枚举量随 $n$ 指数增长，只能处理 $n \leqslant 15$ 左右的小数据。

正解

思路

先不考虑"每种食材不能超过一半"的限制，计算总方案数，再扣掉坏方案（存在某种食材严格超过一半）。

总方案数：第 $i$ 行有 $1$ 种"不选"和 $\sum_j a_{i,j}$ 种"选"，所以总方案数为：

\prod_{i=1}^{n} \left(1 + \sum_{j=1}^{m} a_{i,j}\right) - 1

减一是去掉空方案。

坏方案计数：关键观察是——严格多数的食材至多只有一种。若两种食材都超过一半，则它们的出现次数之和大于总菜数，矛盾。

因此可以枚举哪一种食材 $p$ 是"严格多数者"，分别计数后求和。

固定食材 $p$ 后的三种选择

把每一行的选择分成三类：

对第 $i$ 行的处理	方案数	差值变化
不选	$1$	$0$
选食材 $p$	$a_{i,p}$	$+1$
选其它食材	$\sum_j a_{i,j} - a_{i,p}$	$-1$

定义 $\mathit{diff} =$ （选食材 $p$ 的次数） $-$ （选其它食材的次数）。

最终 $\mathit{diff} > 0$ 就意味着食材 $p$ 比其它所有食材加起来还多，即严格超过一半。

于是做一维 DP：

$dp[d]$ 表示当前差值为 $d$ 的方案数（ $d$ 用偏移量 $n+1$ 映射到非负下标）
每一行按上表做三种转移
最后把所有 $\mathit{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
111
112
113
114
115
116
117
118
119
120
121
122/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-06-20 07:35
 * update_at: 2026-10-01 20:09
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

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

int n, m;
int a[MAXN][MAXM]; // a[i][j]：第 i 种做法用食材 j 的方案数，值域 < MOD，用 int
ll row_sum[MAXN];  // 第 i 行所有食材方案数之和（模 MOD）
ll dp[MAXD];       // dp[d]：当前差值为 d 的方案数，d 用偏移量 offset = n+1 映射到非负下标
ll ndp[MAXD];      // 下一行滚动数组

// 模意义下加法：x = (x + y) % MOD
void add_mod(ll &x, ll y) {
    x += y;
    if (x >= MOD) {
        x -= MOD;
    }
}

// 统计"食材 food 成为严格多数"的坏方案数。
// diff = 选 food 的次数 - 选其它食材的次数，
// 最终 diff > 0 表示 food 严格超过一半。
ll 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));

        ll same = a[i][food];           // 选食材 food 的方案数
        ll other = row_sum[i] - same;   // 选非 food 食材的方案数
        if (other < 0) {
            other += MOD;
        }

        for (int d = left; d <= right; d++) {
            ll 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));
    }

    ll 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;
            }
        }
    }

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

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

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

    cout << ans << '\n';

    return 0;
}

复杂度

时间： $O(nm + mn^2)$ ，读入 $O(nm)$ ，枚举 $m$ 种食材各做一次 $O(n^2)$ 的 DP
空间： $O(nm)$ ，输入矩阵占主要空间，DP 数组 $O(n)$

总结

这题最关键的两步是：

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

一旦做到这一步，原本看起来像多维计数的问题，就被压成了一个很规整的一维 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 家今天的饭

目录

形式化题目

暴力解法

思路

代码

复杂度

瓶颈

正解

思路

固定食材 ppp 后的三种选择

代码

复杂度

总结

图示解析

固定食材 $p$ 后的三种选择