Ta định nghĩa:

• ~dp[i][j]~ là số cách chia dãy từ ~a[1...i]~ thành ~j~ nhóm và những cách chia này thỏa mãn với yêu cầu đề bài.

• ~pre[i]~ là tổng xor của dãy ~a[1...i]~ ~(a[1] \oplus a[2] \oplus ... \oplus a[i])~.

• ~mask(x, i)~ là ~bit~ thứ ~i~ của ~x~

Từ đó ta dễ dàng xây dựng được công thức: $$dp[i][j] = \sum_{\substack k=1}^{i-1} dp[k][j - 1]$$ với điều kiện ~L[j] \le pre[i] \oplus pre[k] \le R[j]~

Giải thích điều kiện: ~L[j] \le (a[k+1] \oplus a[k+2] \oplus ... \oplus a[i]) \le R[j] \implies L[j] \le pre[i] \oplus pre[k] \le R[j]~

Vậy ta sẽ chuyển bài toán về thành: Với mỗi ~(i, j)~, cần tính hiệu của (tổng của các ~dp[k][j-1]~ với ~pre[i] \oplus pre[k] \le R[j]~ ~(1)~ và tổng của các ~dp[k][j - 1]~ với ~pre[i] \oplus pre[k] \le L[j] - 1~ ~(2)~).

Ta sẽ sử dụng ~k~ cây binary trie lưu biến sum, cây trie thứ ~j~ sẽ lưu các số ~pre[k]~ và cộng vào biến sum ở các node mà ~pre[k]~ đi qua một lượng ~dp[k][j]~.

Để tìm tổng ~(1)~, ta sẽ xét lần lượt các bit từ lớn đến bé của ~R[j]~ và ~pre[i]~, đi từ gốc của cây trie thứ ~j~, xảy ra các trường hợp sau (giả sử đang xét ~bit~ thứ ~x~):

• ~mask(R[j], x) = 1~: Ta sẽ cộng vào ~dp[i][j]~ một lượng ~sum~ của của cây con tương ứng với ~mask(pre[i], x)~. Sau đó ta đi xuống cây con tương ứng với ~mask(R[j], x) \oplus mask(pre[i], x)~.

• ~mask(R[j], x) = 0~: ta đi xuống cây con tương ứng với ~mask(R[j], x) \oplus mask(pre[i], x)~.

Tổng ~(2)~ tìm tương tự giống tổng ~(1)~.

Độ phức tạp: ~O(n*k*log(10^9))~.

Code: https://ideone.com/GTt9XJ.