you can think in pascal triangle for cell (i , j) how many times the cell (1 , 1) contribute at so like

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1

for example so Now known the fact that the cell (i , j) of pascal triangle is Ncr(i , j) and knowing also that in pascal triangle the value of the cell(i , j) is how many time the root (cell(1 , 1)) effect on the cell (i , j) , we can know that Ncr(i , j) is equal to the number of times the root contribute to cell (i , j) returning to our problem which change the operator in pascal triangle to XOR , to solve we just need to know the parity for the contribution from the root to the cell we need , so we just interested in parity of (Ncr(n , i)).

to solve the previous subproblem there are two ways 1. use Locus theorem that mention to know that if Ncr(i , j) is odd then No bit equal to 1 in j that is a 0 in i 2. you can just keep tracking of number of two in factorials and to know the Ncr(i , j) is even number of twos in fact[i] > number of twos in fact[j] + number of twos in fact[i — j]

Think of xor as binary addition without carrying. Then the xor of the two elements above the current element is just the sum of the two elements above in binary without carrying.

Legendre’s theorem combined with factorial definition of combinations works

By Lucas's Theorem or Kummer's Theorem, $$$\binom{a+b}a$$$ is odd if and only if $$$a$$$ and $$$b$$$ do not share any ones in their binary representations. Therefore, Sierpinski's Triangle comes from $$$\binom{i+j}i$$$ being odd if and only if $$$\binom{2^k+i+j}{2^k+i}$$$ is odd, if and only if $$$\binom{2^k+i+j}i$$$ is odd whenever $$$2^k>i,j$$$, since you can visualize this as recursively constructing the triangle given the first $$$2^k$$$ rows by sliding it $$$2^k$$$ down and then copying it on the left and right side to form the next $$$2^k$$$ rows.