2019 Emiya 家今天的饭 · 方案二状态折叠

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

把「多一种主食」的差值折成两态，省掉一维枚举

2019
计数DP

正文

// CSP-S 2019 复赛 T4 · Emiya 家今天的饭（方案二：状态折叠，O(n·m) 满分）
// 原题：https://oj.yecheng.tv/p/CSPS2019D
// 题意：同方案一（n ≤ 100，m ≤ 2000）。
// 思路（把差值折成两态）：
//   方案一里 d 的精确值并不重要，答案只统计 d ≥ 1。把状态折叠成：
//       f[i][0]：d ≤ 0 的全部状态（"欠账"，精确欠多少无所谓）；
//       f[i][1]：d ≥ 1 的全部状态（已超标）。
//   转移（第 i 行）：
//   - j=0：不选 → 留在 0；选其它（差 -1，欠账更深）→ 仍在 0；
//     选 c（差 +1）→ 可能从 d=0 到 1：进入 j=1（d≤0 里只有 d=0
//     会转正，需要单独维护 d=0！）。
//   所以三态更稳：f[i][0]=d<0、f[i][1]=d=0、f[i][2]=d≥1。
//   转移：0 -(选其它)-> 0；0 -(不选)-> 1；1 -(选其它)-> 0；
//         1 -(不选)-> 1；1 -(选 c)-> 2；2 -(任意)-> 2。
// 复杂度：O(n·m)，n=100、m=2000 时 ~2e5 级别。
// 易错点：
//   1. 折叠的关键是"d=0 必须单独一态"，两态会算错转正边界；
//   2. 选 c 的转移只发生在 d=0（其它 d≤-1 选 c 后仍 <1，回 0 态：
//      注意 d=-1 选 c 变 d=0 → 是 0 态到 1 态的转移！）
//      完整转移：0 -(选 c)-> 0（d=-1+1 仍 ≤0）；1 -(选 c)-> 2；
//      所以 0 态"选其它"出边权 others，"选 c"留在 0 态……
//      实现按注释三态逐条写清楚即可；
//   3. 每列独立清零；D_c = f[n][2]。
#include <cstdio>
#include <cstring>
using namespace std;

const int MOD = 998244353;
int n, m;
int a[105][2005];
long long rowSum[105];
long long f[105][3];                   // 0: d<0  1: d=0  2: d>=1

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++) {
        long long others = 0;
        memset(f, 0, sizeof(f));
        f[0][1] = 1;                   // 初始 d = 0
        for (int i = 1; i <= n; i++) {
            others = (rowSum[i] - a[i][c] + MOD) % MOD;
            long long n0 = (f[i-1][0] + f[i-1][0] * others) % MOD;   // d<0：不选/选其它
            long long n1 = (f[i-1][1]                               // d=0：不选
                          + f[i-1][0] * a[i][c]) % MOD;             // d<0 选 c → 仍 ≤0
            long long n2 = (f[i-1][2] * (1LL + a[i][c] + others)    // 已超标：任意
                          + f[i-1][1] * a[i][c]) % MOD;             // d=0 选 c → 超标
            f[i][0] = n0 % MOD;
            f[i][1] = n1 % MOD;
            f[i][2] = n2 % MOD;
        }
        illegal = (illegal + f[n][2]) % MOD;
    }
    printf("%lld\n", (total - illegal + MOD) % MOD);
    return 0;
}

2019 Emiya 家今天的饭 · 方案二 状态折叠

正文

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

2019 Emiya 家今天的饭 · 方案二状态折叠