「MCOI-04」Dream and Strings
题目描述
Tommy 的加密系统用了如下的字符串哈希算法:
```cpp
int Hash(std::string s, int base, int mod) {
int result = 0;
for(int i=0; i<s.length(); i++)
result = (1ll * result * base + s[i]) % mod;
return result;
}
```
其中 $\texttt{base}$ 和 $\texttt{mod}$ 是给定参数,满足 $257\le\texttt{base}\le\texttt{mod}\le10^9+9$,并且 $\texttt{mod}$ 是一个质数。
现在 Dream 要破解 Tommy 的密文,先需要找到一个适合的哈希碰撞。给定 $\texttt{base}$,$\texttt{mod}$,和一个字符串 $S$,请找一个一样长度的字符串 $T$ 使得 $|S|=|T|$,$\texttt{hash(S)=hash(T)}$,但是 $S$ 和 $T$ 有至少一个位置不同。
如果有多个合法的 $T$,输出任意一个即可。
输入输出格式
输入格式
第一行,两个正整数 $\texttt{base}$ 和 $\texttt{mod}$。
第二行,一个由小写字母组成的字符串 $S$。
输出格式
一行,一个由小写字母组成的字符串 $T$,表示答案。
输入输出样例
输入样例 #1
257 997
aabdccbabdcdcadbcabcabaabdbbddbaabcadabcbcdacbbaac
输出样例 #1
lmzaeccihyailccmzzaxshssgbvjvhthllyofzudraatifnzxy
说明
#### 数据规模与约定
如果 $S$ 是一个字符串,$|S|$ 是它的长度。
对于前 $10\%$ 的数据,$\texttt{mod}=997$。
对于前 $40\%$ 的数据,$|S|=2\times10^5$ 并且 $S$ 随机。
对于 $100\%$ 的数据,$50\le|S|\le2\times10^5$,$257\le\texttt{base}<\texttt{mod}\le10^9+9$,$\texttt{mod}$ 是一个质数。
#### 说明
[Minecraft OI Round 4](https://www.luogu.com.cn/contest/33344) D
idea & solution:w33z8kqrqk8zzzx33 check:MatKave