题解：AT_arc204_a [ARC204A] Use Udon Coupon

· · 题解

观察基本条件。相当于是各实施 n 次操作 1 和操作 2。然后在任意时刻你已经实施的操作 2 次数不能大于操作 1 的次数。

参照 Iniaugoty 大佬的思路（最好先看一下他的题解，看懂就不用看我的了），把操作 1 想象成一条斜上的直线，操作 2 想象成斜下的直线。

由于每次我们 x 轴方向和 y 轴方向移动的距离相等，所以斜率也是相等的，只有斜上和斜下之分。把图画出来大概长这样。

注释：我这里要说一下，我画完图之后才发现自己画的不严谨，第一次操作只能是操作 1， 因此图像的第一个折线应该只能是斜下的。不过懒得重画了，领会精神即可。

图像画出来大概长成这个样子（蓝）。

题目中的条件 “将 C 替换为 \max(0, C - A_{i})“， 其实就相当于图像碰到 x 轴之后不继续往下，而是水平向右延申。

那么图像其实就长成这个样子（红）。

你发现，最右边那一段，红色的图像是比蓝色要长的。这长的一段距离，也就是蓝色图像在 x 轴以下的距离。

因为我们只考虑结束点的 y 值，也就是 C 的最终值，所以我们可以直接把蓝色图像向上平移。得到绿色图像。

绿色图像的结束点和红色图像的结束点的 y 值一样。

我们考虑到平移的距离其实就是蓝色最低点离 x 轴的距离，那么我们设它为 low。

由此表示绿色图像的最终点纵坐标，也就是红色图像的最终点纵坐标，也就是 C。

C = \sum_{i = 1}^{n} b_i - \sum_{i = 1}^{n} a_i + low = sumb_n - suma_n + low

然后把 C 代入题目中的不等式，解得

suma_n - sumb_n - R \leq low \leq suma_n - sumb_n - L

这个不等式容斥做一下就行。

然后我们就 dp 呗，计算已经实施了前 i 个操作 1， 前 j 个操作 2 ，并且满足限制条件的方案数。

小细节是，发现不满足限制条件要直接 continue 掉，也不能给后面转移。因为我们设 low 是全局的最小值，如果有小于它的值一定不合法。

#include <bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
constexpr int N = 5005, mod = 998244353;
int ans, n, l, r, L, R, suma[N], sumb[N], f[N][N], g[N][N];
inline void gm(int &x) {
    if(x >= mod) {
        x -= mod;
    }
}
signed main() {
    cin >> n >> L >> R;
    rep(i, 1, n) {
        cin >> suma[i];
        suma[i] += suma[i - 1];
    }
    rep(i, 1, n) {
        cin >> sumb[i];
        sumb[i] += sumb[i - 1];
    }
    l = sumb[n] - suma[n] - R, r = sumb[n] - suma[n] - L + 1;
    f[0][0] = g[0][0] = 1;
    rep(i, 1, n) {
        rep(j, 0, i) {
            if(sumb[j] - suma[i] < l) continue;
            if(j) {
                f[i][j] = f[i][j] + f[i][j - 1];
                gm(f[i][j]);
            }
            f[i][j] = f[i][j] + f[i - 1][j];
            gm(f[i][j]);

        }
    }
    rep(i, 1, n) {
        rep(j, 0, i) {
            if(sumb[j] - suma[i] < r) continue;
            if(j) {
                g[i][j] = g[i][j] + g[i][j - 1];
                gm(g[i][j]);
            }
            g[i][j] = g[i][j] + g[i - 1][j];
            gm(g[i][j]);
        }
    }
    cout << (f[n][n] - g[n][n] + mod) % mod;
    return 0;
}