h924: 揩淯愛牌組
Tags : DP 數學
Accepted rate : 2人/2人 ( 100% ) [非即時]
評分方式:
Tolerant

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

Content

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

給你一個長度為 $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}$ 相異?

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

Input

第一行有兩個整數 $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$
Output

輸出有幾組 $(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$ 取餘數。

Sample Input #1
3 3
1 2 3
Sample Output #1
1
Sample Input #2
5 3
1 2 3 4 5
Sample Output #2
10
Sample Input #3
4 3
1 2 3 3
Sample Output #3
2
Sample Input #4
4 3
3 3 3 3
Sample Output #4
0
Sample Input #5
20 5
10 20 16 8 8 5 4 14 3 19 5 15 9 19 3 13 12 15 17 3
Sample Output #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
Hint :

$13\%:k = 3$,就跟這題一樣

$87\%:無特別限制$

Tags:
DP 數學
出處:
第六屆簡單的小競賽 [管理者: becaido(Caido) ]


ID User Problem Subject Hit Post Date
30888 becaido(Caido) h924
題解
29 2022-06-19 19:25