简答题 偏难
#22101

day2-1 Emiya家今天的饭

day2-1 Emiya家今天的饭


未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; using namespace std; const int MOD = 998244353; int main() {     int n, m;     cin &gt;&gt; n &gt;&gt; m;     vector&lt;vector&lt;int&gt;&gt; a(n, vector&lt;int&gt;(m));     for (int i = 0; i &lt; n; ++i) {         for (int j = 0; j &lt; m; ++j) {             cin &gt;&gt; a[i][j];         }     }     // 计算总方案数:所有选至少一道且烹饪方法不同的方案数     long long total = 1;     for (int i = 0; i &lt; n; ++i) {         int sum = 0;         for (int j = 0; j &lt; 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 &lt; m; ++j) {         // dp[i][d + n]表示前i道烹饪方法,j的数量比其他食材多d的方案数         vector&lt;vector&lt;int&gt;&gt; dp(n + 1, vector&lt;int&gt;(2 * n + 2, 0));         dp[0][n] = 1; // 初始状态:0道,差值为0         for (int i = 1; i &lt;= n; ++i) {             int sum_a = 0;             for (int k = 0; k &lt; 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 &lt;= 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 &lt;= 2 * n; ++pos) {             invalid = (invalid + dp[n][pos]) % MOD;         }     }     long long ans = (total - invalid + MOD) % MOD;     cout &lt;&lt; ans &lt;&lt; endl;     return 0; }</pre><p><br/></p>
解析

方法思路

1、总方案数计算:首先计算所有满足 “烹饪方法互不相同” 的方案数(至少选一道菜)。对于每道烹饪方法,可以选择其中一种食材或不选,因此总方案数为所有烹饪方法可选情况的乘积减 1(减去都不选的情况)。

2、非法方案数计算:对于每种食材,计算存在该食材使用次数超过一半的非法方案数。使用动态规划来跟踪每道烹饪方法选择后,该食材数量与其他食材数量的差值,从而判断是否超过一半。

3、结果计算:总合法方案数等于总方案数减去所有非法方案数的和,结果对 998244353 取模。

代码解释

1、输入处理:读取烹饪方法数n和食材数m,以及每道烹饪方法使用各食材的菜数。

2、总方案数计算:通过遍历每道烹饪方法,计算其可选情况的乘积,再减 1 得到至少选一道的总方案数。

3、非法方案数计算:对每种食材,使用动态规划跟踪其数量与其他食材数量的差值,统计差值大于 0 的情况(即该食材使用次数超过一半)。

4、结果计算:总合法方案数为总方案数减去所有非法方案数的和,确保结果为非负数后输出。

该方法通过动态规划高效处理了每种食材的非法情况,确保了时间复杂度和空间复杂度在合理范围内。