Detailed mathematical approach

Problem Summary

For an \(n\)-bit state \(x\), write

$x=b_0+2b_1+4b_2+\cdots+2^{n-1}b_{n-1},\qquad b_i\in\{0,1\}.$

The transition rule keeps shifting the bits to the right and inserts a new highest bit given by

$b_0\land(b_1\oplus b_2).$

So the next state is

$f(x)=\left\lfloor\frac{x}{2}\right\rfloor+2^{n-1}\bigl(b_0\land(b_1\oplus b_2)\bigr).$

The implementations reduce the counting task to the following graph problem on the \(N=2^n\) states: count all subsets of vertices such that no state is chosen together with its image under \(f\). In graph-theoretic language, this is an independent-set count on a special functional digraph, and the final result is taken modulo \(1001001011\).

Mathematical Approach

Let \(G_n\) be the directed graph with one vertex for each state \(x\in\{0,1,\dots,2^n-1\}\) and one directed edge \(x\to f(x)\). Because every vertex has exactly one outgoing edge, every connected component of \(G_n\) has a very rigid shape: one directed cycle, with rooted trees feeding into the cycle.

Step 1: Turn the Bit Rule into a Functional Graph

The mapping \(f\) is completely determined by the lowest three bits of \(x\). Every vertex therefore has outdegree \(1\), although its indegree may vary. This matters because graphs of outdegree \(1\) are functional graphs, and each component decomposes into exactly one cycle plus zero or more in-trees.

That decomposition is the structural reason the problem is tractable. Instead of counting admissible subsets on the full graph at once, we can solve each component separately and multiply the answers.

Step 2: Reformulate the Constraint as an Independent-Set Condition

If a subset \(S\) of states is valid, then no directed edge \(x\to f(x)\) may have both endpoints in \(S\). Since the restriction only concerns adjacent states, we can forget the arrow direction for counting purposes and work with the underlying undirected graph.

So the problem becomes: how many independent sets does each unicyclic component have? Once that is known, the total answer is

$\prod_{\text{components }C}\operatorname{IS}(C)\pmod{1001001011},$

where \(\operatorname{IS}(C)\) denotes the number of independent sets in component \(C\).

Step 3: Solve Every Tree Feeding into a Cycle

Take a non-cycle vertex \(u\), and orient its attached tree away from the cycle. Define

$E(u)=\text{number of valid selections in the subtree of }u\text{ when }u\text{ is excluded},$

$I(u)=\text{number of valid selections in the subtree of }u\text{ when }u\text{ is included}.$

If the children of \(u\) are \(v_1,\dots,v_k\), then standard tree DP gives

$E(u)=\prod_{j=1}^{k}\bigl(E(v_j)+I(v_j)\bigr),$

$I(u)=\prod_{j=1}^{k}E(v_j).$

The first formula allows each child to be either excluded or included. The second forbids including any child once \(u\) itself is included. A leaf satisfies

$E(u)=1,\qquad I(u)=1.$

Step 4: Collapse the Trees into Weights on the Cycle

Now consider a cycle \(c_1,c_2,\dots,c_m\). Each cycle vertex may have extra tree children that are not on the cycle. After solving those trees, we compress their effect into two local weights:

$W_i^{(0)}=\prod_{v\in T_i}\bigl(E(v)+I(v)\bigr),$

$W_i^{(1)}=\prod_{v\in T_i}E(v),$

where \(T_i\) is the set of non-cycle children attached directly to \(c_i\).

Interpretation:

\(W_i^{(0)}\) counts all valid choices in the incoming trees when \(c_i\) is not selected.

\(W_i^{(1)}\) counts all valid choices in the incoming trees when \(c_i\) is selected, so every attached child must stay out.

After this compression, the whole component is reduced to a weighted cycle.

Step 5: Run a Two-Case DP Around the Cycle

For a path version of the cycle, let

