310519: CF1845E. Boxes and Balls
Description
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$.
InputThe 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$.
OutputPrint a single integer — the number of different arrangements of balls that can exist after exactly $k$ moves are performed, modulo $10^9+7$.
ExamplesInput4 1 1 0 1 0Output
3Input
4 2 1 0 1 0Output
2Input
10 6 1 0 0 1 0 0 0 1 1 1Output
69Note
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.
Input
题意翻译
给定一个长度为 $n$，由 $0,1$ 构成的数组 $a$。你可以对他进行以下操作： - 交换数列中一对相邻的 $0$ 和 $1$。 问在**恰好** $k$ 次操作后，可以产生多少种本质不同的数组。Output
E. 盒子和球
有 n 个盒子排成一行，从 1 到 n 编号。一些盒子里有一个球，其余为空。至少有一个盒子里有球，至少有一个盒子为空。
每次操作，你**必须**选择一个带球的盒子和一个相邻的空盒子，并将球从一个盒子移动到另一个盒子。对于所有 1 到 n-1 的 i，盒子 i 和 i+1 被认为是相邻的。盒子 1 和 n **不**相邻。
在恰好执行 k 次移动后，存在多少种不同的球排列？如果至少有一个盒子在一个排列中有球而在另一个中没有，则认为这两个排列是不同的。
由于答案可能相当大，请输出其除以 10^9+7 的余数。
输入输出数据格式：
输入：
- 第一行包含两个整数 n 和 k（2 ≤ n ≤ 1500; 1 ≤ k ≤ 1500）—— 盒子的数量和移动次数。
- 第二行包含 n 个整数 a_1, a_2, …, a_n（a_i ∈ {0, 1}）—— 0 表示空盒子，1 表示有球的盒子。至少有一个 0 和一个 1。
输出：
- 打印一个整数——在恰好执行 k 次移动后，可以存在的不同球排列的数量，模 10^9+7。
示例：
输入：
```
4 1
1 0 1 0
```
输出：
```
3
```
输入：
```
4 2
1 0 1 0
```
输出：
```
2
```
输入：
```
10 6
1 0 0 1 0 0 0 1 1 1
```
输出：
```
69
```题目大意： E. 盒子和球 有 n 个盒子排成一行，从 1 到 n 编号。一些盒子里有一个球，其余为空。至少有一个盒子里有球，至少有一个盒子为空。 每次操作，你**必须**选择一个带球的盒子和一个相邻的空盒子，并将球从一个盒子移动到另一个盒子。对于所有 1 到 n-1 的 i，盒子 i 和 i+1 被认为是相邻的。盒子 1 和 n **不**相邻。 在恰好执行 k 次移动后，存在多少种不同的球排列？如果至少有一个盒子在一个排列中有球而在另一个中没有，则认为这两个排列是不同的。 由于答案可能相当大，请输出其除以 10^9+7 的余数。 输入输出数据格式： 输入： - 第一行包含两个整数 n 和 k（2 ≤ n ≤ 1500; 1 ≤ k ≤ 1500）—— 盒子的数量和移动次数。 - 第二行包含 n 个整数 a_1, a_2, …, a_n（a_i ∈ {0, 1}）—— 0 表示空盒子，1 表示有球的盒子。至少有一个 0 和一个 1。 输出： - 打印一个整数——在恰好执行 k 次移动后，可以存在的不同球排列的数量，模 10^9+7。 示例： 输入： ``` 4 1 1 0 1 0 ``` 输出： ``` 3 ``` 输入： ``` 4 2 1 0 1 0 ``` 输出： ``` 2 ``` 输入： ``` 10 6 1 0 0 1 0 0 0 1 1 1 ``` 输出： ``` 69 ```