11_sliding_window_problems/sliding_window_or_3405.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <iostream>
#include <vector>

// We pre-compute prefix and suffix or for non-overlapping windows of k
// elements, and we compute the sliding window or from those.
// https://codeforces.com/blog/entry/142846

int main() {
	size_t n, k;
	long long a, b, c, sol{0};
	std::cin >> n >> k;
	std::vector<long long> v(n), pre(n), suf(n);
	std::cin >> v[0] >> a >> b >> c;

	for (size_t i = 1; i < n; i++)
		v[i] = (a*v[i-1] + b) % c;

	for (size_t i = 0; i < n; i++)
		pre[i] = i % k == 0 ? v[i] : v[i] | pre[i-1];

	for (size_t i = n; i > 0; i--)
		suf[i-1] = i == n || (i-1) % k == 0 ? v[i-1] : v[i-1] | suf[i];

	for (long long i = k-1; i < n; i++)
		sol ^= pre[i] | suf[i-(k-1)];

	std::cout << sol << "\n";
}