CF1204E = 998244853.
Natasha, Sasha and the Prefix Sums
NaCly_Fish 最喜欢的数字是 \(n\) 和 \(1\)；\(\mathsf E \color{red} \mathsf{ntropyIncreaser}\) 最喜欢 \(m\) 和 \(-1\)。
有一天，她们在一起写出了一个长度为 \(n+m\)，有 \(n\) 个 \(1\) 和 \(m\) 个 \(-1\) 的序列 \(a\)，定义其最大前缀和为：
\[\large \max\{ 0,\max\limits_{1\le i\le n+m}\sum\limits_{j=1}^ia_j \} \]换句话说，就是对于 \(a\) 的前缀和的所有项和 \(0\) 取 \(\max\) 的值。
NaCly_Fish 想知道，对于全部可能的序列，它们的 最大前缀和 之和是多少。
为了防止答案过大，要对 \({998244\textcolor{red}853}\) (是个质数) 取模。\(\mathsf E \color{red} \mathsf{ntropyIncreaser}\) 只用 1s 就想到了做法，但是 NaCly_Fish 还不会，你能帮帮她吗？
转化成统计有多少个数列的最大前缀和为 \(k\)。
再枚举最大前缀和出现的第一个位置的前一个位置。设它为 \(i\)。
然后问题拆成两半。第一半是从 \(0\) 自增 \(a\) 次，自减 \(b\) 次增长到 \(k - 1\)，并且始终不超过 \(k - 1\) 的方案数。
然后自增一次。然后就是从 \(k\) 自增 \(n - a - 1\) 次，自减 \(m - b\) 次，始终不超过 \(k\) 的方案数。
\(a + b = i, a - b = k - 1\)。
扔到坐标图上。
把自加体现成向右，自减体现成向上。走到 \((a,b)\)，不能穿过直线 \(y = x - k + 1\)。
把自加体现成向左，自减体现成向下，从 \((a, b)\) 走到 \((0, 0)\)，不能穿过直线 \(y = x - k + 1\)。
所有坐标减去 \((a, b)\)。从 \((0, 0)\) 走到 \((-a, -b)\)，不能穿过直线 \(y = x\)。
向左向下走太抽象，把整张图以 \(y = -x\) 为轴对称一下。
把自加体现成向上，自减体现成向右，从 \((0, 0)\) 走到 \((b, a)\)，不能经过直线 \(y = x\)。
啊好看多了。这样的方案数是：
\[\binom {b + a}{b} - \binom{b + a}{b - 1} \]另一边也差不多。自减 \(m - b\) 次，自增 \(n - a - 1\) 次。令 \(x = m - b\)，\(y = n - a - 1\)。
\(x \ge y\)，一定。
\[\binom {x + y}{y} - \binom{x + y}{y - 1} \]是不是做完了。
#include<iostream>
#include<fstream>
#include<algorithm>
#define int long long
using namespace std;
namespace azus{
int n, m;
const int P = 998244853;
int jc[2000005], inv[2000005];
int Ksm(int u, int v){
int ret = 1;
while(v){
if(v & 1) ret = 1ll * ret * u % P;
u = 1ll * u * u % P, v >>= 1;
}
return ret;
}
int binom(int u, int v){
return (jc[u] * inv[v] % P) * inv[u - v] % P;
}
int Cat(int u, int v){
if(v == 0) return 1;
return (P + binom(u + v, v) - binom(u + v, v - 1)) % P;
}
int prework(){
jc[0] = inv[0] = 1;
for(int i = 1; i <= 2000000; i ++)
jc[i] = jc[i - 1] * i % P;
inv[2000000] = Ksm(jc[2000000], P - 2);
for(int i = 1999999; i >= 1; i --)
inv[i] = inv[i + 1] * (i + 1) % P;
return 0;
}
int ans = 0;
int main(){
prework();
cin >> n >> m;
for(int k = max(1ll, n - m); k <= n; k ++){
for(int i = 0; i < n + m; i ++){
int a, b;
if((i + k - 1) & 1) continue;
a = (i + k - 1) / 2, b = (i - (k - 1)) / 2;
// cout << "[" << a << " ," << b << "] ";
// if(i == 3 && k == 1)
// cout << "(" << a << "," << b << ") ";
if(a < 0 || b < 0) continue;
int c1 = Cat(a, b);
int x, y;
x = m - b, y = n - a - 1;
if(x < 0 || y < 0) continue;
int c2 = Cat(x, y);
ans += (c1 * c2 % P) * k % P;
ans %= P;
// cout << i << " ";
}
// cout << "\n";
// cout << k << " " << ans << "\n";
}
cout << ans;
return 0;
}
}
signed main(){
// ios::sync_with_stdio(0);
// cin.tie(0), cout.tie(0);
int T = 1;
while(T --) azus::main();
return 0;
}