洛谷题单指南-组合数学与计数-P5664 [CSP-S 2019] Emiya 家今天的饭

原题链接：https://www.luogu.com.cn/problem/P5664

题意解读：

Emiya 掌握 n 种烹饪方法和 m 种主要食材，用第 i 种烹饪方法和第 j 种食材可做 a[i][j] 道不同的菜。需选择若干道菜（至少 1 道），满足以下要求：

• 每道菜的烹饪方法互不相同（即每种烹饪方法最多选 1 道菜）；
• 每种主要食材的使用次数不超过总菜数 k 的一半（即 ≤ k / 2）。

求符合要求的方案数，结果对 998244353 取模。

解题思路：

1、容斥思想

对于每一种烹饪方法i，一共可以做出s[i] = a[i][1] + a[i][2] + ... + a[i][m]种菜。

根据约束，每一种烹饪方法只能选一种菜，但是还有一个约束是同一食材的菜不能超过总菜数的一半，这就不好直接选。

在第一个条件满足，第二个条件不满足的某一种不合法方案中，只可能有一个食材的菜数量超过总菜数的一半（如果有两个食材超过，总菜数就>k）。

因此，可以用容斥原理来计算：所有选菜的方案数 - 所有同一食材的菜超过半数的方案数

2、乘法原理计算所有选菜的方案数

当不考虑第二个约束条件，所有选菜的方案数就是在每一种烹饪方法里选，

每一种烹饪方法都有s[i] + 1中选法（含不选该烹饪方法的任何菜），注意至少要选一个菜，因此所有选菜方案数为：

(s[1]+1) * (s[2]+1) * ... * (s[n]+1) - 1 （减一是排除一个菜都不选的情况）

3、动态规划计算所有同一食材的菜超过半数的方案数

由于只会有一种食材的菜超量，不妨枚举超量的食材p

设f[i][j][t]表示前i种烹饪方式，一共选了j道菜，包含食材p的菜数量为t的方案数

根据定义，对于食材p，非法的方案数为所有t>j/2时的f[i][j][t]之和

状态转移方程为：

第i种烹饪方式一个菜都不选：f[i][j][t] = f[i-1][j][t]

第i种烹饪方式选非食材p的菜：f[i][j][t] = f[i-1][j-1][t] * (s[i] - a[i][p])

第i种烹饪方式选食材p的菜：f[i][j][t] = f[i-1][j-1][t-1] * a[i][p]

分析一下时间复杂度：

枚举所有的食材m，再枚举所有烹饪方式n，再枚举所有菜的数量n，再枚举某个食材的菜的数量n，总体为O(mn³)，不可行。

4、差值替换优化

f[i][j][t]中j和t存在的目的是为了比较t>j/2，不妨用一个d = t - (j - t)的差值来表示，也就是对于某个食材p，

f[i][d]表示前i个烹饪方式中，选了p食材的菜与没有选p食材的菜的数量的差值为d的方案数，

这样所有d>0的f[i][d]都是非法的方案，

由于d的取值范围变成了[-n, n]，可以加上n值进行修正，避免负数。

状态转移方程为(实际编程时注意d要加上修正值)：

第i种烹饪方式一个菜都不选：f[i][d] = f[i-1][d]

第i种烹饪方式选非食材p的菜：f[i][d] = f[i-1][d+1] * (s[i] - a[i][p])

第i种烹饪方式选食材p的菜：f[i][d] = f[i-1][d-1] * a[i][p]

分析一下时间复杂度：

枚举所有的食材m，再枚举所有烹饪方式n，再枚举所有选某个食材的菜的数量与没选的差值2n，总体为O(mn²)。

100分代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;const int N = 105, M = 2005, MOD = 998244353, OFFSET = 100;LL s[N], a[N][M], f[N][2 * N];
LL n, m, ans;//计算不考虑第二个约束条件，所有选菜的方案数
LL total()
{LL res = 1;for(int i = 1; i <= n; i++)res  = res * (s[i] + 1) % MOD;return res - 1;
}//计算违反第二个约束条件的选菜方案数
LL illegal()
{LL res = 0;for(int p = 1; p <= m; p++) //枚举不合法的食材{memset(f, 0, sizeof f);f[0][OFFSET] = 1; //初始状态for(int i = 1; i <= n; i++) //枚举烹饪方式{for(int d = -n; d <= n; d++) //枚举选食材p的菜的数量与不选食材p的菜的数量之差{//第i种烹饪方式一个菜都不选f[i][d + OFFSET] = (f[i][d + OFFSET] + f[i - 1][d + OFFSET]) % MOD;//第i种烹饪方式选非食材p的菜if(d + 1 + OFFSET >= 0 && d + 1 + OFFSET < 2 * N)f[i][d + OFFSET] = (f[i][d + OFFSET] + f[i - 1][d + 1 + OFFSET] * (s[i] - a[i][p])) % MOD;//第i种烹饪方式选食材p的菜if(d - 1 + OFFSET >= 0 && d - 1 + OFFSET < 2 * N)f[i][d + OFFSET] = (f[i][d + OFFSET] + f[i - 1][d - 1 + OFFSET] * a[i][p]) % MOD;}}for(int d = 1; d <= n; d++) //统计不合法方案数res = (res + f[n][d + OFFSET]) % MOD;}return res;
}int main()
{cin >> n >> m;for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++)cin >> a[i][j];for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++)s[i] = (s[i] + a[i][j]) % MOD;ans = total() - illegal();ans = (ans % MOD + MOD) % MOD;cout << ans << endl;return 0;
}