test/convolution/subset-convolution/yosupo-Bitwise-And-Convolution.test.cpp

• View this file on GitHub
• Last update: 2023-07-31 16:36:45+08:00
• Problem: https://judge.yosupo.jp/problem/bitwise_and_convolution

Depends on

• library/convolution/subset-convolution.hpp
• library/math/inv-gcd.hpp
• library/math/safe-mod.hpp
• library/misc/type-traits.hpp
• library/modint/modint.hpp

Code

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

#include <iostream>

#include "../../../library/modint/modint.hpp"

#include "../../../library/convolution/subset-convolution.hpp"

using namespace std;
using namespace felix;

using mint = modint998244353;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	n = 1 << n;
	vector<mint> a(n);
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
	vector<mint> b(n);
	for(int i = 0; i < n; i++) {
		cin >> b[i];
	}
	vector<mint> c(n), d(n);
	for(int i = 0; i < n; i++) {
		c[i] = a[~i & (n - 1)];
		d[i] = b[~i & (n - 1)];
	}
	auto e = and_convolution(a, b);
	auto f = or_convolution(c, d);
	for(int i = 0; i < n; i++) {
		assert(e[i] == f[~i & (n - 1)]);
		cout << e[i] << " \n"[i == n - 1];
	}
	return 0;
}

#line 1 "test/convolution/subset-convolution/yosupo-Bitwise-And-Convolution.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/bitwise_and_convolution"

#include <iostream>

#line 3 "library/modint/modint.hpp"
#include <vector>

#include <algorithm>

#include <cassert>

#include <type_traits>

#line 3 "library/misc/type-traits.hpp"
#include <numeric>

#line 5 "library/misc/type-traits.hpp"

namespace felix {

namespace internal {

#ifndef _MSC_VER
template<class T> using is_signed_int128 = typename std::conditional<std::is_same<T, __int128_t>::value || std::is_same<T, __int128>::value, std::true_type, std::false_type>::type;
template<class T> using is_unsigned_int128 = typename std::conditional<std::is_same<T, __uint128_t>::value || std::is_same<T, unsigned __int128>::value, std::true_type, std::false_type>::type;
template<class T> using make_unsigned_int128 = typename std::conditional<std::is_same<T, __int128_t>::value, __uint128_t, unsigned __int128>;
template<class T> using is_integral = typename std::conditional<std::is_integral<T>::value || is_signed_int128<T>::value || is_unsigned_int128<T>::value, std::true_type, std::false_type>::type;
template<class T> using is_signed_int = typename std::conditional<(is_integral<T>::value && std::is_signed<T>::value) || is_signed_int128<T>::value, std::true_type, std::false_type>::type;
template<class T> using is_unsigned_int = typename std::conditional<(is_integral<T>::value && std::is_unsigned<T>::value) || is_unsigned_int128<T>::value, std::true_type, std::false_type>::type;
template<class T> using to_unsigned = typename std::conditional<is_signed_int128<T>::value, make_unsigned_int128<T>, typename std::conditional<std::is_signed<T>::value, std::make_unsigned<T>, std::common_type<T>>::type>::type;
#else
template<class T> using is_integral = typename std::is_integral<T>;
template<class T> using is_signed_int = typename std::conditional<is_integral<T>::value && std::is_signed<T>::value, std::true_type, std::false_type>::type;
template<class T> using is_unsigned_int = typename std::conditional<is_integral<T>::value && std::is_unsigned<T>::value, std::true_type, std::false_type>::type;
template<class T> using to_unsigned = typename std::conditional<is_signed_int<T>::value, std::make_unsigned<T>, std::common_type<T>>::type;
#endif

template<class T> using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template<class T> using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
template<class T> using to_unsigned_t = typename to_unsigned<T>::type;

template<class T> struct safely_multipliable {};
template<> struct safely_multipliable<short> { using type = int; };
template<> struct safely_multipliable<unsigned short> { using type = unsigned int; };
template<> struct safely_multipliable<int> { using type = long long; };
template<> struct safely_multipliable<unsigned int> { using type = unsigned long long; };
template<> struct safely_multipliable<long long> { using type = __int128; };
template<> struct safely_multipliable<unsigned long long> { using type = __uint128_t; };

template<class T> using safely_multipliable_t = typename safely_multipliable<T>::type;

}  // namespace internal


}  // namespace felix

