h924. 揩淯愛牌組 - 高中生程式解題系統

內容

揩淯是個熱愛牌組的小孩，有一天揩淯出給與紅一個牌組問題，但是與紅解不出來，想請你幫忙！！

給你一個長度為 $N$ 的牌組序列 $A_{1} \sim A_{N}$ ，每張牌的花色為 $A_{i}$ ，揩淯想從這些牌裡選出 $k$ 張花色相異牌 (一組牌最多 $54$ 張)，組成一副牌組，於是他想問你，有多少組 $(p_{1}, p_{2}, \dots, p_{k})$ ， $(1 \leq p_{1} < p_{2} < \dots < p_{k} \leq N)$ 使得 $A_{p_{1}}, A_{p_{2}}, \dots, A_{p_{k}}$ 相異？

如果你幫助揩淯，揩淯會教你啃啃啃雞腿的方法，你就能成為啃啃啃雞腿大師！

輸入說明

第一行有兩個整數 $N, k$ ，第二行有 $N$ 個整數 $A_{1} \sim A_{N}$ 。

$3 \leq N \leq 10^{5}$
$1 \leq k \leq 54$
$1 \leq A_{i} \leq 10^{9}$

輸出說明

輸出有幾組 $(p_{1}, p_{2}, \dots, p_{k})$ ， $(1 \leq p_{1} < p_{2} < \dots < p_{k} \leq N)$ 使得 $A_{p_{1}}, A_{p_{2}}, \dots, A_{p_{k}}$ 相異，答案請對 $998244853$ 取餘數。

範例輸入 #1

3 3
1 2 3

範例輸出 #1

範例輸入 #2

5 3
1 2 3 4 5

範例輸出 #2

範例輸入 #3

4 3
1 2 3 3

範例輸出 #3

範例輸入 #4

4 3
3 3 3 3

範例輸出 #4

範例輸入 #5

20 5
10 20 16 8 8 5 4 14 3 19 5 15 9 19 3 13 12 15 17 3

範例輸出 #5

測資資訊：

記憶體限制： 50 MB
不公開測資點#0 (13%): 1.0s , <1M
不公開測資點#1 (9%): 1.0s , <1M
不公開測資點#2 (9%): 1.0s , <1M
不公開測資點#3 (9%): 1.0s , <1M
不公開測資點#4 (10%): 1.0s , <1M
不公開測資點#5 (10%): 1.0s , <1M
不公開測資點#6 (10%): 1.0s , <1M
不公開測資點#7 (10%): 1.0s , <1M
不公開測資點#8 (10%): 1.0s , <1K
不公開測資點#9 (10%): 1.0s , <1K

提示：

$13 % ： k = 3$ ，就跟這題一樣

$87 % ：無特別限制$

標籤:

DP 數學

出處:

第六屆簡單的小競賽 [管理者： beckzerojudge@gmail.com

becaido (Caido) ]

編號	身分	題目	主題	人氣	發表日期
30888	becaido (Caido)	h924		436	2022-06-19 19:25