#include #include #include // #include // https://github.com/amiast/cpp-utility #ifndef KOTONE_PRIME_HPP #define KOTONE_PRIME_HPP 1 #include #include #include #include #include // #include // https://github.com/amiast/cpp-utility #ifndef KOTONE_RANDOM_HPP #define KOTONE_RANDOM_HPP 1 #include namespace kotone { // Returns a random unsigned 64-bit integer. uint64_t randint() { static std::random_device rd; static std::mt19937_64 gen(rd()); return gen(); } // Reference: https://codeforces.com/blog/entry/62393 uint64_t splitmix64(uint64_t x) noexcept { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } // A randomized hash for integers. struct randomized_hash { std::size_t operator()(uint64_t x) const { static const uint64_t SEED = randint(); return splitmix64(x ^ SEED); } }; } // namespace kotone #endif // KOTONE_RANDOM_HPP // #include // https://github.com/amiast/cpp-utility #ifndef KOTONE_MOD_MATH_HPP #define KOTONE_MOD_MATH_HPP 1 #include #include namespace kotone { // Returns the non-negative remainder produced from dividing `n` by `m`. // Requires `m > 0`. template uint64_t mod(T n, uint64_t m) { assert(m > 0u); if (n >= 0) return uint64_t(n) % m; if (m < 1ULL << 63) { int64_t sm = m; return (n % sm + sm) % sm; } if (n == -1LL << 63) return m - (1ULL << 63); return m - -n; } // Returns the non-negative remainder produced from dividing `n` by `m`. // Requires `m > 0`. template uint64_t mod(T n, uint64_t m) { assert(m > 0u); return n % m; } // Returns `(a + b) % m`. // Requires `m > 0`. template uint64_t sum_mod(S a, T b, uint64_t m) { uint64_t ua = mod(a, m), ub = mod(b, m); uint64_t result = ua + ub; if (result < ua) result -= m; if (result >= m) result -= m; return result; } // Returns `a * b % m`. // Requires `m > 0`. // Requires compiler-provided type `__int128`. template uint64_t prod_mod(S a, T b, uint64_t m) { uint64_t ua = mod(a, m), ub = mod(b, m); return __int128(ua) * ub % m; } // Returns `pow(n, k) % m`. // Returns `1 % m` if `n == k == 0`. // Requires `m > 0`. // Requires compiler-provided type `__int128`. template uint64_t pow_mod(T n, uint64_t k, uint64_t m) { assert(m > 0u); if (k == 0) return m > 1u; uint64_t un = mod(n, m); uint64_t result = 1 % m; while (k) { if (k & 1u) result = prod_mod(result, un, m); un = prod_mod(un, un, m); k >>= 1; } return result; } } #endif // KOTONE_MOD_MATH_HPP namespace kotone { // Retuens a `bool` indicating whether `n` is prime. // Requires compiler-provided type `__int128`. bool is_prime(int64_t n) { constexpr static int bases[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}; if (n <= 2) return n == 2; if (~n & 1) return false; int64_t s = std::bit_width(uint64_t((n - 1) & -(n - 1))) - 1; int64_t d = (n - 1) >> s; for (int a : bases) { if (a >= n) continue; int64_t x = pow_mod(a, d, n); if (x == 1 || x == n - 1) continue; bool flag = true; for (int t = 0; t < s - 1; t++) { x = prod_mod(x, x, n); if (x == n - 1) { flag = false; break; } } if (flag) return false; } return true; } // Returns a factor of composite number `n`. // Requires `n` to be a positive composite number. // Requires compiler-provided type `__int128`. int64_t pollards_rho(int64_t n) { assert(n >= 4); if (n % 2 == 0) return 2; while (true) { int64_t b = randint() % (n - 3) + 1; auto g = [n, b](int64_t x) { return sum_mod(prod_mod(x, x, n), b, n); }; int64_t x = randint() % n; int64_t y = x, d = 1; while (d == 1) { x = g(x); y = g(g(y)); d = std::gcd(std::abs(x - y), n); } if (d != n) return d; } } // Returns a vector containing all prime factors of `n`. // The order of factors is undefined. // Requires `n` to be a positive integer. // Requires compiler-provided type `__int128`. std::vector factorize(int64_t n) { assert(n > 0); auto rec = [&](auto &rec, int64_t n, std::vector &vec) { if (n == 1) return; if (is_prime(n)) { vec.push_back(n); return; } int64_t d = pollards_rho(n); rec(rec, d, vec); rec(rec, n / d, vec); }; std::vector result; rec(rec, n, result); return result; } // Returns the least primitive root of prime `p`. // Requires `p` to be a prime. // Requires compiler-provided type `__int128`. int64_t least_primitive_root(int64_t p) { std::vector factors = factorize(p - 1); std::sort(factors.begin(), factors.end()); factors.erase(std::unique(factors.begin(), factors.end()), factors.end()); for (int64_t n = 1; n < p; n++) { bool flag = true; for (int64_t q : factors) { if (pow_mod(n, (p - 1) / q, p) == 1) { flag = false; break; } } if (flag) return n; } } } // namespace kotone #endif // KOTONE_PRIME_HPP using mint = atcoder::modint998244353; int main() { int P; std::cin >> P; std::vector A(P), B(P); for (int i = 1; i < P; i++) std::cin >> A[i]; for (int i = 1; i < P; i++) std::cin >> B[i]; int g = kotone::least_primitive_root(P); int64_t acc = 1; std::vector exp_to_int(P - 1); for (int i = 0; i < P - 1; i++) { exp_to_int[i] = acc; acc *= g; acc %= P; } std::vector pa(P - 1), pb(P - 1); for (int i = 0; i < P - 1; i++) pa[i] = A[exp_to_int[i]]; for (int i = 0; i < P - 1; i++) pb[i] = B[exp_to_int[i]]; std::vector prod = atcoder::convolution(pa, pb); std::vector result(P); for (int i = 0; i < P * 2 - 3; i++) result[exp_to_int[i % (P - 1)]] += prod[i]; for (int i = 1; i < P; i++) std::cout << result[i].val() << ' '; std::cout << std::endl; }