2019 Emiya 家今天的饭 · 方案一逐列容斥 DP

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 4/5 · 共 2036 字

n 种烹饪法、m 种食材，a[i][j] = 法 i 配食材

2019
计数DP

正文

// CSP-S 2019 复赛 T4 · Emiya 家今天的饭（方案一：逐列容斥 DP）
// 原题：https://oj.yecheng.tv/p/CSPS2019D
// 题意：n 种烹饪法、m 种食材，a[i][j] = 法 i 配食材 j 的做法数。
//       合法方案：至少一道菜、每法至多一道、存在主食材出现次数
//       严格超过总菜数一半。求方案数 mod 998244353。
// 思路（经典容斥）：
//   合法 = 全部方案 − 非法。非法方案中"超标的食材"至多一种，因此
//   可以对每个食材列 c 单独计算"c 超标"的方案数再求和。
//   全部方案 = Π(rowSum_i + 1) − 1（每行选一道或不选）。
//   对列 c：dp[i][d] = 前 i 行、(选 c 次数 − 选其它次数) = d 的方案数。
//   d 每行只在 {-1, 0, +1} 变化，d ≥ 1 即 c 超标。
//   方案一保留完整 d 维（范围 [-n, n]），下标偏移 n。
// 复杂度：O(m · n^2)。
// 易错点：
//   1. d 下标 +n 防负；每列开始前 f[0][0+n] = 1、其余清零；
//   2. "选其它"的方案数 = rowSum_i − a[i][c]，取模防负；
//   3. 最后只累加 d ≥ 1 的 f[n][d]；total − illegal 防负。
#include <cstdio>
#include <cstring>
using namespace std;

const int MOD = 998244353;
int n, m;
int a[105][2005];
long long f[105][205];
long long rowSum[105];

int main() {
    freopen("meal.in", "r", stdin);
    freopen("meal.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            scanf("%d", &a[i][j]);
            rowSum[i] = (rowSum[i] + a[i][j]) % MOD;
        }
    long long total = 1;
    for (int i = 1; i <= n; i++) total = total * ((rowSum[i] + 1) % MOD) % MOD;
    total = (total - 1 + MOD) % MOD;
    long long illegal = 0;
    for (int c = 1; c <= m; c++) {
        memset(f, 0, sizeof(f));
        f[0][n] = 1;
        for (int i = 1; i <= n; i++)
            for (int d = -i; d <= i; d++) {
                long long w = f[i - 1][d + n];
                if (!w) continue;
                f[i][d + n] = (f[i][d + n] + w) % MOD;
                if (d + 1 + n <= 2 * n)
                    f[i][d + 1 + n] = (f[i][d + 1 + n] + w * a[i][c]) % MOD;
                long long others = (rowSum[i] - a[i][c] + MOD) % MOD;
                if (d - 1 + n >= 0)
                    f[i][d - 1 + n] = (f[i][d - 1 + n] + w * others) % MOD;
            }
        for (int d = 1; d <= n; d++)
            illegal = (illegal + f[n][d + n]) % MOD;
    }
    printf("%lld\n", (total - illegal + MOD) % MOD);
    return 0;
}

2019 Emiya 家今天的饭 · 方案一 逐列容斥 DP

正文

CSP-S 标程 · 复赛真题的其它内容

2019 Emiya 家今天的饭 · 方案一逐列容斥 DP