P9227 异或积 的题解

· · 题解

题目大意

传送门

思路

为什么感觉大家的题解代码都那么复杂？其实根本不需要啊。

首先，我们可以猜测这就是找规律题，因为我们不可能在 1 秒内跑 10^{18} 的数据。

我们可以发现，除非是 n 和 k 均为偶数，其他都必须进行一次操作。

比如：n=4。

我们把它进行转换：

(a_1,a_2,a_3,a_4)$ $\rightarrow$ $(a_2 ⊕a_3⊕a_4,a_1⊕a_3⊕a_4,a_1⊕a_2⊕a_4,a_1⊕a_2⊕a_3)$ $\rightarrow$ $(a_1,a_2,a_3,a_4)$ $\rightarrow...

可以发现当 n 为偶数时，答案将会在 原来的式子 与 变换一次的式子 之间徘徊。

同样，我们也可以验证 n 是奇数的性质：除第一次外其他都是 变换一次的式子。

只需要特判 n 和 k 均为偶数时即可。

其中进行一次操作有些技巧，具体见代码。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T, n; ll k;
ll a[100007], b[100007];
inline void work() {
    ll sum = 0;
    for(int i = 1; i <= n; i++) sum ^= a[i];
    for(int i = 1; i <= n; i++) b[i] = sum ^ a[i];
}
inline ll read() {
    ll x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
int main() {
    T = read();
    while(T--) {
        n = read(), k = read();
        for(int i = 1; i <= n; i++)
            a[i] = read();
        if(n % 2 == 0 && k % 2 == 0) {
            for(int i = 1; i <= n; i++)
                printf("%lld ", a[i]);
            printf("\n");
            continue;
        }
        work();
        for(int i = 1; i <= n; i++)
            printf("%lld ", b[i]);
        printf("\n");
    }
    return 0;
}