題外話，
這題編號是 $520$ 欸 XD
排列，
是將相異物件或符號根據確定的順序重排。
舉例來說，
$ABC$ 這個序列，
可能的排列有：$ABC,\ ACB,\ BAC,\ BCA,\ CAB,\ CBA$，
總共六種。
那要怎麼算排列總數呢？
一種一種列出來實在太慢了，
透過觀察可以發現，
X _ _ 第一位可以放 $A,\ B,\ C$ 三種選擇，
_ X _ 第二位可以放另外兩種選擇（第一位放過的不能放），
_ _ X 第三位只能放一種選擇。
$\implies3\times2\times1=6$，
這樣就可以算出全排列數。
但是如果有重覆的元素，
比如 $ABBC$，
打個標籤 $AB_1B_2C$ 和 $AB_2B_1C$ 其實是一樣的，
所以重覆的要除掉，
$\implies4\times3\times2\times1\div2=12$。
再簡單一點好了，
假設現在的序列和其對應的數量如下：
$A\to2,\ B\to4,\ C\to3,\ D\to5$。
那麼排列的總數即是 $\frac{14!}{2!\times5!\times3!\times5!}$。
公式：
$$全排列數=\frac{(總個數)!}{(A的個數)!\times (B的個數)!\times(C的個數)!\dots}\ \ \ \ \ \ \ \ \ \ \ $$
其中 $!\ \ $ 符號代表「階乘 (factorial)」，
定義：
$$n!=n\times (n-1)\times (n-2)\times\dots\times1$$
但是數字有可能過大，
為了方便輸出，
所以輸出模運算 (取餘數) 的結果，
舉例：
$$100\equiv1\pmod3$$
對於階乘 $+$ 除法 $+$ 模運算是個很大的問題，
因為除法在模運算下不會成立，
舉例：
$$15\div6\pmod{4}\ne15\pmod{4}\div6\pmod{4}$$
可行的解決方法是「$質因數分解$」，
把階乘運算拆成質因數相乘 (用陣列 index 存數字、arr[index] 存指數)，
那在做除法的時候相當於指數相減 ($2^7\div2^3=2^4$，相當於指數相減)，
最後再把所有質因數和其指數次方乘起來，
在乘的時候可以做模運算，
就可以避免溢位且可達到題目所滿足的答案。
舉例：
以 $ABBCCC$ 為例，
分子：
$$6!=2^4\times3^2\times5$$
分母：
$$2!\times3!=2^2\times3$$
做除法 (指數相減) 得到答案：
$$2^2\times3\times5$$
假設 $M=19$，那可得到答案：
$$2^2\times3\times5\equiv3\pmod{19}$$
單筆測資。
只有一行輸入 $M$ 和 $S$。
輸出 $S$ 的全排列數模運算 $M$ 的結果。
# 範例測資 01 : 5 ABC # 範例測資 02 : 19 ABBCCC
# 範例測資 01 : 1 # 範例測資 02 : 3
# $2\le M\le 1000000$。
# $S$ 為大寫英文字母之組合。
# 字母的排列順序不會影響答案，$ABC,\ CAB$ 的全排列數都是 $6$。
# subtask 30% : 字串不會出現重複，$2\le|S|\le26$。
# subtask 60% : $2\le|S|\le200$。
# subtask 10% : $900\le|S|\le1000$。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||