Natasha, Sasha and the Prefix Sums
Contest: Codeforces Round 581 (Div. 2)
Difficulty rating: 2300
Tags: combinatorics, dp, math, number theory

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 format:
The only line contains two integers $$$n$$$ and $$$m$$$ ($$$0 \le n,m \le 2\,000$$$).

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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$$$.

Example input:
0 2

Example output:
0

Example input:
2 0

Example output:
2

Editorial:
Let's count a dp $$$k[x][y]$$$ — the number of arrays consisting of $$$x$$$ ones and $$$y$$$ minus ones such that their maximal prefix sum is equal to $$$0$$$: if $$$x=0$$$ then $$$k[x][y] = 1$$$, else if $$$x>y$$$ then $$$k[x][y] = 0$$$, else $$$k[x][y] = k[x-1][y] + k[x][y-1]$$$, because if we consider any array consisting of $$$x$$$ ones and $$$y-1$$$ minus ones which maximal prefix sum is $$$0$$$ then adding a minus one to the end leaves it equal to $$$0$$$; also if we consider any array consisting of $$$x-1$$$ ones and $$$y$$$ minus ones which maximal prefix sum is $$$0$$$ then adding a one to the end leaves it equal to $$$0$$$, because $$$x \leq y$$$.
Now let's count a dp $$$d[x][y]$$$ — the answer to the problem for $$$n=x$$$ and $$$m=y$$$: if $$$x=0$$$ then $$$d[x][y]=0$$$, else if $$$y=0$$$ then $$$d[x][y]=x$$$, else $$$d[x][y] = (\binom{x+y-1}{y}+d[x-1][y]) + (d[x][y-1] - (\binom{x+y-1}{x}-k[x][y-1]))$$$. That is because if we consider any array of $$$x-1$$$ ones and $$$y$$$ minus ones (there are $$$\binom{x+y-1}{y}$$$ such arrays) then adding a one in its beginning increases its maximal prefix sum by $$$1$$$; also if we consider any array of $$$x$$$ ones and $$$y-1$$$ minus ones then adding a minus one in its beginning either decreases its maximal prefix sum by $$$1$$$ if it was greater than $$$0$$$ (there are $$$\binom{x+y-1}{x}-k[x][y-1]$$$ such arrays) or leaves it equal to $$$0$$$. So the answer to the problem is $$$d[n][m]$$$.