結果
問題 | No.931 Multiplicative Convolution |
ユーザー | Haar |
提出日時 | 2020-11-07 03:19:40 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 148 ms / 2,000 ms |
コード長 | 9,351 bytes |
コンパイル時間 | 2,378 ms |
コンパイル使用メモリ | 215,052 KB |
実行使用メモリ | 8,832 KB |
最終ジャッジ日時 | 2024-07-22 14:14:21 |
合計ジャッジ時間 | 5,790 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 3 ms
5,376 KB |
testcase_07 | AC | 17 ms
5,376 KB |
testcase_08 | AC | 148 ms
8,704 KB |
testcase_09 | AC | 133 ms
8,576 KB |
testcase_10 | AC | 143 ms
8,576 KB |
testcase_11 | AC | 134 ms
8,320 KB |
testcase_12 | AC | 137 ms
7,552 KB |
testcase_13 | AC | 145 ms
8,576 KB |
testcase_14 | AC | 145 ms
8,704 KB |
testcase_15 | AC | 146 ms
8,832 KB |
testcase_16 | AC | 144 ms
8,704 KB |
ソースコード
#line 1 "main.cpp" #include <bits/stdc++.h> #line 4 "/home/haar/Downloads/kyopro-lib/Mylib/Number/Mint/mint.cpp" namespace haar_lib { template <int32_t M> class modint { uint32_t val_; public: constexpr static auto mod(){return M;} constexpr modint(): val_(0){} constexpr modint(int64_t n){ if(n >= M) val_ = n % M; else if(n < 0) val_ = n % M + M; else val_ = n; } constexpr auto& operator=(const modint &a){val_ = a.val_; return *this;} constexpr auto& operator+=(const modint &a){ if(val_ + a.val_ >= M) val_ = (uint64_t)val_ + a.val_ - M; else val_ += a.val_; return *this; } constexpr auto& operator-=(const modint &a){ if(val_ < a.val_) val_ += M; val_ -= a.val_; return *this; } constexpr auto& operator*=(const modint &a){ val_ = (uint64_t)val_ * a.val_ % M; return *this; } constexpr auto& operator/=(const modint &a){ val_ = (uint64_t)val_ * a.inv().val_ % M; return *this; } constexpr auto operator+(const modint &a) const {return modint(*this) += a;} constexpr auto operator-(const modint &a) const {return modint(*this) -= a;} constexpr auto operator*(const modint &a) const {return modint(*this) *= a;} constexpr auto operator/(const modint &a) const {return modint(*this) /= a;} constexpr bool operator==(const modint &a) const {return val_ == a.val_;} constexpr bool operator!=(const modint &a) const {return val_ != a.val_;} constexpr auto& operator++(){*this += 1; return *this;} constexpr auto& operator--(){*this -= 1; return *this;} constexpr auto operator++(int){auto t = *this; *this += 1; return t;} constexpr auto operator--(int){auto t = *this; *this -= 1; return t;} constexpr static modint pow(int64_t n, int64_t p){ if(p < 0) return pow(n, -p).inv(); int64_t ret = 1, e = n % M; for(; p; (e *= e) %= M, p >>= 1) if(p & 1) (ret *= e) %= M; return ret; } constexpr static modint inv(int64_t a){ int64_t b = M, u = 1, v = 0; while(b){ int64_t t = a / b; a -= t * b; std::swap(a, b); u -= t * v; std::swap(u, v); } u %= M; if(u < 0) u += M; return u; } constexpr static auto frac(int64_t a, int64_t b){return modint(a) / modint(b);} constexpr auto pow(int64_t p) const {return pow(val_, p);} constexpr auto inv() const {return inv(val_);} friend constexpr auto operator-(const modint &a){return modint(M - a.val_);} friend constexpr auto operator+(int64_t a, const modint &b){return modint(a) + b;} friend constexpr auto operator-(int64_t a, const modint &b){return modint(a) - b;} friend constexpr auto operator*(int64_t a, const modint &b){return modint(a) * b;} friend constexpr auto operator/(int64_t a, const modint &b){return modint(a) / b;} friend std::istream& operator>>(std::istream &s, modint &a){s >> a.val_; return s;} friend std::ostream& operator<<(std::ostream &s, const modint &a){s << a.val_; return s;} template <int N> static auto div(){ static auto value = inv(N); return value; } explicit operator int32_t() const noexcept {return val_;} explicit operator int64_t() const noexcept {return val_;} }; } #line 7 "/home/haar/Downloads/kyopro-lib/Mylib/Convolution/ntt_convolution.cpp" namespace haar_lib { template <typename T, int PRIM_ROOT, int MAX_SIZE> class number_theoretic_transform { public: using value_type = T; constexpr static int primitive_root = PRIM_ROOT; constexpr static int max_size = MAX_SIZE; private: const int MAX_POWER_; std::vector<T> BASE_, INV_BASE_; public: number_theoretic_transform(): MAX_POWER_(__builtin_ctz(MAX_SIZE)), BASE_(MAX_POWER_ + 1), INV_BASE_(MAX_POWER_ + 1) { static_assert((MAX_SIZE & (MAX_SIZE - 1)) == 0, "MAX_SIZE must be power of 2."); T t = T::pow(PRIM_ROOT, (T::mod() - 1) >> (MAX_POWER_ + 2)); T s = t.inv(); for(int i = MAX_POWER_; --i >= 0;){ t *= t; s *= s; BASE_[i] = -t; INV_BASE_[i] = -s; } } void run(std::vector<T> &f, bool INVERSE = false) const { const int n = f.size(); assert((n & (n - 1)) == 0 and n <= MAX_SIZE); // データ数は2の冪乗個 if(INVERSE){ for(int b = 1; b < n; b <<= 1){ T w = 1; for(int j = 0, k = 1; j < n; j += 2 * b, ++k){ for(int i = 0; i < b; ++i){ const auto s = f[i + j]; const auto t = f[i + j + b]; f[i + j] = s + t; f[i + j + b] = (s - t) * w; } w *= INV_BASE_[__builtin_ctz(k)]; } } const T t = T::inv(n); for(auto &x : f) x *= t; }else{ for(int b = n >> 1; b; b >>= 1){ T w = 1; for(int j = 0, k = 1; j < n; j += 2 * b, ++k){ for(int i = 0; i < b; ++i){ const auto s = f[i + j]; const auto t = f[i + j + b] * w; f[i + j] = s + t; f[i + j + b] = s - t; } w *= BASE_[__builtin_ctz(k)]; } } } } template <typename U> std::vector<T> convolve(std::vector<U> f, std::vector<U> g) const { const int m = f.size() + g.size() - 1; int n = 1; while(n < m) n *= 2; std::vector<T> f2(n), g2(n); for(int i = 0; i < (int)f.size(); ++i) f2[i] = (int64_t)f[i]; for(int i = 0; i < (int)g.size(); ++i) g2[i] = (int64_t)g[i]; run(f2); run(g2); for(int i = 0; i < n; ++i) f2[i] *= g2[i]; run(f2, true); return f2; } template <typename U> std::vector<T> operator()(std::vector<U> f, std::vector<U> g) const { return convolve(f, g); } }; template <typename T> std::vector<T> convolve_general_mod(std::vector<T> f, std::vector<T> g){ static constexpr int M1 = 167772161, P1 = 3; static constexpr int M2 = 469762049, P2 = 3; static constexpr int M3 = 1224736769, P3 = 3; auto res1 = number_theoretic_transform<modint<M1>, P1, 1 << 20>().convolve(f, g); auto res2 = number_theoretic_transform<modint<M2>, P2, 1 << 20>().convolve(f, g); auto res3 = number_theoretic_transform<modint<M3>, P3, 1 << 20>().convolve(f, g); const int n = res1.size(); std::vector<T> ret(n); const int64_t M12 = (int64_t)modint<M2>::inv(M1); const int64_t M13 = (int64_t)modint<M3>::inv(M1); const int64_t M23 = (int64_t)modint<M3>::inv(M2); for(int i = 0; i < n; ++i){ const int64_t r[3] = {(int64_t)res1[i], (int64_t)res2[i], (int64_t)res3[i]}; const int64_t t0 = r[0] % M1; const int64_t t1 = (r[1] - t0 + M2) * M12 % M2; const int64_t t2 = ((r[2] - t0 + M3) * M13 % M3 - t1 + M3) * M23 % M3; ret[i] = T(t0) + T(t1) * M1 + T(t2) * M1 * M2; } return ret; } } #line 3 "/home/haar/Downloads/kyopro-lib/Mylib/Number/Mod/mod_pow.cpp" namespace haar_lib { constexpr int64_t mod_pow(int64_t n, int64_t p, int64_t m){ int64_t ret = 1; while(p > 0){ if(p & 1) (ret *= n) %= m; (n *= n) %= m; p >>= 1; } return ret; } } #line 3 "/home/haar/Downloads/kyopro-lib/Mylib/Number/Prime/primitive_root.cpp" namespace haar_lib { constexpr int primitive_root(int p){ int pf[30] = {}; int k = 0; { int n = p - 1; for(int64_t i = 2; i * i <= p; ++i){ if(n % i == 0){ pf[k++] = i; while(n % i == 0) n /= i; } } if(n != 1) pf[k++] = n; } for(int g = 2; g <= p; ++g){ bool ok = true; for(int i = 0; i < k; ++i){ if(mod_pow(g, (p - 1) / pf[i], p) == 1){ ok = false; break; } } if(not ok) continue; return g; } return -1; } } #line 5 "/home/haar/Downloads/kyopro-lib/Mylib/IO/join.cpp" namespace haar_lib { template <typename Iter> std::string join(Iter first, Iter last, std::string delim = " "){ std::stringstream s; for(auto it = first; it != last; ++it){ if(it != first) s << delim; s << *it; } return s.str(); } } #line 8 "main.cpp" #ifdef DEBUG #include <Mylib/Debug/debug.cpp> #else #define dump(...) #endif using namespace haar_lib; constexpr int mod = 998244353; constexpr int prim_root = primitive_root(mod); using mint = modint<mod>; using NTT = number_theoretic_transform<mint, prim_root, 1 << 20>; const static auto ntt = NTT(); int main(){ std::cin.tie(0); std::ios::sync_with_stdio(false); int P; std::cin >> P; std::vector<mint> 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 p_root = primitive_root(P); std::vector<int> index(P); { int s = 1; for(int i = 0; i < P; ++i){ index[s] = i; (s *= p_root) %= P; } } std::vector<mint> a(P), b(P); for(int i = 1; i < P; ++i){ a[index[i]] = A[i]; b[index[i]] = B[i]; } auto c = ntt(a, b); //dump(p_root, a, b, c); std::vector<mint> ans(P); for(int i = 0; i < (int)c.size(); ++i){ ans[mod_pow(p_root, i, P)] += c[i]; } std::cout << join(ans.begin() + 1, ans.end()) << "\n"; return 0; }