Kocke
레이팅 미적용의견: 0
For his thirteenth birthday, Donald’s parents bought him a bra\(nd-ne\)w set of Lego
cubes. In the set, there are \(n\) cubes of equal size, where the \(i-th\) cube came in
color \(i\). Using these cubes he decided to build a wall.
Donald will build his wall on a r\(ow-li\)ke Lego base that has \(k\) places where cubes
can be put in. He puts the cubes in the following way:
• First, he puts the cube with color 1 on an arbitrary spot on the base.
• For each cube from 2 to \(n\), he places it in a spot neighboring the previously
placed cube. If that spot isn’t empty, he puts the new cube on top of all the others.
After he built the wall, Donald wrote on a piece of paper a sequence of length \(k\): on the \(i-th\) position in
the sequence he wrote the color of the top cube in the \(i-th\) place, or 0 if there isn’t a cube in that place.
He immediately asked himself how many different sequences could he have written on the piece of paper.
Two sequences are considered different if there exists a position in which they differ. After some time, he
has managed to calculate the solution, but he is not sure whether it is correct, so he asks for your help.
Subtask 1 (20 points): n, \(k \le 18\)
Subtask 2 (30 points): n, \(k \le 50\)
Subtask 3 (30 points): n, \(k \le 500\)
Subtask 4 (30 points): No additional constraints.
The only line has integers \(n\) and \(k\) (\(2 \le n\), \(k \le 5\,000\)), the number of cubes, and the length of the base.
In the only line, print the answer to Donald’s question, modulo \(10^{9} + 7\).
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 20점 | n, \(k \le 18\) |
2 | 30점 | n, \(k \le 50\) |
3 | 30점 | n, \(k \le 500\) |
4 | 30점 | No additional constraints. |
4 383 514100 200410783331Clarification of the first example:
All possible sequences are: (0, 3, 4), (2, 3, 4), (0, 4, 3), (1, 4, 3), (4, 3, 0), (4, 3, 2), (3, 4, 0), (3, 4, 1).
Clarification of the second example:
One of the possible sequences is (0, 3, 2, 0, 0). Donald can achieve that by putting the first cube on the
second place, second cube on the third place, and third cube on the second place (on top of the first cube).
평가 및 의견
Kocke
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Kocke