#P13037. [GCJ 2021 #2] Hidden Pancakes

    ID: 12838 Type: RemoteJudge 30000~40000ms 1024MiB Tried: 0 Accepted: 0 Difficulty: 5 Uploaded By: Tags>动态规划 DP2021组合数学Google Code Jam

[GCJ 2021 #2] Hidden Pancakes

题目描述

We are cooking N\mathbf{N} pancakes in total. We cook one pancake with a 1 centimeter (cm) radius, one with a 2 cm2 \mathrm{~cm} radius, one with a 3 cm3 \mathrm{~cm} radius, ..., and one with an Ncm\mathbf{N} \mathrm{cm} 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 3 cm3 \mathrm{~cm}, and it is visible. Then, we cook the pancake with radius 1 cm1 \mathrm{~cm}, lay it on top of the first one and both are visible. Third, we cook the pancake with radius 2 cm2 \mathrm{~cm}, 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 4 cm4 \mathrm{~cm} 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 Vi\mathbf{V}_{\mathbf{i}} be the number of visible pancakes when the stack contains exactly ii pancakes. In the example above, $\mathbf{V}_{1}=1, \mathbf{V}_{2}=2, \mathbf{V}_{3}=2$, and V4=1\mathbf{V}_{4}=1.

Given the list $\mathbf{V}_{1}, \mathbf{V}_{2}, \ldots, \mathbf{V}_{\mathbf{N}}$, how many of the N!\mathbf{N} ! 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 109+7(1000000007)10^{9}+7(1000000007).

输入格式

The first line of the input gives the number of test cases, T\mathbf{T}. T\mathbf{T} test cases follow, each described with two lines. The first line of a test case contains a single integer N\mathbf{N}, the number of pancakes we cook. The second line of a test case contains N\mathbf{N} integers $\mathbf{V}_{1}, \mathbf{V}_{2}, \ldots, \mathbf{V}_{\mathbf{N}}$, representing the number of visible pancakes after we cook 1,2,,N1,2, \ldots, \mathbf{N} pancakes, respectively.

输出格式

For each test case, output one line containing Case #x: y, where xx is the test case number (starting from 1) and yy is the number of cooking orders of N\mathbf{N} pancakes that yield the given numbers of visible pancakes after each step, modulo the prime 109+7(1000000007)10^{9}+7(1000000007).

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 3,1,2,43,1,2,4 is the only one that yields the given Vis\mathbf{V}_{\mathbf{i}} \mathrm{s}.

In Sample Case #2, both the order 1,3,21,3,2 and the order 2,3,12,3,1 yield the intended Vis\mathbf{V}_{\mathbf{i}} \mathrm{s}. 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 316234143225316234143225 cooking orders that yield the given Vis\mathbf{V}_{\mathbf{i}} \mathrm{s}. Modulo 109+710^{9}+7, this value is 234141013234141013.

Limits

  • 1T1001 \leq \mathbf{T} \leq 100.
  • 1Vii1 \leq \mathbf{V}_{\mathbf{i}} \leq i, for all ii.

Test Set 1 (Visible Verdict)

  • Time limit: 30 seconds.
  • 2N132 \leq \mathbf{N} \leq 13.

Test Set 2 (Hidden Verdict)

  • Time limit: 40 seconds.
  • 2N1052 \leq \mathbf{N} \leq 10^{5}.