#line 1 "main.cpp" #include #line 2 "library/src/internal/barrett.hpp" #include namespace kyopro { namespace internal { /** * @brief Barrett Reduction */ class barrett { using u32 = uint32_t; using u64 = uint64_t; u32 m; u64 im; public: constexpr barrett() : m(0), im(0) {} constexpr barrett(u32 m_) : m(m_), im((u64) static_cast(-1) / m_ + 1) {} constexpr u32 get_mod() const { return m; } constexpr u32 reduce(int64_t a) const { return mul(a, 1); } constexpr u32 mul(u32 a, u32 b) const { if (!a || !b) { return 0; } u64 z = (u64)a * b; u64 x = (u64)(((__uint128_t)z * im) >> 64); u64 y = x * m; return (u32)(z - y + (z < y ? m : 0)); } }; }; // namespace internal }; // namespace kyopro /** * @ref * https://github.com/atcoder/ac-library/blob/master/atcoder/internal_math.hpp */ #line 2 "library/src/math/dynamic_modint.hpp" #include #include #line 3 "library/src/internal/montgomery.hpp" #include #include #line 5 "library/src/internal/type_traits.hpp" #include namespace kyopro { namespace internal { /* * @ref https://qiita.com/kazatsuyu/items/f8c3b304e7f8b35263d8 */ template struct first_enabled {}; template struct first_enabled, Args...> { using type = T; }; template struct first_enabled, Args...> : first_enabled {}; template struct first_enabled { using type = T; }; template using first_enabled_t = typename first_enabled::type; template struct int_least { static_assert(dgt <= 128); using type = first_enabled_t, std::enable_if, std::enable_if, std::enable_if, std::enable_if >; }; template struct uint_least { static_assert(dgt <= 128); using type = first_enabled_t, std::enable_if, std::enable_if, std::enable_if, std::enable_if >; }; template using int_least_t = typename int_least::type; template using uint_least_t = typename uint_least::type; template using double_size_uint_t = uint_least_t<2 * std::numeric_limits::digits>; template using double_size_int_t = int_least_t<2 * std::numeric_limits::digits>; }; // namespace internal }; // namespace kyopro #line 6 "library/src/internal/montgomery.hpp" namespace kyopro { namespace internal { using u32 = uint32_t; using u64 = uint64_t; using i32 = int32_t; using i64 = int64_t; using u128 = __uint128_t; using i128 = __int128_t; /** * @brief Montgomery Reduction */ template class Montgomery { static constexpr int lg = std::numeric_limits::digits; using LargeT = internal::double_size_uint_t; T mod, r, r2, minv; T inv() { T t = 0, res = 0; for (int i = 0; i < lg; ++i) { if (~t & 1) { t += mod; res += static_cast(1) << i; } t >>= 1; } return res; } public: Montgomery() = default; constexpr T get_mod() { return mod; } void set_mod(T m) { assert(m); assert(m & 1); mod = m; r = (-static_cast(mod)) % mod; r2 = (-static_cast(mod)) % mod; minv = inv(); } T reduce(LargeT x) const { u64 res = (x + static_cast(static_cast(x) * minv) * mod) >> lg; if (res >= mod) res -= mod; return res; } T generate(LargeT x) { return reduce(x * r2); } T mul(T x, T y) { return reduce((LargeT)x * y); } }; }; // namespace internal }; // namespace kyopro #line 6 "library/src/math/dynamic_modint.hpp" namespace kyopro { template class barrett_modint { using u32 = uint32_t; using u64 = uint64_t; using i32 = int32_t; using i64 = int64_t; using br = internal::barrett; static br brt; static u32 mod; u32 v; public: static void set_mod(u32 mod_) { brt = br(mod_); mod = mod_; } public: explicit constexpr barrett_modint() : v(0) { assert(mod); } explicit constexpr barrett_modint(i64 v_) : v(brt.reduce(v_)) { assert(mod); } u32 val() const { return v; } static u32 get_mod() { return mod; } using mint = barrett_modint; constexpr mint& operator=(i64 r) { v = brt.reduce(r); return (*this); } constexpr mint& operator+=(const mint& r) { v += r.v; if (v >= mod) { v -= mod; } return (*this); } constexpr mint& operator-=(const mint& r) { v += mod - r.v; if (v >= mod) { v -= mod; } return (*this); } constexpr mint& operator*=(const mint& r) { v = brt.mul(v, r.v); return (*this); } constexpr mint operator+(const mint& r) const { return mint(*this) += r; } constexpr mint operator-(const mint& r) const { return mint(*this) -= r; } constexpr mint operator*(const mint& r) const { return mint(*this) *= r; } constexpr mint& operator+=(i64 r) { return (*this) += mint(r); } constexpr mint& operator-=(i64 r) { return (*this) -= mint(r); } constexpr mint& operator*=(i64 r) { return (*this) *= mint(r); } friend mint operator+(i64 l, const mint& r) { return mint(l) += r; } friend mint operator+(const mint& l, i64 r) { return mint(l) += r; } friend mint operator-(i64 l, const mint& r) { return mint(l) -= r; } friend mint operator-(const mint& l, i64 r) { return mint(l) -= r; } friend mint operator*(i64 l, const mint& r) { return mint(l) *= r; } friend mint operator*(const mint& l, i64 r) { return mint(l) += r; } friend std::ostream& operator<<(std::ostream& os, const mint& mt) { os << mt.val(); return os; } friend std::istream& operator>>(std::istream& is, mint& mt) { i64 v_; is >> v_; mt = v_; return is; } template mint pow(T e) const { mint res(1), base(*this); while (e) { if (e & 1) { res *= base; } e >>= 1; base *= base; } return res; } mint inv() const { return pow(mod - 2); } mint& operator/=(const mint& r) { return (*this) *= r.inv(); } mint operator/(const mint& r) const { return mint(*this) *= r.inv(); } mint& operator/=(i64 r) { return (*this) /= mint(r); } friend mint operator/(const mint& l, i64 r) { return mint(l) /= r; } friend mint operator/(i64 l, const mint& r) { return mint(l) /= r; } }; }; // namespace kyopro template typename kyopro::barrett_modint::u32 kyopro::barrett_modint::mod; template typename kyopro::barrett_modint::br kyopro::barrett_modint::brt; namespace kyopro { template class dynamic_modint { using LargeT = internal::double_size_uint_t; static T mod; static internal::Montgomery mr; public: static void set_mod(T mod_) { mr.set_mod(mod_); mod = mod_; } static T get_mod() { return mod; } private: T v; public: dynamic_modint(T v_ = 0) { assert(mod); v = mr.generate(v_); } T val() const { return mr.reduce(v); } using mint = dynamic_modint; mint& operator+=(const mint& r) { v += r.v; if (v >= mr.get_mod()) { v -= mr.get_mod(); } return (*this); } mint& operator-=(const mint& r) { v += mr.get_mod() - r.v; if (v >= mr.get_mod) { v -= mr.get_mod(); } return (*this); } mint& operator*=(const mint& r) { v = mr.mul(v, r.v); return (*this); } mint operator+(const mint& r) { return mint(*this) += r; } mint operator-(const mint& r) { return mint(*this) -= r; } mint operator*(const mint& r) { return mint(*this) *= r; } mint& operator=(const T& v_) { (*this) = mint(v_); return (*this); } friend std::ostream& operator<<(std::ostream& os, const mint& mt) { os << mt.val(); return os; } friend std::istream& operator>>(std::istream& is, mint& mt) { T v_; is >> v_; mt = v_; return is; } template mint pow(P e) const { assert(e >= 0); mint res(1), base(*this); while (e) { if (e & 1) { res *= base; } e >>= 1; base *= base; } return res; } mint inv() const { return pow(mod - 2); } mint& operator/=(const mint& r) { return (*this) *= r.inv(); } mint operator/(const mint& r) const { return mint(*this) *= r.inv(); } mint& operator/=(T r) { return (*this) /= mint(r); } friend mint operator/(const mint& l, T r) { return mint(l) /= r; } friend mint operator/(T l, const mint& r) { return mint(l) /= r; } }; }; // namespace kyopro template T kyopro::dynamic_modint::mod; template kyopro::internal::Montgomery kyopro::dynamic_modint::mr; /** * @brief 動的modint * @docs docs/math/dynamic_modint.md */ #line 2 "library/src/math/rho.hpp" #include #include #line 3 "library/src/math/gcd.hpp" #include namespace kyopro { template constexpr T inline _gcd(T a, T b) { assert(a >= 0 && b >= 0); if (a == 0 || b == 0) return a + b; int d = std::min(__builtin_ctzll(a), __builtin_ctzll(b)); a >>= __builtin_ctzll(a), b >>= __builtin_ctzll(b); while (a != b) { if (!a || !b) { return a + b; } if (a >= b) { a -= b; a >>= __builtin_ctzll(a); } else { b -= a; b >>= __builtin_ctzll(b); } } return a << d; } template constexpr T ext_gcd(T a, T b, T& x, T& y) { x = 1, y = 0; T nx = 0, ny = 1; while (b) { T q = a / b; std::tie(a, b) = std::pair{b, a % b}; std::tie(x, nx) = std::pair{nx, x - nx * q}; std::tie(y, ny) = std::pair{ny, y - ny * q}; } return a; } }; // namespace kyopro #line 3 "library/src/math/miller.hpp" namespace kyopro { /** * @brief MillerRabin素数判定法 */ class miller { using i128 = __int128_t; using u128 = __uint128_t; using u64 = uint64_t; using u32 = uint32_t; template static constexpr bool miller_rabin(T n) { T d = n - 1; while (~d & 1) { d >>= 1; } const T rev = n - 1; if (mint::get_mod() != n) { mint::set_mod(n); } for (int i = 0; i < length; ++i) { if (n <= bases[i]) { return true; } T t = d; mint y = mint(bases[i]).pow(t); while (t != n - 1 && y.val() != 1 && y.val() != rev) { y *= y; t <<= 1; } if (y.val() != rev && (~t & 1)) return false; } return true; } // 底 static constexpr int bases_int[3] = {2, 7, 61}; static constexpr int bases_ll[7] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}; public: template static constexpr bool is_prime(T n) { if (n < 2) { return false; } else if (n == 2) { return true; } else if (~n & 1) { return false; }; if (std::numeric_limits::digits < 32 || n <= 1 << 30) { return miller_rabin>, bases_int, 3>(n); } else { return miller_rabin>, bases_ll, 7>(n); } return false; } }; }; // namespace kyopro /** * @docs docs/math/miller.md */ #line 2 "library/src/random/xor_shift.hpp" #include #line 4 "library/src/random/xor_shift.hpp" #include namespace kyopro { struct xor_shift32 { uint32_t rng; constexpr explicit xor_shift32(uint32_t seed) : rng(seed) {} explicit xor_shift32() : rng(std::chrono::steady_clock::now().time_since_epoch().count()) {} constexpr uint32_t operator()() { rng ^= rng << 13; rng ^= rng >> 17; rng ^= rng << 5; return rng; } }; struct xor_shift { uint64_t rng; constexpr xor_shift(uint64_t seed) : rng(seed) {} explicit xor_shift() : rng(std::chrono::steady_clock::now().time_since_epoch().count()) {} constexpr uint64_t operator()() { rng ^= rng << 13; rng ^= rng >> 7; rng ^= rng << 17; return rng; } }; }; // namespace kyopro /** * @brief xor shift */ #line 7 "library/src/math/rho.hpp" namespace kyopro { /** * @brief Pollard Rho 素因数分解法 */ class rho { using i128 = __int128_t; using u128 = __uint128_t; using u64 = uint64_t; using u32 = uint32_t; template static u64 find_factor(u64 n) { xor_shift32 rng(2023); if (~n & 1uL) { return 2; } if (kyopro::miller::is_prime(n)) { return n; } if (mint::get_mod() != n) { mint::set_mod(n); } while (1) { u64 c = rng(); const auto f = [&](mint x) -> mint { return x * x + c; }; mint x = rng(); mint y = f(x); u64 d = 1; while (d == 1) { d = _gcd( std::abs((long long)x.val() - (long long)y.val()), n); x = f(x); y = f(f(y)); } if (1 < d && d < n) { return d; } } exit(0); } template static std::vector rho_fact(u64 n) { if (n < 2) { return {}; } if (kyopro::miller::is_prime(n)) { return {n}; } std::vector v; std::vector st{n}; while (st.size()) { u64& m = st.back(); if (kyopro::miller::is_prime(m)) { v.emplace_back(m); st.pop_back(); } else { u64 d = find_factor(m); m /= d; st.emplace_back(d); } } return v; } public: static std::vector factorize(u64 n) { if (n < 2) { return {}; } auto v = (n < (1uL << 31) ? rho_fact>(n) : rho_fact>(n)); std::sort(v.begin(), v.end()); return v; } static std::vector> exp_factorize(u64 n) { std::vector pf = factorize(n); if (pf.empty()) { return {}; } std::vector> res; res.emplace_back(pf.front(), 1); for (int i = 1; i < (int)pf.size(); i++) { if (res.back().first == pf[i]) { res.back().second++; } else { res.emplace_back(pf[i], 1); } } return res; } static std::vector enumerate_divisor(u64 n) { std::vector> pf = rho::exp_factorize(n); std::vector divisor{1}; for (auto [p, e] : pf) { u64 pow = p; int sz = divisor.size(); for (int i = 0; i < e; ++i) { for (int j = 0; j < sz; ++j) divisor.emplace_back(divisor[j] * pow); pow *= p; } } return divisor; } }; }; // namespace kyopro /** * @docs docs/math/rho.md */ #line 5 "library/src/math/primitive_root.hpp" namespace kyopro { /** * @brief 原始根 */ inline uint64_t primitive_root(uint64_t p) { if (p == 2) return 1; auto pf = kyopro::rho::factorize(p - 1); pf.erase(std::unique(pf.begin(), pf.end()), pf.end()); for (auto& q : pf) { q = (p - 1) / q; } using ull = unsigned long long; if (dynamic_modint::get_mod() != p) { dynamic_modint::set_mod(p); } xor_shift rng(2023); while (1) { dynamic_modint g(rng()); if (g.val() == 0) continue; bool is_ok = true; for (auto q : pf) { if (dynamic_modint(g).pow(q).val() == 1) { is_ok = false; break; } } if (is_ok) { return g.val(); } } } }; // namespace kyopro #line 2 "library/src/stream.hpp" #include #include #include namespace kyopro { /** * 整数の入出力 */ template constexpr inline void readint(T& a) { a = 0; bool is_negative = false; char c = getchar_unlocked(); while (isspace(c)) { c = getchar_unlocked(); } if (c == '-') is_negative = true, c = getchar_unlocked(); while (isdigit(c)) { a = 10 * a + (c - '0'); c = getchar_unlocked(); } if (is_negative) a *= -1; } template constexpr inline void readint(Head& head, Tail&... tail) { readint(head); readint(tail...); } template void write_int(T a) { if (!a) { putchar_unlocked('0'); putchar_unlocked('\n'); return; } if (a < 0) putchar_unlocked('-'), a *= -1; char s[37]; int now = 37; while (a) { s[--now] = (char)'0' + a % 10; a /= 10; } while (now < 37) putchar_unlocked(s[now++]); } template constexpr inline void putint(T a) { if (!a) { putchar_unlocked('0'); putchar_unlocked('\n'); return; } if (a < 0) putchar_unlocked('-'), a *= -1; char s[37]; int now = 37; while (a) { s[--now] = (char)'0' + a % 10; a /= 10; } while (now < 37) putchar_unlocked(s[now++]); putchar_unlocked('\n'); } template constexpr inline void putint(Head head, Tail... tail) { putint(head); putint(tail...); } /** * 文字列の入出力 */ void readstr(std::string& str) { char c = getchar_unlocked(); while (isspace(c)) c = getchar_unlocked(); while (!isspace(c)) { str += c; c = getchar_unlocked(); } } void putstr(const std::string& str) { for (auto c : str) { putchar_unlocked(c); } putchar_unlocked('\n'); } }; // namespace kyopro /** * @brief fastIO */ #line 2 "library/src/template.hpp" #include #define rep(i, N) for (int i = 0; i < (N); i++) #define all(x) (x).begin(), (x).end() #define popcount(x) __builtin_popcountll(x) using i128 = __int128_t; using ll = long long; using ld = long double; using graph = std::vector>; using P = std::pair; constexpr int inf = 1e9; constexpr ll infl = 1e18; constexpr ld eps = 1e-6; const long double pi = acos(-1); constexpr uint64_t MOD = 1e9 + 7; constexpr uint64_t MOD2 = 998244353; constexpr int dx[] = {1, 0, -1, 0}; constexpr int dy[] = {0, 1, 0, -1}; template constexpr inline bool chmax(T1& a, T2 b) { return a < b && (a = b, true); } template constexpr inline bool chmin(T1& a, T2 b) { return a > b && (a = b, true); } #line 6 "main.cpp" #define debug(x) \ std::cout << #x << " : "; \ for (auto __ : x) std::cout << __.val() << ' '; \ std::cout << std::endl; using namespace std; using namespace atcoder; using namespace kyopro; using mint = atcoder::modint998244353; int main() { int p; readint(p); int g = primitive_root(p); // putint(g); vector a(p), b(p); for (int i = 1; i < p; ++i) readint(a[i]); for (int i = 1; i < p; ++i) readint(b[i]); vector ap(p - 1), bp(p - 1); vector pow(p); { for (int e = 0, pw = 1; e <= p; ++e) { pow[e] = pw; pw = (ll)pw * g % p; } } for (int i = 0; i < p - 1; ++i) { ap[i] = a[pow[i]]; bp[i] = b[pow[i]]; } // debug(ap) debug(bp); vector cp = convolution(ap, bp); // debug(cp); vector c(p); for (int i = p - 1; i < (int)cp.size(); ++i) { cp[i - p + 1] += cp[i]; } // debug(cp); for (int i = 0; i < p - 1; ++i) { c[pow[i]] = cp[i]; } // debug(c); for (int i = 1; i < p; ++i) putint(c[i].val()); }