sliding_window_or_3405.cpp (716B)
1 #include <iostream> 2 #include <vector> 3 4 // We pre-compute prefix and suffix or for non-overlapping windows of k 5 // elements, and we compute the sliding window or from those. 6 // https://codeforces.com/blog/entry/142846 7 8 int main() { 9 size_t n, k; 10 long long a, b, c, sol{0}; 11 std::cin >> n >> k; 12 std::vector<long long> v(n), pre(n), suf(n); 13 std::cin >> v[0] >> a >> b >> c; 14 15 for (size_t i = 1; i < n; i++) 16 v[i] = (a*v[i-1] + b) % c; 17 18 for (size_t i = 0; i < n; i++) 19 pre[i] = i % k == 0 ? v[i] : v[i] | pre[i-1]; 20 21 for (size_t i = n; i > 0; i--) 22 suf[i-1] = i == n || (i-1) % k == 0 ? v[i-1] : v[i-1] | suf[i]; 23 24 for (long long i = k-1; i < n; i++) 25 sol ^= pre[i] | suf[i-(k-1)]; 26 27 std::cout << sol << "\n"; 28 }