TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

100.0% (16/16)

Submission's AC Ratio

47.7% (52/109)

Description

  假設我們有 n 顆看起來一樣的球要進行分群,那麼球上是否有編號將會影響到分群的結果。舉例來說,假設我們有 3 顆沒有編號的球,那麼分群的方法共有三種,分別是:(1)每顆球獨自一群;(2)其中一群有兩顆球,另一群則是一顆球;(3)三顆球都在同一群。如果這 3 顆球分別編號為 1、2、3,並且以{}表示分在同一群,那麼分群的方法將會有以下五種:(1) {1}, {2}, {3};(2) {1}, {2, 3};(3) {2}, {1, 3};(4) {3}, {1, 2};(5) {1, 2, 3}。請注意:{1}, {2, 3}、{1}, {3,2}、{2, 3}, {1}、{3, 2}, {1}這四種表示法都視為是同一種分群,因為這四種其實都代表著 1 號球自己一群,2, 3 號球在另一群。
  有的時候我們會想要在分群的時候加上一些條件限制:例如已經知道部分的分群狀況了,想要知道還有幾種分群的方法滿足這樣的分群狀況。如果是沒有編號的球,我們已知的訊息可能是:其中的 k 群,它們的球數分別是$a_1, a_2, \cdots, a_k$。如果是有編號的球,我們已知的訊息可能是:其中的 k 顆球$b_1,b_2, \cdots, b_k$,任兩顆球都分屬於不同的群。
給定 n 顆看起來一樣的球、它們是否有編號、以及上述條件。請你寫一個程式來判斷分群的方法到底有幾種。

Input Format

輸入的第一行有一個大寫字母 U 或 N,表示球有沒有編號(U:沒有、N:有);接著會有非負整數 n, k,表示總球數以及條件中的 k 值。第二行有 k 個數字,對應題目敘述的條件內容。

子任務(測資) 額外限制 分數
1 (0~4) 球沒有編號,$1\leq n\leq 20, k\leq 1$ 18
2 (5~9) 球有編號,$1\leq n\leq 15, k\leq 1$ 20
3 (0~14) $1\leq n\leq 100, k\leq 1$ 21
4 (0~25) $1\leq n\leq 5000, k\leq n$ 41

Output Format

對於每一筆測試資料,請輸出分群的方法種數除以 $10^ 9 + 7$ 的餘數。

Sample Input

#Sample Input 1
U 3 1
2
#Sample Input 2
U 10 2
2 3
#Sample Input 3
N 3 0

#Sample Input 4
N 10 4
1 2 3 4

Sample Output

#Sample Output 1
1
#Sample Output 2
7
#Sample Output 3
5
#Sample Output 4
29371

Hints

Problem Source

題目取自2017 TOI選訓第二次模擬考pC

Subtasks

No. Testdata Range Score
1 0~4 18
2 5~9 20
3 0~14 21
4 0~25 41

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 900 262144 262144 1 3 4
1 900 262144 262144 1 3 4
2 900 262144 262144 1 3 4
3 900 262144 262144 1 3 4
4 900 262144 262144 1 3 4
5 900 262144 262144 2 3 4
6 900 262144 262144 2 3 4
7 900 262144 262144 2 3 4
8 900 262144 262144 2 3 4
9 900 262144 262144 2 3 4
10 900 262144 262144 3 4
11 900 262144 262144 3 4
12 900 262144 262144 3 4
13 900 262144 262144 3 4
14 900 262144 262144 3 4
15 900 262144 262144 4
16 900 262144 262144 4
17 900 262144 262144 4
18 900 262144 262144 4
19 900 262144 262144 4
20 900 262144 262144 4
21 900 262144 262144 4
22 900 262144 262144 4
23 900 262144 262144 4
24 900 262144 262144 4
25 900 262144 262144 4