提出 #39248995

---

ソースコード 拡げる

#include <bits/stdc++.h>
typedef long long ll;
const int mod = 998244353;
void amod(int &x, int y) {
	x = x + y >= mod ? x + y - mod : x + y;
}
void dmod(int &x, int y) {
	x = x - y < 0 ? x - y + mod : x - y;
}
int inc(int x, int y) {
	return x + y >= mod ? x + y - mod : x + y;
}
int dec(int x, int y) {
	return x - y < 0 ? x - y + mod : x - y;
}
int ksm(int x, int y = mod - 2) {
	int res = 1;
	for(; y > 0; y >>= 1, x = 1ll * x * x % mod) {
		if(y & 1) {
			res = 1ll * res * x % mod;
		}
	}
	return res;
}
namespace Cipolla {
	int i2;
	struct C {
		int a, b;
		C(int a = 0, int b = 0) : a(a), b(b) {}
		friend C operator * (C x, C y) {
			return C(((ll)x.a * y.a % mod + (ll)x.b * y.b % mod * i2 % mod) % mod, ((ll)x.a * y.b % mod + (ll)y.a * x.b % mod) % mod);
		}
	};
	C ksm(C x, int y) {
		C res = C(1, 0);
		while(y) {
			if(y & 1) {
				res = res * x;
			}
			x = x * x;
			y >>= 1;
		}
		return res;
	}
	bool check(int x) {
		x = (x % mod + mod) % mod;
		return ::ksm(x, (mod - 1) / 2) == 1;
	}
	int cipolla(int a) {
		if(!check(a)) {
			return -1;
		}
		int x;
		std::mt19937 rnd(rand());
		std::uniform_int_distribution<int> dis(1, mod - 1);
		while(1) {
			x = (dis(rnd) % mod + mod) % mod;
			i2 = ((ll)x * x % mod - a + mod) % mod;
			if(x && !check(i2)) {
				break;
			}
		}
		x = ksm(C(x, 1), (mod + 1) / 2).a;
		x = std::min(x, mod - x);
		return x;
	}
}
namespace Poly {
	const int G[2] = {332748118, 3};
	std::vector<int> rev;
	int null;
	int init(int n) {
		n = 1 << (int)ceil(log2(n));
		rev.resize(n);
		for(int i = 0; i < n; i++) {
			rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (n >> 1) : 0);
		}
		return n;
	}
	struct poly {
		std::vector<int> a;
		poly(const int &n = 0) {
			a.clear();
			a.resize(n);
		}
		void resize(const int &n) {
			a.resize(n);
		}
		int size() const {
			return a.size();
		}
		void reverse() {
			std::reverse(a.begin(), a.end());
		}
		int operator [] (const int &i) const {
			return (i >= 0 && i < size()) ? a[i] : 0;
		}
		int &operator [] (const int &i) {
			return (i >= 0 && i < size()) ? a[i] : (null = 0);
		}
		poly modx(const int &k) {
            poly res = poly(std::min(size(), k));
            for(int i = 0; i < res.size(); i++) {
            	res[i] = a[i];
			}
			return res;
        }
        poly mulx(const int &k) {
            poly res = poly(size() + k);
            for(int i = 0; i < size(); i++) {
            	res[i + k] = a[i];
			}
            return res;
        }
        poly powx(const int &k) {
        	poly res = poly((size() - 1) * k + 1);
        	for(int i = 0; i < size(); i++) {
        		res[i * k] = a[i];
			}
			return res;
		}
		void ntt(int o) {
			for(int i = 0; i < size(); i++) {
				if(i < rev[i]) {
					std::swap(a[i], a[rev[i]]);
				}
			}
			for(int i = 2; i <= size(); i <<= 1) {
				int wn = ksm(G[o], (mod - 1) / i);
				for(int j = 0; j < size(); j += i) {
					int w = 1;
					for(int k = 0; k < (i >> 1); k++) {
						int x = a[j + k], y = 1ll * w * a[j + k + (i >> 1)] % mod;
						a[j + k] = (x + y) % mod;
						a[j + k + (i >> 1)] = (x - y + mod) % mod;
						w = 1ll * w * wn % mod;
					}
				}
			}
			if(!o) {
				int d = ksm(size());
				for(int i = 0; i < size(); i++) {
					a[i] = 1ll * a[i] * d % mod;
				}
			}
		}
	};
	poly xk(const int &k) {
		poly res = poly(k + 1);
		res[k] = 1;
		return res;
	}
	poly operator + (const poly &x, const poly &y) {
		poly res = poly(std::max(x.size(), y.size()));
		for(int i = 0; i < res.size(); i++) {
			res[i] = inc(x[i], y[i]);
		}
		return res;
	}
	poly operator + (poly f, int x) {
		f[0] = (f[0] + x) % mod;
		return f;
	}
	poly operator + (int x, poly f) {
		f[0] = (f[0] + x) % mod;
		return f;
	}
	poly operator - (poly f, int x) {
        f[0] = dec(f[0], x);
		return f;
	}
	poly operator - (int x, poly f) {
		f[0] = dec(x, f[0]);
		for(int i = 1; i < f.size(); i++) {
			f[i] = dec(0, f[i]);
		}
		return f;
	}
	poly operator - (const poly &x, const poly &y) {
		poly res = poly(std::max(x.size(), y.size()));
		for(int i = 0; i < res.size(); i++) {
			res[i] = dec(x[i], y[i]);
		}
		return res;
	}
	poly operator * (poly f, int x) {
		for(int i = 0; i < f.size(); i++) {
			f[i] = 1ll * f[i] * x % mod;
		}
		return f;
	}
	poly operator * (int x, poly f) {
		for(int i = 0; i < f.size(); i++) {
			f[i] = 1ll * f[i] * x % mod;
		}
		return f;
	}
	poly operator * (poly f, poly g) {
		int m = f.size() + g.size() - 1, n = init(m);
		poly res = poly(n);
		f.resize(n), g.resize(n);
		f.ntt(1), g.ntt(1);
		for(int i = 0; i < n; i++) {
			res[i] = 1ll * f[i] * g[i] % mod;
		}
		res.ntt(0);
		res.resize(m);
		return res;
	}
	poly inv(poly f, int n) {
		poly res = poly(1);
		res[0] = ksm(f[0]);
		for(int i = 1; i < n; ) {
			i <<= 1;
			res = (res * (2 * xk(0) - (res * f.modx(i)).modx(i))).modx(i);
		}
		return res.modx(n);
	}
	poly dao(poly f) {
		for(int i = 1; i < f.size(); i++) {
			f[i - 1] = 1ll * f[i] * i % mod;
		}
		f.resize(f.size() - 1);
		return f;
	}
	poly jifen(poly f) {
		f.resize(f.size() + 1);
		for(int i = f.size() - 2; i >= 0; i--) {
			f[i + 1] = 1ll * f[i] * ksm(i + 1) % mod;
		}
		f[0] = 0;
		return f;
	}
	poly ln(poly f, int n) {
		return jifen(dao(f) * inv(f, n)).modx(n);
	}
	poly exp(poly f, int n) {
		poly res = poly(1);
		res[0] = 1;
		for(int i = 1; i < n; ) {
			i <<= 1;
			res = (res * (xk(0) - ln(res, i) + f.modx(i))).modx(i);
		}
		return res.modx(n);
	}
	poly sqrt(poly f, int n) {
		poly res = poly(1);
		res[0] = Cipolla::cipolla(f[0]);
		for(int i = 1; i < n; ) {
			i <<= 1;
			res = ((res * res + f.modx(i)) * inv(res * 2, i)).modx(i);
		}
		return res.modx(n);
	}
	poly pow(poly f, int y, int n) {
		int k = -1;
		f.resize(n);
		for(int i = 0; i < f.size(); i++) {
			if(f[i]) {
				k = i;
				break;
			}
		}
		if(k == -1 || 1ll * k * y >= n) {
			return poly(n);
		}
		poly g(n);
		int d = ksm(f[k], mod - 2);
		for(int i = k; i < n; i++) {
			g[i - k] = 1ll * f[i] * d % mod;
		}
		g = exp(ln(g, n) * y, n);
		g = g * xk(k * y) * ksm(f[k], y);
		return g.modx(n);
	}
	poly operator / (poly f, poly g) {
		if(f.size() < g.size()) {
			return poly(1);
		}
		int n = f.size() - 1, m = g.size() - 1;
		f.reverse(), g.reverse();
		f = (f * inv(g, n - m + 1)).modx(n - m + 1);
		f.reverse();
		return f;
	}
	poly operator % (poly f, poly g) {
		int m = g.size() - 1;
		f = f - f / g * g;
		return f.modx(m);
	}
}
namespace Binom {
	std::vector<int> fac, ifac;
	void init(int n) {
		fac.resize(n + 1), ifac.resize(n + 1);
		for(int i = (fac[0] = 1); i <= n; i++) {
			fac[i] = 1ll * fac[i - 1] * i % mod;
		}
		ifac[n] = ksm(fac[n]);
		for(int i = n - 1; i >= 0; i--) {
			ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
		}
	}
	int binom(int x, int y) {
		if(x < y || x < 0 || y < 0) {
			return 0;
		}
		return 1ll * fac[x] * ifac[y] % mod * ifac[x - y] % mod;
	}
}
namespace Stirling {
	using Poly::poly;
	using Poly::xk;
	using Binom::fac;
	using Binom::ifac;
	poly stirling1_row(int n) {
		auto jump = [&](poly f, int n) {
			poly a(n + 1), b(n + 1);
			for(int i = 0; i <= n; i++) {
				a[i] = 1ll * f[n - i] * fac[n - i] % mod;
				b[i] = 1ll * ksm(n, i) * ifac[i] % mod;
			}
			a = a * b;
			for(int i = 0; i <= n; i++) {
				b[i] = 1ll * a[n - i] * ifac[i] % mod;
			}
			f = f * b;
			return f;
		};
		poly f = xk(1);
		int now = 1;
		for(int i = log2(n) - 1; i >= 0; i--) {
			f = jump(f, now);
			now <<= 1;
			if((n >> i) & 1) {
				f = f * (xk(1) + xk(0) * now);
				now++;
			}
		}
		return f;
	}
	poly stirling1_line(int n, int k) {
		poly f(n + 1);
		for(int i = 1; i <= n; i++) {
			f[i - 1] = 1ll * ifac[i] * fac[i - 1] % mod;
		}
		f = (exp(ln(f, n + 1) * k, n + 1)).mulx(k);
		for(int i = 0; i <= n; i++) {
			f[i] = 1ll * f[i] * fac[i] % mod * ifac[k] % mod;
		}
		f.resize(n + 1);
		return f;
	}
	poly stirling2_row(int n) {
		poly f(n + 1), g(n + 1);
		for(int i = 0; i <= n; i++) {
			f[i] = 1ll * ksm(i, n) * ifac[i] % mod;
			g[i] = (i & 1) ? (mod - ifac[i]) : ifac[i];
		}
		f = f * g;
		f.resize(n + 1);
		return f;
	}
	poly stirling2_line(int n, int k){
		poly f(n + 1);
		for(int i = 1; i <= n; i++) {
			f[i] = ifac[i];
		}
		f = pow(f, k, n + 1);
		for(int i = 1; i <= n; i++) {
			f[i] = 1ll * f[i] * fac[i] % mod * ifac[k] % mod;
		}
		return f;
	}
}
using namespace std;
using Poly::poly;
const int maxn = 5e5 + 5;
int n, a[maxn], b[maxn];
ll ans[maxn];

int main() {
#ifdef DEBUG
	freopen("1.in", "r", stdin);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for(int i = 0; i < n; i++) {
		cin >> b[i];
	}
	for(int i = 0; i < 5; i++) {
		poly f(n), g(n * 2);
		for(int j = 0; j < n; j++) {
			f[j] = (a[n - j - 1] >> i & 1) == 0;
			g[j] = g[j + n] = (b[j] >> i & 1) == 0;
		}
		f = f * g;
		for(int j = 0; j < n; j++) {
			ans[j] += (1ll << i) * (n - f[j + n]);
		}
	}
	cout << *max_element(ans, ans + n) << '\n';
	return 0;
}

提出情報

ジャッジ結果