#1463. Hash Killer 1.1

Hash Killer 1.1

题目描述

小 Z 近日学会了字符串哈希,他用 C++ 写了如下的哈希函数。

typedef __int128 bi;
bi hash(std::string s) {
    bi v = 0;
    for (char c : s) v = (v * B + c) % M;
    return v;
}

形式化地,字符串 c0c1cn1c_0c_1\cdots c_{n-1} 的 hash 值为 (i=0n1Bn1ici)modM(\sum_{i=0}^{n-1} B^{n-1-i}c_i)\bmod M,这里的 cc 即各位的 ascii 码。例如,当 B=100B=100M=998244353M=998244353 时,hash(abc)=979899\mathrm{hash}(\texttt{abc})=979899

你认为这个哈希方法非常脆弱,于是打算卡掉它。对于给定的三个整数 BBMMxx,请构造出一个长度不超过 1000010000 的由小写字母组成的非空字符串,使得它使用如上函数算出的哈希值为 xx

输入格式

一行三个整数,BBMMxx

输出格式

一行一个由小写字母组成的非空字符串,长度不超过 1000010000。如有多解,可以输出任意一个。

样例

200 100000000000000003 1234567890
aadffikdnakjaoaicmibmommolegeifpyanglichuan

数据范围与提示

对于所有数据,BB[130,200][130,200] 中均匀随机生成。xx 的生成方法为,随机生成一个长度为 10001000 的由小写字母组成的字符串,计算它的哈希值作为 xx,因此解一定存在。

本题共有 33 个子任务,每个子任务恰有 2020 个测试点。子任务的得分为每个测试点得分之和,每个子任务内每个测试点分值相同。

Subtask 114040 pts):MM[2,109][2,10^9] 范围内的随机质数。

Subtask 222020 pts):MM[2,1016][2,10^{16}] 范围内的随机质数。

Subtask 334040 pts):MM[2,1018][2,10^{18}] 范围内的随机质数。