Content:
简体中文
補教界名師艾迪來到了哈味國中教書。 最近期中考才剛考完,為了獎勵同學的⾟勞,艾迪特地為他班上的N 位同學準備了N 份禮 物,打算每個⼈各送⼀份。 艾迪本來打算要隨機發給每個同學⼀份禮物,但是他準備的每個禮物都不⼀樣,價值也有⾼ 低之分,他擔⼼如果成績好的同學看到其他同學拿到⽐⾃⼰好的禮物,就會感到內⼼不平衡。 因此,為了不要打擊某些同學的玻璃⼼,艾迪特地將班上的同學依照這次期中考的成績從第 ⼀名排到第N 名(每個⼈名次都不同)。然後⼜為每⼀個禮物評估了⼀個價值指數Ti,表⽰排名 要在第Ti名以前才能獲得這個禮物。艾迪認為只要每個⼈的名次都符合他們拿到的禮物的價值指 數,就不會有同學感到不滿了。但艾迪發現多了這些規則後他就不能隨便發禮物了,所以他想請 你幫他算出在滿⾜這些條件下,有幾種不同的分配禮物⽅式能讓⼤家都滿意。 舉例來說,班上有N = 3位同學,⽽艾迪為三份禮物評估出的價值指數Ti分別是2, 3, 3,那 艾迪有以下的幾種分配⽅式:{1,2,3}、{1,3,2}、{2,1,3}、{2,3,1},其中的{a,b,c}代表第⼀份 禮物發給第a名的同學,第⼆份禮物發給第b名的同學,第三份禮物發給第c名的同學。因此總 共有4種讓⼤家都滿意的⽅式。
Input:
測試資料的第⼀⾏包含⼀個正整數N,代表艾迪班上有N個同學。 第⼆⾏有N個正整數,分別代表艾迪所準備的N個禮物的價值指數Ti。
• 1 ≤ N ≤ 20
• 1 ≤ Ti ≤ N
• T1 ≤ T2 ≤···≤ TN−1 ≤ TN
Output:
請輸出⼀⾏包含⼀個整數,表⽰艾迪有幾種分配禮物的⽅式能讓所有⼈都滿意。 順道⼀提,你可以發現,有N 位同學的話,不考慮規則的話,最多只會有N! = 1×2×3× ···×N 種分配禮物的⽅式。也就是說,當N = 20時,答案不會超過2432902008176640000,可以發現這個值⽐long long int的最⼤值263 −1 = 9223372036854775807⼩,所以可以⽤long long int儲存。
Sample Input:
若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
3
2 3 3
3
2 2 2
20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
20
20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
Sample Output
:
4
0
1
2432902008176640000
Hint
:
Author
:
NPSC2015國中決賽
(管理員:Chang)