public class _1442 {
    //O(N^3)
    static class Solution1 {
        public int countTriplets(int[] arr) {
            //a ^ b = c; a ^ c = b
            //dp[i+1] = arr[0] ^ arr[1]...arr[i];
            int[] dp = new int[arr.length+1];
            for(int i = 0;i < arr.length;i++){
                dp[i+1] = dp[i] ^ arr[i];
            }
            int res = 0;
            for(int i = 0;i < arr.length-1;i++){
                for(int j = i+1;j < arr.length;j++){
                    for(int k = j;k < arr.length;k++){
                        if((dp[j] ^ dp[i]) == (dp[k+1] ^ dp[j])) res ++;
                    }
                }
            }
            return res;
        }
    }
    //O(N^2)
    static class Solution2 {
        public int countTriplets(int[] arr) {
            // a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]
            // b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]
            // a  ^ b == 0; ，那么可以将 a ^ b任何一段移动到等式右侧，会出现 j-i个等式成立
            //discuss中的思路
            int[] dp = new int[arr.length+1];
            for(int i = 0;i < arr.length;i++){
                dp[i+1] = dp[i] ^ arr[i];
            }
            int res = 0;
            for(int i = 0;i < arr.length;i++){
                for(int j = i+1;j < arr.length;j++){
                    if((dp[j+1] ^ dp[i] )== 0){
                        res += j -i;
                    }
                }
            }
            return res;
        }
    }
}