今天帥哥總召在做字串問題時,突然看到了一個字串雜湊演算法,此演算法的實作方法如下:
int hash(string s, int n, int m, int p) {
int h = 0;
for (int i = 0; i < n; i++) h = (h * p + s[i]) % m;
return h;
}
其中 $s$ 是要拿來做雜湊的字串, $n$ 是字串 $s$ 的長度,而 $m,p$ 皆為雜湊函數的參數且滿足 $m$ 是質數。 聰明的帥哥總召當然知道雜湊函數是一種多對一的函數因此有可能會發生碰撞,因此他開始在想,在給定 $n,m,p$ 的情況下,若考慮所有長度為 $n$ 僅包含大寫英文字母 (A-Z) 的字串,從中挑出任兩個相異的字串發生碰撞的機率為何?兩字串 $s,t$ 發生碰撞代表 $hash(s,n,m,p)=hash(t,n,m,p)$ ,由於這個問題太過簡單不需要勞煩帥哥總召親自出馬,請你們趕緊幫他算出這個問題的答案。
輸入僅包含一行三個正整數 $n,m,p$ 如題目所述。
請求出題目中所述問題的答案。已知答案可以表示成最簡分數 $\frac{P}{Q}$ ,請輸出 $P\times Q^ {-1} \text{ mod } 998243$ 的值。
IOICamp 2021 Day5 pC
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~4 | 範例測資 | 0 |
2 | 0~29 | 無額外限制 | 100 |