No.8015 Anti-Rolling Hash
タグ : / 解いたユーザー数 39
作問者 :
koyumeishi
Problem Statement
The other day, Taro implemented the following function that computes the hash value of a string.
(Reference: Rabin-Karp string search algorithm)
The hash value of a string $S$ of length $n$ is calculated by the following formula.
$$Hash(S)=\sum_{i=0}^{n-1}\ (S_i\ \times\ a^{n-1-i}\ ) \pmod{b}$$
Here, $S_i$ denotes the ASCII code of the $i$-th character of the string.
For example, if $S = $"abcz", then $S_0 = 97$, $S_1 = 98$, $S_2 = 99$, $S_3 = 122$.
However, since Taro implemented it just by imitating what he had seen, he does not really understand what numbers he should choose for $a$ and $b$.
So, for the time being, Taro has apparently decided to choose $a$ and $b$ at random from the integers between $1$ and $10^5$, inclusive.
Given the $a$, $b$ chosen by Taro as input, output two strings $S$, $T$ whose hash values are equal.
Here, $S$ and $T$ must be different strings consisting of lowercase letters 'a'-'z', and their lengths must be equal and at most $10^6$.
The implementation (C++) of the hash function used by the judge is as follows.
unsigned long long get_hash(string s, unsigned long long a, unsigned long long b){
unsigned long long hash = 0;
for(int i = 0; i < s.size(); i++){
hash = (hash * a + s[i]) % b;
}
return hash;
}
Input
$a$ $b$
$a$ and $b$ are given separated by a space.
$1\leq a \leq 10^5$
$1\leq b \leq 10^5$
Output
$S$ $T$
Output $S$ on the first line and $T$ on the second line.
$S$ and $T$ must satisfy the following constraints.
$Hash(S) = Hash(T)$
$1 \leq |S| = |T| \leq 10^6$
$S \neq T$
$S$ and $T$ consist only of lowercase letters 'a'-'z'
Sample
Sample 1
Input
3 7
Output
ulwoorwpxrhrfcckazth ulwoarwpxrhrfcckazth
This is one example of S, T.
Both have a hash value of 4.
Sample 2
Input
7 9
Output
talybdsmdphtmvhutkxb talybdsmdphtgvtutkxn
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。