O(N)解好強==
原來大家都會prefix這招喔
剛剛有想到如果一大坨0裡面
可以拆成小0a小0b的話
組法可以直接算出來
可是不知道怎麼先找到一大坨去拆
原來可以用prefix看
只剩我還在2D了
class Solution {
public:
int countTriplets(vector<int>& arr) {
// a == b imply (a xor b) == 0
int n = arr.size();
vector<vector <int>> dp(n, vector<int>(0, {}));
dp[0] = arr;
int res = 0;
//dp[i][j]
for(int i = 1; i < n; i++){
int t1, t2;
int sub = (i+1)/2;
for(int j = 0; j < n-i; j++){
if(i % 2){
// 012 345
t1 = dp[i-sub][j];
t2 = dp[i-sub][j+sub];
}
else{
// 01
t1 = dp[i-sub-1][j];
t2 = dp[i-sub][j+sub];
}
dp[i].push_back(t1 xor t2);
if(dp[i][j] == 0 ){
res += i;
}
}
}
return res;
}
};