#P13037. [GCJ 2021 #2] Hidden Pancakes
[GCJ 2021 #2] Hidden Pancakes
题目描述
We are cooking pancakes in total. We cook one pancake with a 1 centimeter (cm) radius, one with a radius, one with a radius, ..., and one with an radius, not necessarily in that order. After we cook the first pancake, we just lay it on a plate. After we cook each subsequent pancake, we lay it on top of the previously made pancake, with their centers coinciding. In this way, a pancake is visible from the top of the stack when we first add it. A pancake only becomes hidden if we later cook another pancake with a larger radius.
For example, say we cook 4 pancakes. We first cook the pancake with radius , and it is visible. Then, we cook the pancake with radius , lay it on top of the first one and both are visible. Third, we cook the pancake with radius , and now that covers the previous pancake, but not the first one, so 2 pancakes remain visible in total. Finally, we cook the pancake with radius which covers the other pancakes leaving only 1 visible pancake. The picture below illustrates the state of the stack after each pancake is cooked. Within each stack, the fully colored pancakes are visible and the semi-transparent pancakes are not visible.
Let be the number of visible pancakes when the stack contains exactly pancakes. In the example above, $\mathbf{V}_{1}=1, \mathbf{V}_{2}=2, \mathbf{V}_{3}=2$, and .
Given the list $\mathbf{V}_{1}, \mathbf{V}_{2}, \ldots, \mathbf{V}_{\mathbf{N}}$, how many of the possible cooking orders yield those values? Since the output can be a really big number, we only ask you to output the remainder of dividing the result by the prime .
输入格式
The first line of the input gives the number of test cases, . test cases follow, each described with two lines. The first line of a test case contains a single integer , the number of pancakes we cook. The second line of a test case contains integers $\mathbf{V}_{1}, \mathbf{V}_{2}, \ldots, \mathbf{V}_{\mathbf{N}}$, representing the number of visible pancakes after we cook pancakes, respectively.
输出格式
For each test case, output one line containing Case #x: y
, where is the test case number (starting from 1) and is the number of cooking orders of pancakes that yield the given numbers of visible pancakes after each step, modulo the prime .
3
4
1 2 2 1
3
1 1 2
3
1 1 3
Case #1: 1
Case #2: 2
Case #3: 0
1
24
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
Case #1: 234141013
提示
Sample Case #1 is explained in the problem statement. The order is the only one that yields the given .
In Sample Case #2, both the order and the order yield the intended . The pictures below illustrate both options.
In Sample Case #3, only 1 pancake is visible after the second is made, so there is no way to have more than 2 visible pancakes by only adding a third.
Sample Test Set 2 fits the limits of Test Set 2. It will not be run against your submitted solutions.
In the Sample Case for Test Set 2, there are cooking orders that yield the given . Modulo , this value is .
Limits
- .
- , for all .
Test Set 1 (Visible Verdict)
- Time limit: 30 seconds.
- .
Test Set 2 (Hidden Verdict)
- Time limit: 40 seconds.
- .