TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

80.0% (4/5)

Tags

Description

今天帥哥總召在做字串問題時,突然看到了一個字串雜湊演算法,此演算法的實作方法如下:

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)$ ,由於這個問題太過簡單不需要勞煩帥哥總召親自出馬,請你們趕緊幫他算出這個問題的答案。

Input Format

輸入僅包含一行三個正整數 $n,m,p$ 如題目所述。

  • $1\le n\le 10^ 6$
  • $2\le m,p\le 30000$
  • 保證 $m$ 是質數

Output Format

請求出題目中所述問題的答案。已知答案可以表示成最簡分數 $\frac{P}{Q}$ ,請輸出 $P\times Q^ {-1} \text{ mod } 998243$ 的值。

Sample Input 1

1 3 2

Sample Output 1

307152

Sample Input 2

2 3 2

Sample Output 2

869279

Sample Input 3

12 13 16

Sample Output 3

366275

Sample Input 4

94513 8737 9024

Sample Output 4

280600

Sample Input 5

864303 27791 28661

Sample Output 5

892581

Hints

Problem Source

IOICamp 2021 Day5 pC

Subtasks

No. Testdata Range Constraints Score
1 0~4 範例測資 0
2 0~29 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 262144 65536 1 2
1 3000 262144 65536 1 2
2 3000 262144 65536 1 2
3 3000 262144 65536 1 2
4 3000 262144 65536 1 2
5 3000 262144 65536 2
6 3000 262144 65536 2
7 3000 262144 65536 2
8 3000 262144 65536 2
9 3000 262144 65536 2
10 3000 262144 65536 2
11 3000 262144 65536 2
12 3000 262144 65536 2
13 3000 262144 65536 2
14 3000 262144 65536 2
15 3000 262144 65536 2
16 3000 262144 65536 2
17 3000 262144 65536 2
18 3000 262144 65536 2
19 3000 262144 65536 2
20 3000 262144 65536 2
21 3000 262144 65536 2
22 3000 262144 65536 2
23 3000 262144 65536 2
24 3000 262144 65536 2
25 3000 262144 65536 2
26 3000 262144 65536 2
27 3000 262144 65536 2
28 3000 262144 65536 2
29 3000 262144 65536 2