problem link
I was able to solve for L = 1 using xor convolution
can any please explain how to solve for L > 1
thanks
Here is my proposed solution, It is not fully formatted but gives you the intuition about the solution. And editorial will be available soon.
Solution
First let’s solve a smaller problem. What if the same question was asked for an array? i.e. An array A is given. Find the sum of beauty over all subarrays where beauty is equal to the product of xor of subarray and size of the subarray.
Prefix-Sum technique: We can solve the question over each bit level. Let’s suppose we know the prefix xor for all valid j(j <= i) then how to find the subarray whose endpoint is (i+1) and xor equal to 1. We can do this simply to find out the values of prefixes whose xor is 0, but how can we convert this into the length. Let suppose there are 3 prefixes with index value x_1, x_2, x_3 such that x_1, x_2, x_3 \le i than the ans for (i+1) index is given by-
- (i+1) - x1 + 1 + (i+1) - x2 + 1 + (i+1) - x3 + 1
- 3*(i+1) - (x1 + x2 + x3) + 3
- Count of prefix equal to zero xor*(i+1) - sum of their index value + count of prefix equal to zero xor
answer_i is equal to the sum of ans for each i. As we do this calculation for each bit and suppose there are n bits and we denote the answer for each bit by answer_j then the overall answer is given by-
ans = answer_0 * 2^0 + answer_1 * 2^1 + … + answer_n * 2^n
FTT technique: For each length from 1 to N if we are able to find out the number of subarrays such that their xor is 1(we are still working on each bit level). Then answer_j can be nothing but the sum of the product of count of a subarray of length k and k for each valid k.
To find that, we first find the prefix of the array(still on bit-level) and we know if we subtract a prefix with xor equal to zero out of prefix of xor equal to 1 then we get a subarray with xor equal to 1, so construct the first polynomial where power is the size of the prefix and coefficient is 1 if the xor is 1 otherwise coefficient is 0 and the second polynomial where power is the size of the prefix(in negative) and the coefficient is 1 if the xor is 0 otherwise coefficient is 1.
Let the product of these polynomials is P then the power represents the length of the subarray and the coefficient represents the number of a subarray of that length with xor equal to 1.
But this is not all what If any prefix has xor equal to 0 and we substrate xor 1 prefix from it then this subarray also has the answer is 1, we can just reverse the sign of the power of polynomial P and add that to P gives the desired polynomial.
Now, back to our original question, As a submatrix is represented by two subarrays of different subarrays, so we can manipulate the answer for xor of the matrix from these subarrays.
- If Both subarrays have even length then the submatrix should have xor value zero.
Let suppose (even_A)^1 implies that the number of even length subarray in A with xor 1. If we observe than the sum of beauty over all sub-matrix is given by-
- (even_B)^1 * ((odd_A)^0 + (odd_A)^1) + (even_A)^1 * ((odd_B)^0 + (odd_B)^1) + (odd_A)^1 * ((odd_B)^0 + (odd_B)^1) + (odd_B)^1 * (odd_A)^0
To answer queries, we can use a segment or Fenwick tree or simple prefix sum.
Complexity: O(N log^2 N)
2 Likes
Please upload an official tutorial with a heavy explanation asap as this one is a bit harder one and we can’t hold our excitement.