简答题
偏难
#22101
day2-1 Emiya家今天的饭
day2-1 Emiya家今天的饭



答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <iostream>
#include <vector>
using namespace std;
const int MOD = 998244353;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> a[i][j];
}
}
// 计算总方案数:所有选至少一道且烹饪方法不同的方案数
long long total = 1;
for (int i = 0; i < n; ++i) {
int sum = 0;
for (int j = 0; j < m; ++j) {
sum = (sum + a[i][j]) % MOD;
}
total = total * (sum + 1) % MOD; // 每道可选择任意食材或不选
}
total = (total - 1 + MOD) % MOD; // 减去都不选的情况
long long invalid = 0;
// 对每种食材j,计算非法方案数(该食材使用次数超过一半)
for (int j = 0; j < m; ++j) {
// dp[i][d + n]表示前i道烹饪方法,j的数量比其他食材多d的方案数
vector<vector<int>> dp(n + 1, vector<int>(2 * n + 2, 0));
dp[0][n] = 1; // 初始状态:0道,差值为0
for (int i = 1; i <= n; ++i) {
int sum_a = 0;
for (int k = 0; k < m; ++k) {
sum_a = (sum_a + a[i - 1][k]) % MOD;
}
int aj = a[i - 1][j];
int others = (sum_a - aj + MOD) % MOD;
// 遍历前i-1道的所有可能差值
for (int d = -(i - 1); d <= i - 1; ++d) {
int pos = d + n;
if (dp[i - 1][pos] == 0) continue;
// 不选当前烹饪方法
dp[i][pos] = (dp[i][pos] + dp[i - 1][pos]) % MOD;
// 选当前烹饪方法的j食材
dp[i][pos + 1] = (dp[i][pos + 1] + (long long)dp[i - 1][pos] * aj) % MOD;
// 选当前烹饪方法的非j食材
dp[i][pos - 1] = (dp[i][pos - 1] + (long long)dp[i - 1][pos] * others) % MOD;
}
}
// 统计差值大于0的情况(j的数量超过一半)
for (int pos = n + 1; pos <= 2 * n; ++pos) {
invalid = (invalid + dp[n][pos]) % MOD;
}
}
long long ans = (total - invalid + MOD) % MOD;
cout << ans << endl;
return 0;
}</pre><p><br/></p>
解析
方法思路
1、总方案数计算:首先计算所有满足 “烹饪方法互不相同” 的方案数(至少选一道菜)。对于每道烹饪方法,可以选择其中一种食材或不选,因此总方案数为所有烹饪方法可选情况的乘积减 1(减去都不选的情况)。
2、非法方案数计算:对于每种食材,计算存在该食材使用次数超过一半的非法方案数。使用动态规划来跟踪每道烹饪方法选择后,该食材数量与其他食材数量的差值,从而判断是否超过一半。
3、结果计算:总合法方案数等于总方案数减去所有非法方案数的和,结果对 998244353 取模。
代码解释
1、输入处理:读取烹饪方法数n和食材数m,以及每道烹饪方法使用各食材的菜数。
2、总方案数计算:通过遍历每道烹饪方法,计算其可选情况的乘积,再减 1 得到至少选一道的总方案数。
3、非法方案数计算:对每种食材,使用动态规划跟踪其数量与其他食材数量的差值,统计差值大于 0 的情况(即该食材使用次数超过一半)。
4、结果计算:总合法方案数为总方案数减去所有非法方案数的和,确保结果为非负数后输出。
该方法通过动态规划高效处理了每种食材的非法情况,确保了时间复杂度和空间复杂度在合理范围内。