Project Euler Problem 703

Solution

Answer: 843437991

Model the condition

$$T(x)\land T(f(x))=\mathrm{false}$$

as a graph problem on the functional graph of $f$ over the $2^n$ states of $B^n$.

Each state $x$ has exactly one outgoing edge $x \to f(x)$. The condition says that no directed edge may have both endpoints labeled true. Thus, for each connected component of the functional graph (a directed cycle with rooted trees feeding into it), we count the number of independent sets in that directed graph and multiply across components.

A dynamic programming approach works efficiently:

Build the functional graph of $f$ on all $2^n$ states.
Decompose into components (cycle + in-trees).
For each tree, compute DP:
$dp[u][0]$: ways if $u$ is false.
$dp[u][1]$: ways if $u$ is true.
Combine around each cycle with a cyclic DP enforcing no adjacent true assignments.

I verified the implementation against the provided values:

$S(3)=35$ ✓
$S(4)=2118$ ✓

For $n=20$,

$$S(20) \bmod 1001001011 = 843437991$$

Answer: 843437991