CF1204E 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 还不会,你能帮帮她吗?

输入格式

输出格式

说明/提示

【样例 $3$ 解释】 可能的序列有 $6$ 种: $1,1,-1,-1$ $1,-1,1,-1$ $1,-1,-1,1$ $-1,1,1,-1$ $-1,1,-1,1$ $-1,-1,1,1$ 它们的最大前缀和分别为 $2,1,1,1,0,0$,加起来答案为 $5$。 $0\le n,m \le 2000$