This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub Harui-i/library
#define PROBLEM "https://judge.yosupo.jp/problem/lcm_convolution" #include "template/template.hpp" #include "math/modint.hpp" #include "convolution/divisor-zeta-moebius-transform.hpp" using mint = modint998244353; mint op(mint a, mint b) { return a + b; } mint invop(mint a, mint b) { return a - b; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N; cin >> N; vector<mint>a(N+1); for(int i=0; i<N; i++) cin >> a[i+1]; vector<mint>b(N+1); for(int i=0; i<N; i++) cin >> b[i+1]; vector<mint> za = divisor::zeta_transform_naive<mint,op>(a); vector<mint> zb = divisor::zeta_transform_naive<mint,op>(b); vector<mint> zc(N+1); for(int i=0; i<N+1; i++) zc[i] = za[i] * zb[i]; vector<mint> c = divisor::moebius_transform_naive<mint,invop>(zc); for(int i=1; i<=N; i++) cout << c[i].val() << " \n"[i==N]; }
#line 1 "test/verify/convolution/yosupo-lcm-convolution.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/lcm_convolution" #line 1 "template/template.hpp" #include <iostream> #include <cassert> using namespace std; using ll = long long; template<class T> inline bool chmax(T& a, const T& b) {if (a<b) {a=b; return true;} return false;} template<class T> inline bool chmin(T& a, const T& b) {if (b<a) {a=b; return true;} return false;} const int INTINF = 1000001000; const int INTMAX = 2147483647; const ll LLMAX = 9223372036854775807; const ll LLINF = 1000000000000000000; #line 1 "math/modint.hpp" #line 1 "math/external_gcd.hpp" #include <tuple> // g,x,y template<typename T> constexpr std::tuple<T, T, T> extendedGCD(T a, T b) { T x0 = 1, y0 = 0, x1 = 0, y1 = 1; while (b != 0) { T q = a / b; T r = a % b; a = b; b = r; T xTemp = x0 - q * x1; x0 = x1; x1 = xTemp; T yTemp = y0 - q * y1; y0 = y1; y1 = yTemp; } return {a, x0, y0}; } #line 5 "math/modint.hpp" template<int MOD> struct static_modint { int value; constexpr explicit static_modint() : value(0) {} constexpr static_modint(long long v) { value = int(((v % MOD) + MOD) % MOD); } constexpr static_modint& operator+=(const static_modint& other) { if ((value += other.value) >= MOD) value -= MOD; return *this; } constexpr static_modint& operator-=(const static_modint& other) { if ((value -= other.value) < 0) value += MOD; return *this; } constexpr static_modint& operator*=(const static_modint& other) { value = int((long long)value * other.value % MOD); return *this; } constexpr static_modint operator+(const static_modint& other) const { return static_modint(*this) += other; } constexpr static_modint operator-(const static_modint& other) const { return static_modint(*this) -= other; } constexpr static_modint operator*(const static_modint& other) const { return static_modint(*this) *= other; } constexpr static_modint pow(long long exp) const { static_modint base = *this, res = static_modint(1); while (exp > 0) { if (exp & 1) res *= base; base *= base; exp >>= 1; } return res; } constexpr static_modint inv() const { //return pow(MOD - 2); int g,x,y; tie(g,x,y) = extendedGCD(value, MOD); assert(g==1); if (x < 0) { x += MOD; } //cerr << g << " " << x << " " << y << " " << value << endl; //assert((((long)x*value)%MOD + MOD)%MOD == 1); return x; } constexpr static_modint& operator/=(const static_modint& other) { return *this *= other.inv(); } constexpr static_modint operator/(const static_modint& other) const { return static_modint(*this) /= other; } constexpr bool operator!=(const static_modint& other) const { return val() != other.val(); } constexpr bool operator==(const static_modint& other) const { return val() == other.val(); } int val() const { return this->value; } friend std::ostream& operator<<(std::ostream& os, const static_modint& mi) { return os << mi.value; } friend std::istream& operator>>(std::istream& is, static_modint& mi) { long long x; is >> x; mi = static_modint(x); return is; } }; template <int mod> using modint = static_modint<mod>; using modint998244353 = modint<998244353>; using modint1000000007 = modint<1000000007>; #line 1 "convolution/divisor-zeta-moebius-transform.hpp" #include <vector> #include <map> namespace divisor { // 約数についてのゼータ変換。 g_n = \Sigma_{m|n} f_m なる g を求める。 template <typename T, T(*op)(T, T) > std::vector<T> zeta_transform_naive(const std::vector<T>& f) { int N = f.size() - 1; std::vector<T> g = f; for (int i = 1; i <= N; i++) { for (int j = 2 * i; j <= N; j += i) { g[j] = op(g[j], f[i]); } } return g; } // 約数についてのメビウス変換。 f_n = \Sigma_{m|n} g_m なる g を求める。 template <typename T, T(*invop)(T, T)> std::vector<T> moebius_transform_naive(const std::vector<T>& f) { int N = f.size() - 1; std::vector<T> g = f; for (int i = 1; i <= N; i++) { for (int j = i * 2; j <= N; j += i) { g[j] = invop(g[j], g[i]); } } return g; } template <typename I, typename T, T(*op)(T, T)> std::map<I, T> zeta_transform(const std::map<I, T>& mp) { std::map<I, T> ret = mp; for (auto p2itr = mp.rbegin(); p2itr != mp.rend(); p2itr++) { for (auto p1itr = next(p2itr); p1itr != mp.rend(); p1itr++) { if ((*p2itr).first % (*p1itr).first == 0) { ret[(*p2itr).first] = op(ret[(*p2itr).first], ret[(*p1itr).first]); } } } return ret; } template <typename I, typename T, T(*op)(T, T)> std::map<I, T> moebius_transform(const std::map<I, T>& mp) { std::map<I, T> ret = mp; for (auto p1itr = ret.begin(); p1itr != ret.end(); p1itr++) { for (auto p2itr = next(p1itr); p2itr != ret.end(); p2itr++) { if ((*p2itr).first % (*p1itr).first == 0) { ret[(*p2itr).first] = invop(ret[(*p2itr).first], ret[(*p1itr).first]); } } } return ret; } } // namespace divisor #line 6 "test/verify/convolution/yosupo-lcm-convolution.test.cpp" using mint = modint998244353; mint op(mint a, mint b) { return a + b; } mint invop(mint a, mint b) { return a - b; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N; cin >> N; vector<mint>a(N+1); for(int i=0; i<N; i++) cin >> a[i+1]; vector<mint>b(N+1); for(int i=0; i<N; i++) cin >> b[i+1]; vector<mint> za = divisor::zeta_transform_naive<mint,op>(a); vector<mint> zb = divisor::zeta_transform_naive<mint,op>(b); vector<mint> zc(N+1); for(int i=0; i<N+1; i++) zc[i] = za[i] * zb[i]; vector<mint> c = divisor::moebius_transform_naive<mint,invop>(zc); for(int i=1; i<=N; i++) cout << c[i].val() << " \n"[i==N]; }