#line 2 "library/math/safe-mod.hpp"

namespace felix {

namespace internal {

template<class T>
constexpr T safe_mod(T x, T m) {
	x %= m;
	if(x < 0) {
		x += m;
	}
	return x;
}

} // namespace internal


} // namespace felix
#line 3 "library/math/inv-gcd.hpp"

namespace felix {

namespace internal {

template<class T>
constexpr std::pair<T, T> inv_gcd(T a, T b) {
	a = safe_mod(a, b);
	if(a == 0) {
		return {b, 0};
	}
	T s = b, t = a;
	T m0 = 0, m1 = 1;
	while(t) {
		T u = s / t;
		s -= t * u;
		m0 -= m1 * u;
		auto tmp = s;
		s = t;
		t = tmp;
		tmp = m0;
		m0 = m1;
		m1 = tmp;
	}
	if(m0 < 0) {
		m0 += b / s;
	}
	return {s, m0};
}

} // namespace internal


} // namespace felix

#line 9 "library/modint/modint.hpp"

namespace felix {

template<int id>
struct modint {
public:
	static constexpr int mod() { return (id > 0 ? id : md); }
 	
	static constexpr void set_mod(int m) {
		if(id > 0 || md == m) {
			return;
		}
		md = m;
		fact.resize(1);
		inv_fact.resize(1);
		invs.resize(1);
	}

	static constexpr void prepare(int n) {
		int sz = (int) fact.size();
		if(sz == mod()) {
			return;
		}
		n = 1 << std::__lg(2 * n - 1);
		if(n < sz) {
			return;
		}
		if(n < (sz - 1) * 2) {
			n = std::min((sz - 1) * 2, mod() - 1);
		}
		fact.resize(n + 1);
		inv_fact.resize(n + 1);
		invs.resize(n + 1);
		for(int i = sz; i <= n; i++) {
			fact[i] = fact[i - 1] * i;
		}
		auto eg = internal::inv_gcd(fact.back().val(), mod());
		assert(eg.first == 1);
		inv_fact[n] = eg.second;
		for(int i = n - 1; i >= sz; i--) {
			inv_fact[i] = inv_fact[i + 1] * (i + 1);
		}
		for(int i = n; i >= sz; i--) {
			invs[i] = inv_fact[i] * fact[i - 1];
		}
	}
 
	constexpr modint() : v(0) {} 
	template<class T, internal::is_signed_int_t<T>* = nullptr> constexpr modint(T x) : v(x >= 0 ? x % mod() : x % mod() + mod()) {}
	template<class T, internal::is_unsigned_int_t<T>* = nullptr> constexpr modint(T x) : v(x % mod()) {}
 
	constexpr int val() const { return v; }

	constexpr modint inv() const {
		if(id > 0 && v < std::min(mod() >> 1, 1 << 18)) {
			prepare(v);
			return invs[v];
		} else {
			auto eg = internal::inv_gcd(v, mod());
			assert(eg.first == 1);
			return eg.second;
		}
	}
 
	constexpr modint& operator+=(const modint& rhs) & {
		v += rhs.v;
		if(v >= mod()) {
			v -= mod();
		}
		return *this;
	}
 
	constexpr modint& operator-=(const modint& rhs) & {
		v -= rhs.v;
		if(v < 0) {
			v += mod();
		}
		return *this;
	}

	constexpr modint& operator*=(const modint& rhs) & {
		v = 1LL * v * rhs.v % mod();
		return *this;
	}

