有一天,一個叫做Prak Nibar的人想要用Rabin fingerprint來對字串做雜湊。
你應該已經要知道Rabin fingerprint是甚麼了,因為培訓有講過。如果你沒參加培訓,可以看以下的定義:
對於一個字串$A=a_0a_1a_2\cdots a_{N-1}$,其Rabin fingerprint $f(A)$定義為:
$\displaystyle f(A)=\sum_{i=0}^ {N-1}g(a_i)p^ {N-i-1} \mod M$
其中$p, M\in\mathbb{N}; gcd(p, M)=1$,$g : \Sigma\rightarrow\mathbb{N}\cap[0,p)$是單射函數且$\Sigma$是字串$A$的字元集。
然而,因為Nibar覺得模運算常數太大了,所以他想要用位元運算解決一切:只取結果的後$m$個位元不就是模$2^ m$嗎!
雖然他人品沒有很好,但是他知道M取愈大結果會愈好,而他不滿足於現有的資料結構,因此自己實作了一個$m$位元的整數結構。
你對雜湊函數有深刻的了解,所以知道這其實超乎人品之外,但是你必須要說服Nibar。
所以你得構造兩個相異且由小寫英文字母組成的字串,使得不管他選取什麼樣的$p$(當然要符合$gcd(p, M)=1$),這兩個字串的雜湊值永遠相同。
保證他使用的$g(c)$一定會把英文字母按照順序對應到連續的正整數上。(也就是說,如果$g(^ \backprime a')=k$,那麼$g(^ \backprime b')=k+1$,以此類推。)
輸入只有一個正整數$m\leq 256$,代表Nibar所使用的$M=2^ m$。
子任務(測資) | 額外限制 | 分數 |
1 (0~2) | $m \leq 4$ | 17 |
2 (0~5) | $m \leq 15$ | 31 |
3 (0~8) | 無限制 | 52 |
輸出兩行相異的字串,每行一個字串,代表這兩個字串不管選取什麼$p$,在模$M$之下雜湊值永遠相同。
保證一定存在這樣的字串,且如果$m<=32$,長度不超過$10^ 5$;其它情況長度不超過$10^ 7$。
如果你輸出了超過上述保證長度的字串,你會得到一個WA。
Problem set / Description by Yihda Yol
建國中學105學年度校內第二次模擬賽 pE
No. | Testdata Range | Score |
---|---|---|
1 | 0~2 | 17 |
2 | 0~5 | 31 |
3 | 0~8 | 52 |