問題一覧 > 教育的問題

No.8015 Anti-Rolling Hash

レベル : / AI推定難易度 : 1200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 256 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 39
作問者 : koyumeishi
お気に入りにしたユーザー ProblemId : 652 / 自分の提出
問題文最終更新日: 2026-06-26 14:38:27
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

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もしくは右上の雲マークをクリックしてアカウントを作成してください。