	constexpr modint& operator/=(const modint& rhs) & {
		return *this *= rhs.inv();
	}

	friend constexpr modint operator+(modint lhs, modint rhs) { return lhs += rhs; }
	friend constexpr modint operator-(modint lhs, modint rhs) { return lhs -= rhs; }
	friend constexpr modint operator*(modint lhs, modint rhs) { return lhs *= rhs; }
	friend constexpr modint operator/(modint lhs, modint rhs) { return lhs /= rhs; }

	constexpr modint operator+() const { return *this; }
	constexpr modint operator-() const { return modint() - *this; } 
	constexpr bool operator==(const modint& rhs) const { return v == rhs.v; } 
	constexpr bool operator!=(const modint& rhs) const { return v != rhs.v; }

	constexpr modint pow(long long p) const {
		modint a(*this), res(1);
		if(p < 0) {
			a = a.inv();
			p = -p;
		}
		while(p) {
			if(p & 1) {
				res *= a;
			}
			a *= a;
			p >>= 1;
		}
		return res;
	}

	constexpr bool has_sqrt() const {
		if(mod() == 2 || v == 0) {
			return true;
		}
		if(pow((mod() - 1) / 2).val() != 1) {
			return false;
		}
		return true;
	}

	constexpr modint sqrt() const {
		if(mod() == 2 || v < 2) {
			return *this;
		}
		assert(pow((mod() - 1) / 2).val() == 1);
		modint b = 1;
		while(b.pow((mod() - 1) >> 1).val() == 1) {
			b += 1;
		}
		int m = mod() - 1, e = __builtin_ctz(m);
		m >>= e;
		modint x = modint(*this).pow((m - 1) >> 1);
		modint y = modint(*this) * x * x;
		x *= v;
		modint z = b.pow(m);
		while(y.val() != 1) {
			int j = 0;
			modint t = y;
			while(t.val() != 1) {
				t *= t;
				j++;
			}
			z = z.pow(1LL << (e - j - 1));
			x *= z, z *= z, y *= z;
			e = j;
		}
		return x;
	}

	friend std::istream& operator>>(std::istream& in, modint& num) {
		long long x;
		in >> x;
		num = modint<id>(x);
		return in;
	}
	
	friend std::ostream& operator<<(std::ostream& out, const modint& num) {
		return out << num.val();
	}

public:
	static std::vector<modint> fact, inv_fact, invs;
 
private:
	int v;
	static int md;
};

template<int id> int modint<id>::md = 998244353;
template<int id> std::vector<modint<id>> modint<id>::fact = {1};
template<int id> std::vector<modint<id>> modint<id>::inv_fact = {1};
template<int id> std::vector<modint<id>> modint<id>::invs = {0};

using modint998244353 = modint<998244353>;
using modint1000000007 = modint<1000000007>;

namespace internal {

template<class T> struct is_modint : public std::false_type {};
template<int id> struct is_modint<modint<id>> : public std::true_type {};

template<class T, class ENABLE = void> struct is_static_modint : public std::false_type {};
template<int id> struct is_static_modint<modint<id>, std::enable_if_t<(id > 0)>> : public std::true_type {};
template<class T> using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;

template<class T, class ENABLE = void> struct is_dynamic_modint : public std::false_type {};
template<int id> struct is_dynamic_modint<modint<id>, std::enable_if_t<(id <= 0)>> : public std::true_type {};
template<class T> using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;

} // namespace internal


} // namespace felix

#line 6 "library/convolution/subset-convolution.hpp"

