回分類題庫
z087: B.艾迪發禮物
關鍵字: NPSC2015國中決賽

測資點 : 10 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 9 Times / 9 Users | Submit : 11 Times / 9 Users | Accepted rate : 100%
題目加入時間 : 2019-11-18 17:06

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:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 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)

  Solve it!   Status Forum