$P_i^{(0)}=\text{weighted count up to }c_i\text{ with }c_i\text{ excluded},$

$P_i^{(1)}=\text{weighted count up to }c_i\text{ with }c_i\text{ included}.$

Then for \(i\ge 2\),

$P_i^{(0)}=\bigl(P_{i-1}^{(0)}+P_{i-1}^{(1)}\bigr)W_i^{(0)},$

$P_i^{(1)}=P_{i-1}^{(0)}W_i^{(1)}.$

Because \(c_1\) and \(c_m\) are adjacent on the cycle, we split into two boundary cases.

Case A: \(c_1\) is excluded. Start with

$P_1^{(0)}=W_1^{(0)},\qquad P_1^{(1)}=0.$

This contributes

$P_m^{(0)}+P_m^{(1)}.$

Case B: \(c_1\) is included. Start with

$P_1^{(0)}=0,\qquad P_1^{(1)}=W_1^{(1)}.$

Now \(c_m\) must be excluded, so this contributes only

$P_m^{(0)}.$

If \(m=1\), the cycle is a self-loop. Then the lone cycle vertex cannot be selected at all, and the component contributes simply

$W_1^{(0)}.$

Worked Example: \(n=3\)

For \(n=3\) there are \(8\) states. Writing states in binary, the transition graph splits into two components:

000 -> 000, with the chain 100 -> 010 -> 001 -> 000.

011 -> 101 -> 110 -> 011, with the extra leaf 111 -> 011.

In the first component, 000 is a self-loop, so it cannot be chosen. What remains is the path 100-010-001, whose independent sets are

$\varnothing,\ \{100\},\ \{010\},\ \{001\},\ \{100,001\},$

so that component contributes \(5\).

In the second component, the leaf attached to 011 gives weights

$W_1^{(0)}=2,\qquad W_1^{(1)}=1,$

while the other two cycle vertices have weights

$W_2^{(0)}=W_2^{(1)}=W_3^{(0)}=W_3^{(1)}=1.$

Case A, first cycle vertex excluded:

$P_1=(2,0),\qquad P_2=(2,2),\qquad P_3=(4,2),$

so the contribution is \(4+2=6\).

Case B, first cycle vertex included:

$P_1=(0,1),\qquad P_2=(1,0),\qquad P_3=(1,1),$

and only the excluded-last state is allowed, so the contribution is \(1\).

Thus the 3-cycle component contributes \(6+1=7\), and the total is

$5\cdot 7=35,$

which matches the small checkpoint used by the implementation.

How the Code Works

The C++, Python, and Java implementations first build the transition table for all \(2^n\) states and, at the same time, the reverse adjacency lists that list every predecessor of each state. They then find every directed cycle by a standard three-color walk: unvisited, currently on the path, and fully processed. Whenever a walk re-enters a currently active vertex, the cycle segment is recorded.

After the cycles are known, the implementation evaluates every incoming tree exactly once with a post-order dynamic program. Those tree values are folded into the two weights for each cycle vertex, and then a second DP is run around the cycle using the two boundary cases described above. Each component count is multiplied into the global answer modulo \(1001001011\).

Complexity Analysis

Let \(N=2^n\). Building the transition table and reverse graph takes \(O(N)\) time and \(O(N)\) memory. Cycle detection also visits each vertex a constant number of times, so it is \(O(N)\). The tree DP and cycle DP together process each edge and each vertex only once more, so the total running time remains

$O(N)=O(2^n),$

with memory usage

$O(N)=O(2^n).$

For the actual input \(n=20\), this means linear work over \(1{,}048{,}576\) states, which is exactly why the graph decomposition is effective.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=703
2. Independent set: Wikipedia - Independent set
3. Dynamic programming: Wikipedia - Dynamic programming
4. Cycle finding in directed graphs: CP-Algorithms - Checking a graph for acyclicity and finding a cycle
5. Shift registers and feedback rules: Wikipedia - Shift register