問題一覧 > 教育的問題

No.3014 多項式ハッシュに関する教育的な問題

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 256 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 13
作問者 : antaanta
4 ProblemId : 804 / 自分の提出
問題文最終更新日: 2016-06-03 23:31:44

問題文

多項式ハッシュ(ローリングハッシュ, Karp-Rabin fingerprintとも呼ばれる)は、整数$P, B$をパラメーターとして取り、文字列$S$に対して \[ h_{P,B}(S) = (\sum_{i=1}^{|S|} B^{|S|-i} {\rm ord}(S_i)) \bmod P \] として定義される。ここで、$|S|$は$S$の長さを表す。${\rm ord}(c)$は文字$c$のアスキーコード('a'~'z'は97~122)を表す。$x \bmod P$として$x$を$P$で割った余りを表す。

$P$, $B$が与えられる。2つの文字列$S, T$であって、

  • $S \neq T$
  • $|S| = |T|$
  • $1 \le |S|, |T| \le 10^5$
  • $S, T$ はそれぞれ英小文字('a'~'z')のみからなる。
  • $h_{P,B}(S) = h_{P,B}(T)$
以上の条件を全て満たすものを1組求めよ。答えが複数ある場合はそのうちどれを出力してもよい。

入力

$P$
$B$

1行目と2行目に、多項式ハッシュ関数のパラメータである整数$P$と整数$B$が与えられる。
ただし、テストケースは1ケースだけであり、その内容は以下の通りであることが保証される。

1000000000000000003
123456789987654321

出力

$S$
$T$

問題文の条件を満たす$S, T$を2行に出力せよ。

サンプル

サンプル1
入力
1009
123
出力
bab
wbe

$h_{P,B}(S) = h_{P,B}(T) = 342$となる。

サンプル2
入力
1000000007
123456789
出力
hkmpqvm
axlszsi

$h_{P,B}(S) = h_{P,B}(T) = 409775251$となる。

ヒント

テストケースの$P,B$に特に深い意味はありません。

$0 \le B < P \le 10^{18}$であるとしても想定解法が任意の入力に対して制限時間内に必ず正しい答えを出力できることは保証されません。
ただし、単純な埋め込みではなく、テストケースに対しては制限時間内に答えを生成していることは確かです。
よって、埋め込み以外の方法で解いてください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。