Codeforces Round 581 (Div. 2)
E
Natasha, Sasha and the Prefix Sums
Codeforces
2300
原题
← D2→
翻译中…

Natasha's favourite numbers are $n$ and $1$, and Sasha's favourite numbers are $m$ and $-1$. One day Natasha and Sasha met and wrote down every possible array of length $n+m$ such that some $n$ of its elements are equal to $1$ and another $m$ elements are equal to $-1$. For each such array they counted its maximal prefix sum, probably an empty one which is equal to $0$ (in another words, if every nonempty prefix sum is less to zero, then it is considered equal to zero). Formally, denote as $f(a)$ the maximal prefix sum of an array $a_{1, \ldots ,l}$ of length $l \geq 0$. Then:

翻译中…

$$f(a) = \max (0, \smash{\displaystyle\max_{1 \leq i \leq l}} \sum_{j=1}^{i} a_j )$$

翻译中…

Now they want to count the sum of maximal prefix sums for each such an array and they are asking you to help. As this sum can be very large, output it modulo $998\: 244\: 853$.

翻译中…

Input

翻译中…

The only line contains two integers $n$ and $m$ ($0 \le n,m \le 2\,000$).

翻译中…

Output

翻译中…

Output the answer to the problem modulo $998\: 244\: 853$.

翻译中…

Note

翻译中…

In the first example the only possible array is [-1,-1], its maximal prefix sum is equal to $0$.

翻译中…

In the second example the only possible array is [1,1], its maximal prefix sum is equal to $2$.

翻译中…

There are $6$ possible arrays in the third example:

翻译中…

[1,1,-1,-1], f([1,1,-1,-1]) = 2

翻译中…

[1,-1,1,-1], f([1,-1,1,-1]) = 1

翻译中…

[1,-1,-1,1], f([1,-1,-1,1]) = 1

翻译中…

[-1,1,1,-1], f([-1,1,1,-1]) = 1

翻译中…

[-1,1,-1,1], f([-1,1,-1,1]) = 0

翻译中…

[-1,-1,1,1], f([-1,-1,1,1]) = 0

翻译中…

So the answer for the third example is $2+1+1+1+0+0 = 5$.

翻译中…

样例

Input #1
0 2
Output #1
0
InputCopy OutputCopy
Input #2
2 0
Output #2
2
InputCopy OutputCopy
Input #3
2 2
Output #3
5
InputCopy OutputCopy
Input #4
2000 2000
Output #4
674532367
InputCopy OutputCopy
题目信息
题号
1204E
时间限制
2 s
内存限制
256 MB
标签
组合数学
动态规划
数学
数论

题面与样例版权归 Codeforces 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。