\textit{Автор задачи и разработчик: Ильдар Гайнуллин}
\vspace{0.2em}


Рассмотрим последовательность чисел Фибоначчи, не превосходящих $m$.

Если мы рассмотрим все числа как вектора по модулю два, то почти все числа Фибоначчи находятся в базисе, кроме порядка двадцати. Так как часто старший бит $F_k$ отличается от старшего бита $F_{k-1}$.

Переберем для всех чисел Фибоначчи, которые не входят в базис, входят ли они в итоговый XOR (встречаются нечетное число раз), или нет, пусть их XOR равен $x$. Дальше разложим $n \oplus x$ в линейную комбинацию векторов базиса. Так мы переберем порядка $2^{20}$ различных векторов, которые соответствуют числам Фибоначчи, которые встречаются нечетное число раз. Если их сумма равна $y$, то дальше необходимо $m-y$ представить в виде суммы удвоенных чисел Фибоначчи, что можно сделать жадно, при правильной четности.