Problem 703

Circular Logic II

Given an integer $n$ , $n \geq 3$ , let $B = false, true$ and let $B^{n}$ be the set of sequences of $n$ values from $B$ . The function $f$ from $B^{n}$ to $B^{n}$ is defined by $f (b_{1} \dots b_{n}) = c_{1} \dots c_{n}$ where:

$c_{i} = b_{i + 1}$ for $1 \leq i < n$ .
$c_{n} = b_{1} AND (b_{2} XOR b_{3})$ , where $AND$ and $XOR$ are the logical $AND$ and exclusive $OR$ operations.

Let $S (n)$ be the number of functions $T$ from $B^{n}$ to $B$ such that for all $x$ in $B^{n}$ , $T(x) ~~\mathrm{AND}~~ T(f(x)) = \mathrm{false} $. Y o u a r e g i v e n t h a t$ S(3) = 35 $a n d$ S(4) = 2118$.

Find $S (20)$ . Give your answer modulo $1 001 001 011$ .

圆环之理II

给定整数 $n$ ， $n \geq 3$ ，令 $B = false, true$ 而 $B^{n}$ 为从 $B$ 中选择 $n$ 个值所组成的序列。由 $B^{n}$ 映射到 $B^{n}$ 的函数 $f$ ，记为 $f (b_{1} \dots b_{n}) = c_{1} \dots c_{n}$ ，满足以下条件：

对于 $1 \leq i < n$ ， $c_{i} = b_{i + 1}$ 。
$c_{n} = b_{1} AND (b_{2} XOR b_{3})$ ，其中 $AND$ 和 $XOR$ 分别是逻辑与和逻辑异或运算。

考虑由 $B^{n}$ 映射到 $B$ 的函数 $T$ ，对于任意 $x$ 属于 $B^{n}$ 满足$T(x) ~~\mathrm{AND}~~ T(f(x)) = \mathrm{false} $，记所有此类函数的数目为$ S(n) $。已知$ S(3) = 35 $，$ S(4) = 2118$。

求 $S (20)$ ，并将你的答案对 $1 001 001 011$ 取余。