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; } }; ----- Sent from JPTT on my iPad -- ※ 發信站: 批踢踢實業坊(ptt-website.tw), 來自: 123.205.121.194 (臺灣) ※ 文章網址: https://ptt-website.tw/Marginalman/M.1717101496.A.072