c011: 排列第幾個?
Tags : string 排列組合
Accepted rate : 8人/15人 ( 53% ) [非即時]
評分方式:
Tolerant

最近更新 : 2023-06-05 13:26

Content

N 個可重複的英文字母排成一列,共有幾種排法?比如說,兩個 A 一個 B 一個 C 排成一列共有12種排法,依照字典排序法依序如下:AABC、AACB、ABAC、ABCA、ACAB、ACBA、BAAC、BACA、BCAA、CAAB、CABA、CBAA。
現在給定一個排序 π,請問 π 是該些字母排列中的第幾個?上述中第 0 個為 AABC,第 1 個為 AACB,而 BAAC 是兩個 A 一個 B 一個 C 的排列中依照字典排序法中的第 6 個。若 π 是該些字母排列中的第 K 個,為方便輸出,給定一個整數 D,輸出 K 除以 D 的餘數。

Input

輸入只有一行,先有一個整數 D(1 < D < 1000000000),再有一串可重複字母的英文字串 S,中間以空白隔開。

子任務額外限制分數
字母字母不重複,長度最多為 510
2字串字母不重複,長度最多為 5220
3字串字母可重複,長度最多為 1030
4字串字母可重複,長度最多為 1024         40
Output

假設字串 S 為該些字母的排列中的第 K 個,輸出 K 除以 D 的餘數。

Sample Input #1
50 CBA

Sample Output #1
5

Sample Input #2
5 BaaC

Sample Output #2
2

Sample Input #3
5 BAAC
Sample Output #3
1
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1K
公開 測資點#5 (5%): 1.0s , <1K
公開 測資點#6 (5%): 1.0s , <1K
公開 測資點#7 (5%): 1.0s , <1K
公開 測資點#8 (5%): 1.0s , <1K
公開 測資點#9 (5%): 1.0s , <1K
公開 測資點#10 (5%): 1.0s , <1K
公開 測資點#11 (5%): 1.0s , <1K
公開 測資點#12 (5%): 1.0s , <1M
公開 測資點#13 (5%): 1.0s , <1K
公開 測資點#14 (5%): 1.0s , <1K
公開 測資點#15 (5%): 1.0s , <1K
公開 測資點#16 (5%): 1.0s , <1M
公開 測資點#17 (5%): 1.0s , <1K
公開 測資點#18 (5%): 1.0s , <1M
公開 測資點#19 (5%): 1.0s , <1M
Hint :

本題出自 2018 TOI Pre (TIOJ 2052)

Tags:
string 排列組合
出處:
2018 TOI PreTIOJ 2052 [管理者:
nevikw39 ($\mathscr{nevikw}\pmb{39}\in\mathbf{37}^{th}$)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」