This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub Series-205/library
#define PROBLEM "https://judge.yosupo.jp/problem/bitwise_xor_convolution" #include <bits/stdc++.h> using namespace std; #include "../convolution/xor_convolution.cpp" template <int M> class ModInt { int x; public: constexpr ModInt() : x(0) {} constexpr ModInt(int64_t y) : x(y >= 0 ? y % M : (M - (-y) % M) % M) {} constexpr ModInt &operator+=(const ModInt p) { if((x += p.x) >= M) x -= M; return *this; } constexpr ModInt &operator-=(const ModInt p) { if((x += M - p.x) >= M) x -= M; return *this; } constexpr ModInt &operator*=(const ModInt p) { x = (int)(1LL * x * p.x % M); return *this; } constexpr ModInt &operator/=(const ModInt p) { *this *= p.inverse(); return *this; } constexpr ModInt operator-() const { return ModInt(-x); } constexpr ModInt operator+(const ModInt p) const { return ModInt(*this) += p; } constexpr ModInt operator-(const ModInt p) const { return ModInt(*this) -= p; } constexpr ModInt operator*(const ModInt p) const { return ModInt(*this) *= p; } constexpr ModInt operator/(const ModInt p) const { return ModInt(*this) /= p; } constexpr bool operator==(const ModInt p) const { return x == p.x; } constexpr bool operator!=(const ModInt p) const { return x != p.x; } constexpr ModInt inverse() const { int a = x, b = M, u = 1, v = 0, t = 0; while(b > 0) { t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); } return ModInt(u); } constexpr ModInt pow(int64_t k) const { ModInt ret(1), mul(x); while(k > 0) { if(k & 1) ret *= mul; mul *= mul; k >>= 1; } return ret; } constexpr friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x; } constexpr friend istream &operator>>(istream &is, ModInt &a) { int64_t t = 0; is >> t; a = ModInt(t); return (is); } }; using mint = ModInt<998244353>; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int n; cin >> n; vector<mint> a(1 << n), b(1 << n); for(int i = 0; i < 1 << n; i++) cin >> a[i]; for(int i = 0; i < 1 << n; i++) cin >> b[i]; auto ans = xorConvolution::convolution(a, b); for(int i = 0; i < 1 << n; i++) cout << ans[i] << " \n"[(i + 1) == 1 << n]; }
#line 1 "test/yosupo-bitwise_xor_convolution.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/bitwise_xor_convolution" #include <bits/stdc++.h> using namespace std; #line 3 "convolution/xor_convolution.cpp" using namespace std; class xorConvolution { template <typename T> static void FWT(vector<T>& f) { int n = f.size(); for(int i = 1; i < n; i <<= 1) for(int j = 0; j < n; j++) if((j & i) == 0) { T x = f[j], y = f[j | i]; f[j] = x + y, f[j | i] = x - y; } } public: template <typename T> static vector<T> convolution(vector<T> f, vector<T> g) { int sz = 1, n = max(f.size(), g.size()); while(sz < n) sz <<= 1; f.resize(sz); g.resize(sz); FWT(f); FWT(g); for(int i = 0; i < sz; i++) f[i] *= g[i]; FWT(f); for(int i = 0; i < sz; i++) f[i] /= sz; return f; } }; #line 7 "test/yosupo-bitwise_xor_convolution.test.cpp" template <int M> class ModInt { int x; public: constexpr ModInt() : x(0) {} constexpr ModInt(int64_t y) : x(y >= 0 ? y % M : (M - (-y) % M) % M) {} constexpr ModInt &operator+=(const ModInt p) { if((x += p.x) >= M) x -= M; return *this; } constexpr ModInt &operator-=(const ModInt p) { if((x += M - p.x) >= M) x -= M; return *this; } constexpr ModInt &operator*=(const ModInt p) { x = (int)(1LL * x * p.x % M); return *this; } constexpr ModInt &operator/=(const ModInt p) { *this *= p.inverse(); return *this; } constexpr ModInt operator-() const { return ModInt(-x); } constexpr ModInt operator+(const ModInt p) const { return ModInt(*this) += p; } constexpr ModInt operator-(const ModInt p) const { return ModInt(*this) -= p; } constexpr ModInt operator*(const ModInt p) const { return ModInt(*this) *= p; } constexpr ModInt operator/(const ModInt p) const { return ModInt(*this) /= p; } constexpr bool operator==(const ModInt p) const { return x == p.x; } constexpr bool operator!=(const ModInt p) const { return x != p.x; } constexpr ModInt inverse() const { int a = x, b = M, u = 1, v = 0, t = 0; while(b > 0) { t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); } return ModInt(u); } constexpr ModInt pow(int64_t k) const { ModInt ret(1), mul(x); while(k > 0) { if(k & 1) ret *= mul; mul *= mul; k >>= 1; } return ret; } constexpr friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x; } constexpr friend istream &operator>>(istream &is, ModInt &a) { int64_t t = 0; is >> t; a = ModInt(t); return (is); } }; using mint = ModInt<998244353>; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int n; cin >> n; vector<mint> a(1 << n), b(1 << n); for(int i = 0; i < 1 << n; i++) cin >> a[i]; for(int i = 0; i < 1 << n; i++) cin >> b[i]; auto ans = xorConvolution::convolution(a, b); for(int i = 0; i < 1 << n; i++) cout << ans[i] << " \n"[(i + 1) == 1 << n]; }