h924. 揩淯愛牌組
標籤 : DP 數學
通過比率 : 3人/4人 ( 75% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-06-19 19:03

內容

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

給你一個長度為 $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
1
範例輸入 #2
5 3
1 2 3 4 5
範例輸出 #2
10
範例輸入 #3
4 3
1 2 3 3
範例輸出 #3
2
範例輸入 #4
4 3
3 3 3 3
範例輸出 #4
0
範例輸入 #5
20 5
10 20 16 8 8 5 4 14 3 19 5 15 9 19 3 13 12 15 17 3
範例輸出 #5
10344
測資資訊:
記憶體限制: 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 數學
出處:
第六屆簡單的小競賽 [管理者: becaido (Caido) ]

本題狀況 本題討論 排行

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