Accepted rate : 4人/18人 ( 22% ) [非即時]
評分方式：
最近更新 : 2022-10-22 16:14
某個廚師十分喜歡炮製pancake。每個pancake都是圓的，所以我們總可以用直徑來表示其大小。這一次，廚師依次製作了 n 個不同大小的pancake，並把它們一字排開在枱上。
廚師先拿出一個空碟子，再由左到右考慮這 n 個pancake：對每一個pancake他可以選擇把它疊到碟子上，也可以選擇暫時放棄這個pancake；如此考慮完 n 次後，碟子上便會有若干個pancake。如果這 n 個pancake是由下至上越來越小的話，廚師就會說疊起來的那堆pancake是「好看」的，因為由上至下看時我們剛好能清晰看見每一件pancake (沒有pancake被上面的遮蓋)。換句話說，廚師希望選出來的每個pancake都比上一個選出的小。例如當pancake直徑依次為 (6, 5, 2, 3) 時，(3), (2), (5), (6), (6, 3), (6, 2), (6, 5), (5, 2), (5, 3), (6, 5, 2), (6, 5, 3) 是所有合法的堆疊方法。注意每種方法都至少要疊上一個pancake。
此時廚師突發奇想，到底共有多少種方法可以疊出好看的pancake呢？無奈他覺得這個問題極難，所以選擇把重任交給你。由於總方法數可能很大，請輸出答案除以 109+7 (一個質數) 的餘數。
(或者，一個較無趣的題目表達是: 給定一有 n 個互異正整數的序列，求其單調下降子序列的數目。)
第一行有一正整數 T (1 <= T <= 5)，表示接下來有 T 組獨立的測資。（需要應答 T 次）
每個測資共有兩行。第一行給定一個正整數 n ，表示pancake數目；第二行則給 n 個正整數 (以空格隔開)，其中第 i 個數為第 i 個做出的pancake的直徑 di。保證 di 兩兩不同。
1 <= n <= 105, 1 <= di <= 109。
共輸出 T 行，分別為 T 個測資的答案。對第 i 個測資輸出有多少種方法 (mod 109+7) 可以使抽出來的pancake是好看的。
4 3 3 2 1 4 1 2 4 3 4 2 3 1 4 3 2 1 3
7 5 6 4
5 4 6 5 2 3 5 9 7 5 4 2 6 1 2 3 4 7 9 1 9 5 4 3 1 2 5
11 31 6 1 12
不公開 測資點#0 (5%): 0.5s , <1K
不公開 測資點#1 (15%): 0.5s , <1K
不公開 測資點#2 (25%): 0.5s , <1K
不公開 測資點#3 (35%): 1.0s , <1M
不公開 測資點#4 (20%): 1.0s , <10M
温馨提示：系統能根據完成程度給予部分分數，但若要完全解決這題需要能處理 n, di 較大的情況。
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||