Hey everyone!

I was recently practicing on the CSES Problem Set and ran into Xor Pyramid Diagonal. After being stuck for a while, I tried finding an editorial but couldn't find one.

After gathering ideas from different places and finally solving the problem, I thought to write an editorial in case anyone else gets stuck on the same thing.

Key Idea: Pascal's Triangle & Parity

If you've already solved the previous Xor Pyramid Peak (where you only need the peak element), you probably know that each element's contribution behaves just like Pascal's triangle elements of row $$$n-1$$$.

The exact same logic applies here. Number the rows from the bottom, with the input array as row $$$0$$$. The leftmost element of row $$$r$$$ depends only on $$$a_0, a_1, \dots, a_r$$$. In other words, it is the peak of the smaller pyramid built on $$$a_0, \dots, a_r$$$, which has height $$$r$$$. So the Peak formula applies with $$$n-1 = r$$$.

Let $$$P(r, 0)$$$ denote the leftmost element of row $$$r$$$. Then $$$a_j$$$ contributes to $$$P(r, 0)$$$ with weight $$$\binom{r}{j}$$$, and since XOR cancels pairs, it only matters whether this weight is odd:

So an element $$$a_j$$$ is included in the XOR if and only if $$$\binom{r}{j}$$$ is odd.

Lucas' Theorem

By Lucas' Theorem modulo $$$2$$$:

So the problem simply reduces to:

For every $$$0 \le r \lt n$$$, we just need the XOR sum of all elements whose indices are submasks of $$$r$$$.

Fast Submask XOR via SOS DP

Iterating through all submasks for each $$$r$$$ naively is too slow. Since $$$n \le 2 \cdot 10^5 \lt 2^{18}$$$, we can compute the XOR sum over all subsets simultaneously using standard Sum Over Subsets (SOS) DP in $$$\mathcal{O}(B \cdot n)$$$ where $$$B = 18$$$. If you haven't seen this technique before, this blog is a great introduction.

We just iterate over each bit position and propagate the XOR sums in-place. After the transform, $$$a_r$$$ holds the XOR of all $$$a_j$$$ with $$$j \subseteq r$$$, which is exactly $$$P(r, 0)$$$, so we print the array as is.

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin>>a[i];
    //SOS DP
    for(int i=1;i<(1<<18);i<<=1){
        for(int j=0;j<n;j++) if(j&i) a[j] ^= a[j^i];
    }
    for(int i=0;i<n;i++) cout<<a[i]<<' ';
    return 0;
}