题目链接：Codeforces 1204 E

Natasha 最喜欢的数字是 $n$ 和 $1$，Sasha 最喜欢的数字是 $m$ 和 $-1$。某一天他们写下了长度为 $n + m$ 且包含恰好 $n$ 个 $1$ 和 $m$ 个 $-1$ 的所有可能的序列。对于每一个序列计算出它的最大前缀和（允许为空）；形式化地，我们定义 $f(a)$ 表示序列 $a_{1, \dots, l}(l \le 0)$ 的最大前缀和，那么有：

$$ f(a) = \max \left (0, \max _ {i = 1} ^ {l} \sum _ {j = 1} ^ {i} a_{j} \right ) $$

现在他们想要对于所有满足条件的序列，求出 $f(a)$ 的总和。答案对 $998244853$ 取模。

数据范围：$0 \le n, m \le 2000$。

Solution

弱化版

我们设 $f(i, j)$ 表示含有 $i$ 个 $1$ 和 $j$ 个 $-1$ 的所有序列的 $f(a)$ 之和。为了体现「前缀和」的性质，我们每次加入一个数字时不是加在序列的最后面，而是加在最前面。因为我们发现这样可以使新的数字对所有前缀和造成影响；否则无法计算最大前缀和是否被修改。

为了方便描述，我们定义 $g(i, j)$ 表示含有 $i$ 个 $1$ 和 $j$ 个 $-1$ 的序列的个数。显然有：

$$ g(i, j) = \binom {i + j} {i} $$

对于 $f$ 有转移：

$$ \begin {align*} f(i, j) + 1 \cdot g(i, j) & \rightarrow f(i + 1, j) \\ f(i, j) + (-1) \cdot (g(i, j) - h(i, j)) & \rightarrow f(i, j + 1) \end {align*} $$

第二个转移中的 $h(i, j)$ 是什么鬼？如果原序列的 $f(a) = 0$，那么在原序列最前面加上一个 $-1$ 后不会影响其 $f$ 值。这样一来我们就需要记录 $h(i, j)$ 表示含有 $i$ 个 $1$ 和 $j$ 个 $-1$ 的序列中最大前缀和为 $0$ 的方案数，其转移为（考虑在序列末尾加入新数字）：

$$ h(i, j) = \begin {cases} 1 & i = 0 \\ 0 & i > j \\ h(i - 1, j) + h(i, j - 1) & \text{otherwise.} \end {cases} $$

题外话：我们可以发现 $h$ 的定义和「卡特兰数」类似，则有 $h(i, j) = \binom {i + j} {j} - \binom {i + j} {j + 1}$。

时间复杂度：$\mathcal O(nm)$。

加强版

如果我们把数据范围加强到 $0 \le n, m \le 10 ^ {7}$ 呢？大毒瘤！

我们对于每种答案统计方案数。设最大前缀和为 $i$ 的方案数有 $f(i)$ 种，我们不妨对其做后缀和得到：最大前缀和不小于 $i$ 的方案数有 $g(i)$ 种。

我们参考卡特兰数的几何证明，将 $1$ 看做平面向量 $(1, 1)$、将 $-1$ 看做平面向量 $(1, -1)$，那么问题等价于：从点 $(0, 0)$ 出发到达点 $(n + m, n - m)$ 的所有路径中，经过直线 $y = i$ 的方案数。

对于 $i$ 分两种情况讨论：

1. 当 $0 \le i \le n - m$ 时，起点和终点在直线的两侧，则 $g(i) = \binom {n + m} {n}$。

2. 当 $n - m < i \le n$ 时，我们找到路径上第一个经过 $y = i$ 的点，将起点到这个点的路径通过 $y = i$ 对称，起点通过变换变成了 $(0, 2i)$。设路径上有 $x$ 个 $(1, 1)$ 和 $y$ 个 $(1, -1)$，列出方程：

   $$ \begin {cases} x + y = n + m \\ x - y = n - m - 2i \end {cases} $$

   得到 $x = n - i, y = m + i$，方案数 $g(i) = \binom {x + y} {x} = \binom {n + m} {n - i}$。

最终的答案为

$$ \sum _ {i = 0} ^ {n} i \cdot (g(i) - g(i + 1)) $$

时间复杂度：$\mathcal O(n + m + \log p)$。

Code

此处只给出加强版的代码。

#include <cstdio>

const int N = 2e7;
const int MOD = 998244853;

int n, m, fac[N + 5], ifac[N + 5], f[N + 5];

void add(int &x, int y) {
    (x += y) >= MOD && (x -= MOD);
}
void sub(int &x, int y) {
    (x -= y) < 0 && (x += MOD);
}
int add(int x) {
    return x >= MOD ? x - MOD : x;
}
int sub(int x) {
    return x < 0 ? x + MOD : x;
}
int pow(int x, int k) {
    int ans = 1;
    for (; k > 0; k >>= 1, x = 1LL * x * x % MOD) {
        if ((k & 1) == 1) ans = 1LL * ans * x % MOD;
    }
    return ans;
}
int inv(int x) {
    return pow(x, MOD - 2);
}
void init(int n) {
    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = 1LL * fac[i - 1] * i % MOD;
    ifac[n] = inv(fac[n]);
    for (int i = n; i >= 1; i--) ifac[i - 1] = 1LL * ifac[i] * i % MOD;
}
int binom(int n, int m) {
    if (n < m) return 0;
    return 1LL * fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;
}
int main() {
    scanf("%d%d", &n, &m);
    init(n + m);
    for (int i = 0; i <= n; i++) {
        f[i] = (i <= n - m ? binom(n + m, n) : binom(n + m, n - i));
    }
    int ans = 0;
    for (int i = 0; i <= n; i++) add(ans, 1LL * i * sub(f[i] - f[i + 1]) % MOD);
    printf("%d\n", ans);
    return 0;
}