После того, как Хайди изучила полиномиальное хеширование, она решила изучить хэширование через битовый сдвиг и xor. В частности, она наткнулась на следующую задачу:
Дана битовая строка \(y \in \{0,1\}^n\). Нужно посчитать количество \(k\) (\(0 \leq k < n\)), таких что существует \(x \in \{0,1\}^n\), такой что \(y = x \oplus \mbox{shift}^k(x).\)
Где \(\oplus\) обозначает побитового xor, а \(\mbox{shift}^k\) обозначает операцию циклического сдвига битовой строки направо \(k\) раз. Например, \(001 \oplus 111 = 110\), а \(\mbox{shift}^3(00010010111000) = 00000010010111\).