思路:递推思维

假设序列是$a_1,a_2,a_3,a_4$.

1.考虑$f_1$ 到$f_2$ , 多了一个$a_2,a_3,a_4$的后缀异或和，少了一个$a_4$ 这个后缀的异或和

2.$f_2$到$f_3$ , 多了一个$a_3,a_4$的后缀异或和,少了一个$a_3,a_4$ 这个后缀的异或和

3.总结规律:从$f_i$ 到 $f_{i + 1}$ 每次会因为子数组增长而多一个后缀(从每个子数组提取最后一个)，但是同时也会丢失最后一个区间异或和(比如$f_2$的时候有$a_3,a_4$,但是到$f_3$时，这个子数组由于无法往后拓展而失去)

4.实现:我们要往答案里增加/抵消一个后缀，我们可以直接进行异或操作。而后缀异或和的得到，类似前缀和的思路，可以用前缀异或和来差分得到。

代码

java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 读取序列长度
        int[] a = new int[n + 1]; // 存储输入的序列
        int[] s = new int[n + 1]; // 存储前缀异或和

        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextInt(); // 读取每个数
            s[i] = s[i - 1] ^ a[i]; // 计算前缀异或和
        }

        int ans = 0; // 初始化答案
        for (int i = 1; i <= n; i++) {
            ans ^= get(s, i, n) ^ get(s, n - i + 2, n); // 更新答案
            System.out.print(ans + " "); // 输出当前答案
        }
        scanner.close(); // 关闭输入流
    }

    private static int get(int[] s, int l, int r) {
        return s[r] ^ s[l - 1]; // 计算区间[l, r]的异或和
    }
}

python

def get(prefix_xor, l, r):
    return prefix_xor[r] ^ prefix_xor[l - 1]  # 计算区间[l, r]的异或和

def main():
    n = int(input())  # 读取序列长度
    a = list(map(int, input().split()))  # 读取序列
    prefix_xor = [0] * (n + 1)  # 初始化前缀异或和数组

    for i in range(1, n + 1):
        prefix_xor[i] = prefix_xor[i - 1] ^ a[i - 1]  # 计算前缀异或和

    ans = 0  # 初始化答案
    for i in range(1, n + 1):
        ans ^= get(prefix_xor, i, n) ^ get(prefix_xor, n - i + 2, n)  # 更新答案
        print(ans, end=' ')  # 输出当前答案

if __name__ == "__main__":
    main()  # 执行主函数

cpp

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10; // 定义最大数组大小
int a[N], s[N]; // a用于存储输入序列，s用于存储前缀异或和

int get(int l, int r) {
    return s[r] ^ s[l-1]; // 计算区间[l, r]的异或和
}

int main() {
    int n;
    cin >> n; // 读取序列长度
    for(int i = 1 ; i <= n ; i ++) {
        cin >> a[i]; // 读取每个数
        s[i] = s[i-1] ^ a[i]; // 计算前缀异或和
    }
    int ans = 0; // 初始化答案
    for(int i = 1 ; i <= n ; i ++) {
        ans ^= get(i, n) ^ get(n-i+2, n); // 更新答案
        cout << ans << " "; // 输出当前答案
    }
}

OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。

题目内容

$f_k$表示长度为$k$的全部子数组元素按位异或的结果。例如:对于原数组{$1,2,3,4$}，长度为$3$ 的子数组有{$1,2,3$}和{$2,3,4$}，因此$f_3=(1⊕2⊕3)⊕(2⊕3⊕4)$。同理$f_2=(1⊕2)⊕(2⊕3)⊕(3⊕4)$。

现在，对于给定的一个长度为$n$的数组{$a_1,a_2,...,a_n$}。输出$f_1$~ $f_n$。

$a⊕b$表示$a$按位异或$b$(按位异或运算符"⊕”是双目运算符。其功能是参与运算的两数各对应的二进位相异或。只要对应的两个二进位不相同时，结果位就为$1$)。

输入描述

第一行输入一个整数$n(1≤n≤2×10^5)$代表数组中的元素数量。

第二行输入$n$个整数$a_1,a_2,...,a_n(0≤a_i<2^{30})$代表数组元素,

输出描述

在一行上输出$n$个整数，分别表示$f_1$~$f_n$。

示例1

输入

3
1 1 1

输出

1 0 1