#line 1 "test/yc_3014.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/3014"
#include <cstdint>
#include <cstdio>
#include <cassert>
#include <string>
#include <vector>
#line 1 "String/tree_attack.cpp"
/**
* @brief ロリハを衝突させるやつ (tree attack)
* @author えびちゃん
* @see https://codeforces.com/blog/entry/60442
*/
#include <cstddef>
#line 12 "String/tree_attack.cpp"
#include <algorithm>
#include <queue>
#include <tuple>
#line 16 "String/tree_attack.cpp"
#line 1 "utility/literals.cpp"
/**
* @brief ユーザ定義リテラル
* @author えびちゃん
*/
#line 11 "utility/literals.cpp"
constexpr intmax_t operator ""_jd(unsigned long long n) { return n; }
constexpr uintmax_t operator ""_ju(unsigned long long n) { return n; }
constexpr size_t operator ""_zu(unsigned long long n) { return n; }
constexpr ptrdiff_t operator ""_td(unsigned long long n) { return n; }
constexpr int8_t operator ""_i8(unsigned long long n) { return n; }
constexpr int16_t operator ""_i16(unsigned long long n) { return n; }
constexpr int32_t operator ""_i32(unsigned long long n) { return n; }
constexpr int64_t operator ""_i64(unsigned long long n) { return n; }
constexpr uint8_t operator ""_u8(unsigned long long n) { return n; }
constexpr uint16_t operator ""_u16(unsigned long long n) { return n; }
constexpr uint32_t operator ""_u32(unsigned long long n) { return n; }
constexpr uint64_t operator ""_u64(unsigned long long n) { return n; }
#line 18 "String/tree_attack.cpp"
std::vector<int> tree_attack(intmax_t p, intmax_t b, size_t k, int sigma = 2) {
struct node {
intmax_t value;
size_t pos, neg;
int coef;
node() = default;
node(intmax_t v, size_t l, size_t r, int c): value(v), pos(l), neg(r), coef(c) {}
bool operator <(node const& that) const { return value < that.value; }
};
std::vector<std::vector<node>> cl(k+1);
size_t n = 1_zu << k;
cl[0].assign(n, node(1, n-1, -1_zu, 1));
intmax_t pow = 1;
for (size_t j = 1; j < n; ++j) {
pow = __int128(pow) * b % p;
cl[0][j].value = pow;
cl[0][j].coef = 1;
intmax_t cur = pow;
for (int s = 2; s < sigma; ++s) {
cur = __int128(cur + pow) % p;
if (cur < cl[0][j].value) {
cl[0][j].value = cur;
cl[0][j].coef = s;
}
}
cl[0][j].pos = n-1-j;
}
std::sort(cl[0].begin(), cl[0].end());
std::vector<int> coef(n);
for (size_t i = 0; i < n; ++i)
coef[cl[0][i].pos] = cl[0][i].coef;
for (size_t i = 1; i <= k; ++i) {
cl[i].resize(n >> i);
for (size_t j = 0; j < cl[i].size(); ++j) {
size_t jl = j << 1 | 0;
size_t jr = j << 1 | 1;
if (cl[i-1][jr] < cl[i-1][jl]) {
cl[i][j].value = cl[i-1][jl].value - cl[i-1][jr].value;
cl[i][j].pos = jl;
cl[i][j].neg = jr;
} else {
cl[i][j].value = cl[i-1][jr].value - cl[i-1][jl].value;
cl[i][j].pos = jr;
cl[i][j].neg = jl;
}
}
std::sort(cl[i].begin(), cl[i].end());
if (cl[i][0].value > 0) continue;
std::vector<int> res(n, 0);
std::queue<std::tuple<size_t, size_t, bool>> q; // i, j, neg?
q.emplace(i-1, cl[i][0].pos, false);
q.emplace(i-1, cl[i][0].neg, true);
while (!q.empty()) {
auto [i, j, neg] = q.front();
q.pop();
if (i == -1_zu) {
if (j != -1_zu) res[j] = (neg? -coef[j]: +coef[j]);
continue;
}
q.emplace(i-1, cl[i][j].pos, neg);
q.emplace(i-1, cl[i][j].neg, !neg);
}
return res;
}
return {};
}
#line 10 "test/yc_3014.test.cpp"
int main() {
intmax_t p, b;
int sigma = 26;
scanf("%jd %jd %d", &p, &b, &sigma);
auto h = [&](auto const& s) -> intmax_t {
__int128 h = 0;
for (size_t i = 0; i < s.size(); ++i)
h = (h * b + s[i]) % p;
return h;
};
size_t k = 2;
std::string s, t;
do {
size_t n = 1_zu << k;
std::vector<int> a = tree_attack(p, b, k, sigma);
if (a.empty()) {
++k;
continue;
}
s = t = std::string(n, 'x');
for (size_t i = 0; i < a.size(); ++i) {
if (a[i] > 0) {
s[i] = 'a' + a[i];
t[i] = 'a';
}
if (a[i] < 0) {
s[i] = 'a';
t[i] = 'a' - a[i];
}
}
} while (s.empty());
// for special judges
// printf("%s\n", s.data());
// printf("%s\n", t.data());
std::vector<int> u(s.length());
for (size_t i = 0; i < s.length(); ++i)
u[i] = s[i]-t[i];
fprintf(stderr, "s: \"%s\"\n", s.data());
fprintf(stderr, "t: \"%s\"\n", t.data());
fprintf(stderr, "length: %zu\n", s.length());
fprintf(stderr, "h(s): %jd\n", h(s));
fprintf(stderr, "h(t): %jd\n", h(t));
fprintf(stderr, "h(s-t): %jd\n", h(u));
assert(h(u) == 0);
assert(h(s) == h(t));
assert(s != t);
}
test/yc_3014.test.cpp