Автор задачи и разработчик: Антон Вдовин
Обозначим $$$i$$$-й символ $$$j$$$-й полученной строки за $$$s^j_i$$$. Тогда исходная строка равна $$$s^1 = \overline{s^1_0, \ldots, s^1_{n-1}}$$$, а для каждой следующей $$$s^{j+1}_i = s^j_i \oplus s_j^{i+1}$$$. Сходу стоит заметить, что эта формула чем-то напоминает формулу для подсчета числа сочетаний: $$$C_{n+1}^k = C_n^k + C^n_{k-1}$$$.
Также далее будем пользоваться эквивалентностью операции исключающего ИЛИ сложению по модулю $$$2$$$. Поэтому будем записывать $$$x \oplus x \oplus \ldots oplus x$$$, где $$$x$$$ встречается $$$y$$$ раз, как $$$y \cdot x$$$.
Распишем процесс полностью:
Несложно заметить, что коэффициенты, получающиеся при битах исходной строки — это значения из треугольника Паскаля. А как известно, значения в треугольнике Паскаля — это биномиальные коэффициенты $$$C_n^k$$$. Таким образом: $$$$$$s^{n-1}_1 = C_{n-1}^0 s^1_0 \oplus C_{n-1}^1 s^1_1 \oplus \ldots \oplus C_{n-1}^{n-1} s^1_{n-1} \text{.}$$$$$$
Чтобы посчитать это значение, вспомним, что на самом деле мы считаем не сумму, а XOR, а значит нам важен только остаток полученной суммы по модулю $$$2$$$. А найти четность биномиального коэффициента можно по теореме Люка, которая утверждает, что $$$C_n^k$$$ нечетно тогда и только тогда, когда нет бита, равного $$$1$$$ в $$$k$$$ и $$$0$$$ в $$$n$$$. Это можно проверить за $$$\mathcal{O}(1)$$$ следующим выражением: $$$k \land \lnot n \neq 0$$$ (либо же просто проитерироваться по битам и сравнить каждый).
Таким образом, посчитаем четность каждого биномиального коэффициента $$$C_{n-1}^i$$$, умножим на соответствующий бит исходной строки, и сложим. Получим наш ответ за время $$$\mathcal{O}(n)$$$.