問題描述

你得到一個長度為 $n$ 的整數陣列

從左到右計算每個長度為 $k$ 的視窗 or 完的結果

然後將這些最小值做 xor 運算（逐一累積後再輸出結果）

練習題

連結：https://cses.fi/problemset/task/3405

完整程式碼

#include <bits/stdc++.h>
using namespace std;

#define ll long long

// 主邏輯：計算所有長度 k 的滑動視窗的 bitwise OR，再取 XOR
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n, k;
    cin >> n >> k;

    ll x, a, b, c;
    cin >> x >> a >> b >> c;

    vector<ll> vec(n);
    vec[0] = x;
    for (ll i = 1; i < n; i++) {
        vec[i] = (vec[i - 1] * a % c + b) % c;
    }

    ll result = 0;
    ll totalBlocks = (n + k - 1) / k;

    vector<ll> suffix(k), prefix(k);

    for (ll seg = 0; seg + 1 < totalBlocks; ++seg) {
        ll base = seg * k;
        ll end = min(n - 1, base + k - 1);

        // Step 1: 預處理目前區塊的 suffix-OR
        suffix[k - 1] = vec[end];
        for (ll i = end - 1; i >= base; --i) suffix[i - base] = vec[i] | suffix[i - base + 1];

        // Step 2: 預處理下一區塊的 prefix-OR
        ll nextBase = (seg + 1) * k;
        ll nextEnd = min(n - 1, nextBase + k - 1);
        prefix[0] = vec[nextBase];
        for (ll i = nextBase + 1; i <= nextEnd; ++i)
            prefix[i - nextBase] = vec[i] | prefix[i - nextBase - 1];

        // Step 3: 處理這個區塊起點的所有合法視窗
        for (ll i = base; i <= end && i <= n - k; ++i) {
            ll nextCount = i - base;
            ll curCount = k - nextCount;

            ll winOR;
            if (nextCount == 0) {
                winOR = suffix[0]; // 完全在目前區塊
            } else {
                winOR = suffix[k - curCount] | prefix[nextCount - 1];
            }

            result ^= winOR;
        }
    }

    // 如果最後一區塊剛好長度 k，處理尾端視窗
    if (n % k == 0) {
        ll base = (totalBlocks - 1) * k;
        ll end = n - 1;

        suffix[k - 1] = vec[end];
        for (ll i = end - 1; i >= base; --i) suffix[i - base] = vec[i] | suffix[i - base + 1];

        result ^= suffix[0];
    }

    cout << result << '\n';
    return 0;
}