\begin{proposal}{XOR}{}{}{}

\Author

Нияз Нигматуллин

\ProblemIdea

Дано число $k$. $F(x)$ ~--- количество способов представить число $x$ с помощью xor различных чисел не превосходящих $k$, двоичное представление которых имеет вид $1^x0^y$.
Дано $N$, найти $F(N)$

\SolutionIdea

Рассмотрим матрицу $A$, где столбцы это двоичные представления доступных нам чисел. 
Тогда количество способов~--- это количество решений такой системы уравнений: $Ax = y$, где $y$~--- это двоичное представление $N$.
А это либо $0$, либо $2 ^ {n - rgA}$, где $n$~--- кол-во строк в матрице $A$.

\ProblemVariations

Посчитать сумму $F(x)$, по всем $L \le x \le R$.
Для этого надо посчитать кол-во $x$, для которых $F(x) = 0$.

\ProblemComplexity

Идея~--- H(сложная). Реализация~---H(сложная).

\WrongSolutions


\end{proposal}
