No.3015 アンチローリングハッシュ
タグ : / 解いたユーザー数 35
作問者 : koyumeishi
問題文
太郎君は先日、文字列のハッシュ値を得る次のような関数を実装しました。
(参考:ラビン-カープ文字列検索アルゴリズム)
長さ $n$ の文字列 $S$ のハッシュ値は次の式で計算される。
$$Hash(S)=\sum_{i=0}^{n-1}\ (S_i\ \times\ a^{n-1-i}\ ) \pmod{b}$$
ここで、$S_i$ は文字列の $i$ 番目の文字のASCIIコード番号を指す。
例えば $S = $"abcz"ならば、$S_0 = 97$、$S_1 = 98$、$S_2 = 99$、$S_3 = 122$ である。
しかし、太郎君は見様見真似で実装したため、 $a$ と $b$ にどのような数を選んだらいいのかよく分かっていません。
そこで太郎君はとりあえず、 $a$ と $b$ を $1$ 以上 $10^5$ 以下の整数の中からランダムに選ぶ事にしたようです。
太郎君が選んだ $a$, $b$ が入力に与えられるので、
ハッシュ値が等しくなるような2つの文字列$S$, $T$を出力してください。
ただし$S$と$T$は小文字のアルファベット'a'-'z'で構成される異なる文字列で、その長さは等しく、かつ$10^6$以下でなければなりません。
ジャッジに使われるハッシュ関数の実装(C++)は次の通りです。
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; }
入力
$a$ $b$
$a$ と $b$ が空白区切りで与えられます。
$1\leq a \leq 10^5$
$1\leq b \leq 10^5$
出力
$S$ $T$
1行目に$S$、2行目に$T$を出力してください。
$S$と$T$は以下の制約を満たす必要があります。
$Hash(S) = Hash(T)$
$1 \leq |S| = |T| \leq 10^6$
$S \neq T$
$S$、$T$は小文字のアルファベット'a'-'z'のみで構成される
サンプル
サンプル1
入力
3 7
出力
ulwoorwpxrhrfcckazth ulwoarwpxrhrfcckazth
S,Tの一例です。
どちらもハッシュ値が4になります。
サンプル2
入力
7 9
出力
talybdsmdphtmvhutkxb talybdsmdphtgvtutkxn
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。