题解 CF1204E 【Natasha, Sasha and the Prefix Sums】

· · 题解

题意

求所有只有 n 个 1 和 m 个 -1 的序列最大前缀和的总和。(n,\,m \leq 2000)

解题思路

设 f_i 为最大前缀和等于 i 的序列数量，答案即为 \sum\limits_{i=0}^{n}i \times f_i 。恰好等于 i 比较难控制，不妨先求出 g_i 为最大前缀和大于等于 i 的序列数量，差分得到 f_i 。或者粗暴一些：\sum\limits_{i=0}^{n}i \times f_i = \sum\limits_{i=0}^n \sum\limits_{j=1}^{i} f_i = \sum\limits_{i=1}^{n}\sum\limits_{j=i}^{n}f_i = \sum\limits_{i=1}^{n} g_i 。

下一步我沿用了 P1641 字符串生成 里的经典套路。将 1 看成位移向量 (1,\,1) ，-1 看成位移向量 (1,\,-1) ，显然所有序列一一对应了起点 (0,\,0) 到终点 (n + m,\,n - m) 的所有路径。

正如下图，是序列 \{1,\,-1,\,1,\,1,\,-1,\,-1,\,-1,\,1\} 对应的一条路径：

而最大前缀和大于等于 i ，等价于路径要与一条 y = i 的直线有交。乍一看毫无规律而无从下手，要是路径的起点和终点分别在直线的两侧，只要是合法的路径就一定与 y = i 有交，直接组合数求出 g_i = \binom{n+m}{n} 。

如果起点和终点在直线同侧怎么办？强行把起点移到另一边去！不妨设置新的起点 (0,\,2i) ，此时我们观察它到 (n + m,\,n - m) 的路径，因为在异侧，路径与 y = i 一定有交。

接下来的转换将数形结合的精粹表现得淋漓尽致：我们找到路径与 y = i 的第一个交点，将起点到交点这一部分的路径以 y = i 为中心向下翻！这不，新的起点一时间又变到了老的起点，翻转之后的整条路径也是老的起点到终点的一条合法路径，但神奇的是，它一定与 y = i 相交！

想想看，这样的翻转是不是可以把老的路径中与 y = i 相交的一一对应到了新的路径？而数量也是一个组合数就能了结的。

放个图稍加体会：

最后一步，(0,\,2i) 到 (n + m,\,n - m) 有多少合法路径？我们设上移了 x 步，下移了 y 步，列得：

\left\{\begin{aligned}x+y &= n + m - 0\\x-y &= n - m - 2i\end{aligned}\right.

故 x = n - i,\ y = m + i 。g_i = \binom{x+y}{x} = \binom{n+m}{n-i} 。

总结一下：

\left\{\begin{aligned}g_i &= \binom{n+m}{n} \quad (i \leq n - m) \\ g_i &= \binom{n+m}{n-i} \quad (i \geq n - m) \end{aligned}\right.

线性预处理阶乘及逆元，注意坑爹的模数，我们用 O(n + m) 的复杂度完成了此题。

代码实现

惊了，现在题解不贴代码过不了审？？

#include <bits/stdc++.h>

const int mod = 998244853;

inline int add(int x, int y) { return x + y >= mod ? x + y - mod : x + y; }
inline int sub(int x, int y) { return x - y >= 0 ? x - y : x - y + mod; }
inline int power(int x, int y, int res = 1) {
    for (; y; y >>= 1, x = 1ll * x * x % mod) {
        if (y & 1) { res = 1ll * res * x % mod; }
    } return res;
}

const int N = 1e5 + 5;

int n, m, sx, sy, tx, ty, dx, dy, ans, f[N], fac[N], invf[N];

void initCombin(int n) {
    for (int i = fac[0] = 1; i <= n; i++) { fac[i] = 1ll * fac[i - 1] * i % mod; }
    invf[n] = power(fac[n], mod - 2);
    for (int i = n; i; i--) { invf[i - 1] = 1ll * invf[i] * i % mod; }
}

inline int binom(int n, int m) {
    if (n < m) { return 0; }
    return 1ll * fac[n] * invf[m] % mod * invf[n - m] % mod;
}

int main() {
    std::cin >> n >> m; initCombin(1e5);
    tx = n + m; ty = n - m;
    for (int i = 0; i <= n; i++) {
        sx = 0; sy = i + i;
        dx = tx - sx; dy = ty - sy;
        if (ty >= i) {
            f[i] = binom(n + m, n);
        } else {
            f[i] = binom(dx, (dx + dy) / 2);
        }
    }
    for (int i = 0; i <= n; i++) { ans = add(ans, 1ll * i * sub(f[i], f[i + 1]) % mod); }
    std::cout << ans << std::endl;
    return 0;
}