Задача 703
Круговая логика II

Для данного целого числа $n$, $n \geq 3$, пусть $B=\{\mathrm{false},\mathrm{true}\}$ и пусть $B^n$ будет множеством последовательностей $n$ значений из $B$. Функция $f$ для $B^n$ от $B^n$ определена как $f(b_1 \dots b_n) = c_1 \dots c_n$, где:

  • $c_i = b_{i+1}$ для $1 \leq i < n$.
  • $c_n = b_1 \;\mathrm{AND}\; (b_2 \;\mathrm{XOR}\; b_3)$, где $\mathrm{AND}$ и $\mathrm{XOR}$ - логические действия $\mathrm{AND}$ и исключающего $\mathrm{OR}$ .

Пусть $S(n)$ будет количеством функций $T$ для $B$ от $B^n$ таких что для всех $x$ в $B^n$ $T(x) ~\mathrm{AND}~ T(f(x)) = \mathrm{false}$. Известно, что $S(3) = 35$ и $S(4) = 2118$.

Найдите $S(20)$. В качестве ответа приведите остаток от деления полученного результата на $1\,001\,001\,011$.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net