namespace felix {

template<class T, class F>
void fwht(std::vector<T>& a, F f) {
	const int n = (int) a.size();
	assert(__builtin_popcount(n) == 1);
	for(int i = 1; i < n; i <<= 1) {
		for(int j = 0; j < n; j += i << 1) {
			for(int k = 0; k < i; k++) {
				f(a[j + k], a[i + j + k]);
			}
		}
	}
}

template<class T>
void or_transform(std::vector<T>& a, bool inv) {
	fwht(a, [&](T& x, T& y) { y += x * (inv ? -1 : +1); });
}

template<class T>
void and_transform(std::vector<T>& a, bool inv) {
	fwht(a, [&](T& x, T& y) { x += y * (inv ? -1 : +1); });
}

template<class T>
void xor_transform(std::vector<T>& a, bool inv) {
	fwht(a, [](T& x, T& y) {
		T z = x + y;
		y = x - y;
		x = z;
	});
	if(inv) {
		if constexpr(internal::is_integral<T>::value) {
			for(auto& x : a) {
				x /= a.size();
			}
		} else {
			T z = T(1) / T(a.size());
			for(auto& x : a) {
				x *= z;
			}
		}
	}
}

template<class T>
std::vector<T> or_convolution(std::vector<T> a, std::vector<T> b) {
	assert(a.size() == b.size());
	or_transform(a, false);
	or_transform(b, false);
	for(int i = 0; i < (int) a.size(); i++) {
		a[i] *= b[i];
	}
	or_transform(a, true);
	return a;
}

template<class T>
std::vector<T> and_convolution(std::vector<T> a, std::vector<T> b) {
	assert(a.size() == b.size());
	and_transform(a, false);
	and_transform(b, false);
	for(int i = 0; i < (int) a.size(); i++) {
		a[i] *= b[i];
	}
	and_transform(a, true);
	return a;
}

template<class T>
std::vector<T> xor_convolution(std::vector<T> a, std::vector<T> b) {
	assert(a.size() == b.size());
	xor_transform(a, false);
	xor_transform(b, false);
	for (int i = 0; i < (int) a.size(); i++) {
		a[i] *= b[i];
	}
	xor_transform(a, true);
	return a;
}

template<class T>
std::vector<T> subset_convolution(const std::vector<T>& f, const std::vector<T>& g) {
	assert(f.size() == g.size());
	const int n = (int) f.size();
	assert(__builtin_popcount(n) == 1);
	const int lg = std::__lg(n);
	std::vector<std::vector<T>> fhat(lg + 1, std::vector<T>(n)), ghat(fhat), h(fhat);
	for(int mask = 0; mask < n; mask++) {
		fhat[__builtin_popcount(mask)][mask] = f[mask];
		ghat[__builtin_popcount(mask)][mask] = g[mask];
	}
	for(int i = 0; i <= lg; ++i) {
		or_transform(fhat[i], false);
		or_transform(ghat[i], false);
	}
	for(int mask = 0; mask < n; mask++) {
		for(int i = 0; i <= lg; ++i) {
			for(int j = 0; j <= i; ++j) {
				h[i][mask] += fhat[j][mask] * ghat[i - j][mask];
			}
		}
	}
	for(int i = 0; i <= lg; ++i) {
		or_transform(h[i], true);
	}
	std::vector<T> result(n);
	for(int mask = 0; mask < n; mask++) {
		result[mask] = h[__builtin_popcount(mask)][mask];
	}
	return result;
}

} // namespace felix
#line 6 "test/convolution/subset-convolution/yosupo-Bitwise-And-Convolution.test.cpp"
using namespace std;
using namespace felix;

using mint = modint998244353;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	n = 1 << n;
	vector<mint> a(n);
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
	vector<mint> b(n);
	for(int i = 0; i < n; i++) {
		cin >> b[i];
	}
	vector<mint> c(n), d(n);
	for(int i = 0; i < n; i++) {
		c[i] = a[~i & (n - 1)];
		d[i] = b[~i & (n - 1)];
	}
	auto e = and_convolution(a, b);
	auto f = or_convolution(c, d);
	for(int i = 0; i < n; i++) {
		assert(e[i] == f[~i & (n - 1)]);
		cout << e[i] << " \n"[i == n - 1];
	}
	return 0;
}

Back to top page