---

Problem 703

---

Circular Logic II

Given an integer $n$, $n \geq 3$, let $B={\mathrm{false},\mathrm{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\ \mathrm{AND}\ (b_2\ \mathrm{XOR}\ b_3)$, where $\mathrm{AND}$ and $\mathrm{XOR}$ are the logical $\mathrm{AND}$ and exclusive $\mathrm{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}$. You are given that $S(3) = 35$ and $S(4) = 2118$.

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

---

圆环之理II

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

• 对于$1 \leq i<n$，$c_i = b_{i+1}$。
• $c_n = b_1\ \mathrm{AND}\ (b_2\ \mathrm{XOR}\ b_3)$，其中$\mathrm{AND}$和$\mathrm{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$取余。

---