Boxes and Balls
Contest: Educational Codeforces Round 151 (Rated for Div. 2)
Difficulty rating: 2500
Tags: dp, implementation, math

There are $$$n$$$ boxes placed in a line. The boxes are numbered from $$$1$$$ to $$$n$$$. Some boxes contain one ball inside of them, the rest are empty. At least one box contains a ball and at least one box is empty.

In one move, you have to choose a box with a ball inside and an adjacent empty box and move the ball from one box into another. Boxes $$$i$$$ and $$$i+1$$$ for all $$$i$$$ from $$$1$$$ to $$$n-1$$$ are considered adjacent to each other. Boxes $$$1$$$ and $$$n$$$ are not adjacent.

How many different arrangements of balls exist after exactly $$$k$$$ moves are performed? Two arrangements are considered different if there is at least one such box that it contains a ball in one of them and doesn't contain a ball in the other one.

Since the answer might be pretty large, print its remainder modulo $$$10^9+7$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 1500$$$; $$$1 \le k \le 1500$$$) — the number of boxes and the number of moves.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$a_i \in \{0, 1\}$$$) — $$$0$$$ denotes an empty box and $$$1$$$ denotes a box with a ball inside. There is at least one $$$0$$$ and at least one $$$1$$$.

Output format:
Print a single integer — the number of different arrangements of balls that can exist after exactly $$$k$$$ moves are performed, modulo $$$10^9+7$$$.

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

Note:
In the first example, there are the following possible arrangements:

- 0 1 1 0 — obtained after moving the ball from box $$$1$$$ to box $$$2$$$;
- 1 0 0 1 — obtained after moving the ball from box $$$3$$$ to box $$$4$$$;
- 1 1 0 0 — obtained after moving the ball from box $$$3$$$ to box $$$2$$$.

In the second example, there are the following possible arrangements:

- 1 0 1 0 — three ways to obtain that: just reverse the operation performed during the first move;
- 0 1 0 1 — obtained from either of the first two arrangements after the first move.

Example input:
4 1
1 0 1 0

Example output:
3

Example input:
4 2
1 0 1 0

Example output:
2

Editorial:
Consider a harder problem. For each $$$k'$$$ from $$$0$$$ to $$$k$$$, what's the number of arrangements that have $$$k'$$$ as the smallest number of operations needed that obtain them?
That would help us solve the full problem. You just have to sum up the answer for $$$k'$$$ such that they have the same parity as $$$k$$$ (since, once the arrangement is obtained, you can perform two moves on it and change nothing).
Turns out, calculating the smallest number of operations for a fixed arrangement is not that hard. Let the initial arrangement have balls in boxes $$$c_1, c_2, \dots, c_t$$$ for some $$$t$$$; the fixed arrangement have balls in boxes $$$d_1, d_2, \dots, d_t$$$. Then the first ball in the fixed arrangement has to come from the box of the first ball in the initial one. And so on. So the answer is at least $$$\sum\limits_{i=1}^t |c_t - d_t|$$$. That estimate can be achieved. Just move the balls one by one from left to right. So that amount is actually the smallest possible.
That can lead to a dynamic programming solution. Following this construction, let $$$\mathit{dp}[i][j][k]$$$ be the number of ways to fill the first $$$i$$$ boxes with $$$j$$$ balls such that the smallest number of operations to move the first $$$j$$$ balls of the initial arrangement into their new boxes is $$$k$$$. The transitions are trivial. Either leave the $$$i$$$-th (all $$$0$$$-indexed) box empty and go to $$$\mathit{dp}[i+1][j][k]$$$ or put a ball into it and go to $$$\mathit{dp}[i+1][j+1][k + |i - c_j|]$$$. The answer will be in $$$\mathit{dp}[n][t][k']$$$ for all $$$k'$$$ of the same parity as $$$k$$$. That solution is $$$O(n^2k)$$$ that is supposedly too much (although unfortunately can be squeezed if you try hard enough).
That solution has surprisingly little to do with the full one but gives us some insight into the problem.
For a faster solution, let's change the way we calculate the smallest number of operations. What is exactly $$$|c_t - d_t|$$$? Let $$$c_t > d_t$$$. Then on its path the ball crosses the spaces between boxes $$$c_t$$$ and $$$c_t-1$$$, $$$c_t-1$$$ and $$$c_t-2$$$, so on until $$$d_t+1$$$ and $$$d_t$$$. The amount is exactly $$$(c_t - d_t)$$$.
Thus, we could instead calculate the number of balls that move across each space between the boxes along their paths and add up the values. Now it's some sort of balance. We could also denote balls going to the right as positive values and going to the left as negative values. Notice how if some ball moves from a box $$$i$$$ to a box $$$i-1$$$ in the optimal construction, then there is no ball that moves from $$$i-1$$$ to $$$i$$$. Just because the balls never cross each other paths. So the absolute value of the balance is still what we have to add up.
Intuitively, the value for space between boxes $$$i$$$ and $$$i+1$$$ is equal to the signed difference between the initial number of balls to the left of it and the one in the current arrangement. If the numbers are different, then we move exactly this amount of ball from one side to another.
Now we can pack it into another dynamic programming. Let $$$\mathit{dp}[i][j][k]$$$ be the number of ways to fill the first $$$i$$$ boxes, such that the current balance is $$$j$$$ and the smallest number of operations to achieve that is $$$k$$$.
The transitions are the following. If we place a ball into box $$$i$$$, the balance changes to $$$j + 1 - a_i$$$ ($$$a_i$$$ is whether there was a ball in box $$$i$$$ initially) and $$$|j + 1 - a_i|$$$ gets added to $$$k$$$. If we don't place a ball, the balance changes to $$$j - a_i$$$ and $$$|j - a_i|$$$ gets added to $$$k$$$.
Notice that at the end the balance will be $$$0$$$ if and only if we placed as many boxes as there were initially. So, the answer will be in $$$\mathit{dp}[n][0][k']$$$ for all $$$k'$$$ of the same parity as $$$k$$$.
That solution is still $$$O(n^2k)$$$ and even worse in the way that $$$j$$$ can range from $$$-n$$$ to $$$n$$$, doubling the runtime.
However, notice how $$$j$$$ can't change by more than $$$1$$$ on each step. At the same time, $$$|j|$$$ always gets added to $$$k$$$. Thus, to make $$$j$$$ equal to $$$0$$$ at the end, we would have to add $$$|j| + (|j| - 1) + (|j| - 2) + \dots + 1$$$ to $$$k$$$. And since $$$k$$$ can't exceed $$$1500$$$, $$$|j|$$$ actually can't exceed $$$55$$$ (more or less $$$O(\sqrt{k})$$$).
So, that solution can be optimized to $$$O(nk^{1.5})$$$ by reducing the second dimension of the dynamic programming.
In order to store values from $$$-x$$$ to $$$x$$$ in an array, shift them up by $$$x$$$. So the values become from $$$0$$$ to $$$2x$$$.
In order to avoid $$$O(nk^{1.5})$$$ memory, instead of storing all $$$n$$$ layers of the dp, only store the current and the next one. That will make it $$$O(k^{1.5})$$$ memory.
Overall complexity: $$$O(nk^{1.5})$$$.