ac

给定一个整型数组arr，其中可能有正有负有零。你可以随意把整个数组切成若干个不相容的子数组，求异或和为0的子数组最多可能有多少个？整数异或和定义：把数组中所有的数异或起来得到的值。

10
3 2 1 9 0 7 0 2 1 3

最优划分：{3,2,1},{9},{0},{7},{0},{2,1,3} 其中{3,2,1},{0},{0},{2,1,3}的异或和为0

import java.util.*;


public class Main {

    public static Scanner sc = new Scanner(System.in);

    static int M = (int)Math.pow(10, 9) + 7;

    public static void main(String[] args) {
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
        }
        System.out.println(process(arr));
    }

    static int process(int[] arr){
        int len = arr.length;
        // key存储出现过的异或和,value表示下标
        Map<Integer, Integer> mp = new HashMap<>();
        mp.put(0, -1);

        int[] dp = new int[len];
        if(arr[0] == 0){
            dp[0] = 1;
        }else {
            dp[0] = 0;
        }
        mp.put(arr[0], 0);

        int eor = arr[0]; // 累计的eor，划分要是连续的
        for(int i=1;i<len;i++){
            eor = arr[i] ^ eor; // 与自己异或是0，与0异或是自己
            if(mp.containsKey(eor)){
                int k = mp.get(eor);
                if(k != -1){ // 0到k一个划分，k+1到i一个划分
                    dp[i] = 1 + dp[k];
                }else {
                    dp[i] = 1;
                }
            }
            dp[i] = Math.max(dp[i-1], dp[i]);
            mp.put(eor, i);
        }
        return dp[len-1];
    }

}
/*
10
3 2 1 9 0 7 0 2 1 3

4
 */

1、交换律

2、结合律（即(a^b)^c == a^(b^c)）

3、对于任何数x，都有x^x=0，x^0=x

4、自反性 A XOR B XOR B = A xor 0 = A

  0101   0101    1010
^ 1010   1111    1111
  1111   1010    0101