verify/yosupo/yosupo-bitwise_xor_convolution.test.cpp

View this file on GitHub
Last update: 2022-07-21 16:12:33-04:00
Problem: https://judge.yosupo.jp/problem/bitwise_xor_convolution

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/bitwise_xor_convolution"

#include <bits/stdc++.h>
#include <vector>
#include "../../library/set-function/walsh-hadamard-transform.hpp"
#include "../../library/modular-arithmetic/mod-int2.hpp"

using mi = Mint<998244353, 5>;

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	vector<mi> a(1 << n);
	vector<mi> 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];
	}
	walsh_hadamard_transformation(a);
	walsh_hadamard_transformation(b);
	vector<mi> c(1 << n);
	for (int i = 0; i < 1 << n; ++i) {
		c[i] = a[i] * b[i];
	}
	walsh_hadamard_transformation(c, true);
	for (int i = 0; i < 1 << n; ++i) {
		cout << c[i] << ' ';
	}
	cout << '\n';
	return 0;
}

#define PROBLEM "https://judge.yosupo.jp/problem/bitwise_xor_convolution"

#include <bits/stdc++.h>

template <class T> 
void walsh_hadamard_transformation(std::vector<T>& f, bool inverse = false) {
	int n = (int)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;
			}
		}
	}
	if (inverse) {
		if constexpr(std::is_integral<T>::value) {
			for (auto& x : f) x /= n;
		} else {
			T divide = T(1) / T(f.size());
			for (auto& x : f) x *= divide;
		}
	}
}

// 5 is a root of both mods

template <int MOD, int RT> struct Mint {
	static const int mod = MOD;
	static constexpr Mint rt() { return RT; } // primitive root for FFT

	static constexpr int md() { return MOD; } // primitive root for FFT

	int v; 
	explicit operator int() const { return v; } // explicit -> don't silently convert to int

	explicit operator bool() const { return v != 0; }
	Mint() { v = 0; }
	Mint(long long _v) { v = int((-MOD <= _v && _v < MOD) ? _v : _v % MOD); if (v < 0) v += MOD; }
	friend bool operator==(const Mint& a, const Mint& b) { return a.v == b.v; }
	friend bool operator!=(const Mint& a, const Mint& b) { return !(a == b); }
	friend bool operator<(const Mint& a, const Mint& b) { return a.v < b.v; }
	friend bool operator>(const Mint& a, const Mint& b) { return a.v > b.v; }
	friend bool operator<=(const Mint& a, const Mint& b) { return a.v <= b.v; }
	friend bool operator>=(const Mint& a, const Mint& b) { return a.v >= b.v; }
	friend std::istream& operator >> (std::istream& in, Mint& a) { 
		long long x; std::cin >> x; a = Mint(x); return in; }
	friend std::ostream& operator << (std::ostream& os, const Mint& a) { return os << a.v; }
	Mint& operator+=(const Mint& m) { 
		if ((v += m.v) >= MOD) v -= MOD; 
		return *this; }
	Mint& operator-=(const Mint& m) { 
		if ((v -= m.v) < 0) v += MOD; 
		return *this; }
	Mint& operator*=(const Mint& m) { 
		v = (long long)v * m.v % MOD; return *this; }
	Mint& operator/=(const Mint& m) { return (*this) *= inv(m); }
	friend Mint pow(Mint a, long long p) {
		Mint ans = 1; assert(p >= 0);
		for (; p; p /= 2, a *= a) if (p & 1) ans *= a;
		return ans; 
	}
	friend Mint inv(const Mint& a) { assert(a.v != 0); return pow(a, MOD - 2); }
	Mint operator-() const { return Mint(-v); }
	Mint& operator++() { return *this += 1; }
	Mint& operator--() { return *this -= 1; }
	friend Mint operator+(Mint a, const Mint& b) { return a += b; }
	friend Mint operator-(Mint a, const Mint& b) { return a -= b; }
	friend Mint operator*(Mint a, const Mint& b) { return a *= b; }
	friend Mint operator/(Mint a, const Mint& b) { return a /= b; }
};

using mi = Mint<998244353, 5>;

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	vector<mi> a(1 << n);
	vector<mi> 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];
	}
	walsh_hadamard_transformation(a);
	walsh_hadamard_transformation(b);
	vector<mi> c(1 << n);
	for (int i = 0; i < 1 << n; ++i) {
		c[i] = a[i] * b[i];
	}
	walsh_hadamard_transformation(c, true);
	for (int i = 0; i < 1 << n; ++i) {
		cout << c[i] << ' ';
	}
	cout << '\n';
	return 0;
}