CF1713F Lost Array

My orzlers, we can optimize this problem from $ O(S^3) $ to $ O\left(T^\frac{5}{9}\right) $ ! — Spyofgame, founder of Orzlim religion A long time ago, Spyofgame invented the famous array $ a $ ( $ 1 $ -indexed) of length $ n $ that contains information about the world and life. After that, he decided to convert it into the matrix $ b $ ( $ 0 $ -indexed) of size $ (n + 1) \times (n + 1) $ which contains information about the world, life and beyond. Spyofgame converted $ a $ into $ b $ with the following rules. - $ b_{i,0} = 0 $ if $ 0 \leq i \leq n $ ; - $ b_{0,i} = a_{i} $ if $ 1 \leq i \leq n $ ; - $ b_{i,j} = b_{i,j-1} \oplus b_{i-1,j} $ if $ 1 \leq i, j \leq n $ . Here $ \oplus $ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). Today, archaeologists have discovered the famous matrix $ b $ . However, many elements of the matrix has been lost. They only know the values of $ b_{i,n} $ for $ 1 \leq i \leq n $ (note that these are some elements of the last column, not the last row). The archaeologists want to know what a possible array of $ a $ is. Can you help them reconstruct any array that could be $ a $ ?

N/A

N/A

If we let $ a = [1,2,3] $ , then $ b $ will be: $ \bf{0} $ $ \bf{1} $ $ \bf{2} $ $ \bf{3} $ $ \bf{0} $ $ 1 $ $ 3 $ $ 0 $ $ \bf{0} $ $ 1 $ $ 2 $ $ 2 $ $ \bf{0} $ $ 1 $ $ 3 $ $ 1 $ The values of $ b_{1,n}, b_{2,n}, \ldots, b_{n,n} $ generated are $ [0,2,1] $ which is consistent with what the archaeologists have discovered.