Detailed mathematical approach

Problem Summary

There are \(n\) seats in one row, and people sit down one after another. At every step, the allowed choices are exactly the empty seats with the smallest possible number of occupied neighbours. If \(T(n)\) denotes the number of complete seating orders, the program must compute \(T(10^6) \bmod 100000007\). A direct state search is exponential, so the solution counts orders through the gap pattern that appears after the last seat with zero occupied neighbours has been taken.

Mathematical Approach

Step 1: The greedy rule forces three phases

The neighbour count of an empty seat can only be \(0\), \(1\), or \(2\). Because the rule always chooses the minimum, every valid seating order is split into three consecutive phases: first all choices with \(0\) occupied neighbours, then all choices with \(1\) occupied neighbour, and finally all choices with \(2\) occupied neighbours. No move from a later phase can occur while an earlier phase is still available.

Step 2: The zero-neighbour skeleton

Stop the process exactly when no seat with \(0\) occupied neighbours remains. The occupied seats are then isolated singletons; let their number be \(m\). Between consecutive singletons there are \(m-1\) internal gaps. Each such gap must have length \(1\) or \(2\), because a longer internal gap would still contain a seat with zero occupied neighbours. At the ends, the left and right boundary gaps can only have length \(0\) or \(1\).

Let \(g_2\) be the number of internal gaps of length \(2\). Let the boundary gap lengths be \(\ell,r \in \{0,1\}\), and write

$s=\ell+r \in \{0,1,2\}.$

Counting occupied seats, internal gaps, and boundary gaps gives

$n = m + \bigl((m-1-g_2)\cdot 1 + g_2\cdot 2\bigr) + s = 2m - 1 + s + g_2.$

Therefore, once \(m\) and \(s\) are fixed, the implementation has no freedom left for \(g_2\):

$g_2 = n - (2m - 1 + s), \qquad 0 \le g_2 \le m - 1.$

Step 3: Count the possible skeleton shapes

The value of \(s\) does not uniquely determine the two boundary gaps. There is one boundary pattern for \(s=0\), two patterns for \(s=1\), and one pattern for \(s=2\). The corresponding multiplicities are

$w_0=1,\qquad w_1=2,\qquad w_2=1.$

After the boundary type is chosen, we must decide which \(g_2\) of the \(m-1\) internal gaps have length \(2\). Hence the number of skeleton shapes is

$N_{\mathrm{shape}} = w_s \binom{m-1}{g_2}.$

Step 4: Count all valid orders for one fixed skeleton

Phase 1 contains the \(m\) isolated singleton seats. Since they are pairwise non-adjacent in the skeleton, they may be chosen in any order, contributing \(m!\).

In Phase 2, each boundary gap of length \(1\) contributes one forced seat with one occupied neighbour, while each internal gap of length \(2\) contributes exactly one one-neighbour choice and a left-or-right decision. Thus there are \(s+g_2\) Phase-2 events, they can be interleaved arbitrarily, and each long internal gap contributes a factor \(2\):

$N_1 = (s+g_2)! \, 2^{g_2}.$

After Phase 2, every internal gap leaves exactly one empty seat between two occupied seats, so Phase 3 contains \(m-1\) independent two-neighbour choices. Their order is arbitrary, giving

$N_2 = (m-1)!.$

Multiplying the shape count and the ordering count, one feasible triple \((m,s,g_2)\) contributes

$w_s \binom{m-1}{g_2} m! (m-1)! (s+g_2)! 2^{g_2}.$

Step 5: Final formula and a small check

Summing over all \(m\) and all \(s \in \{0,1,2\}\) yields

$\boxed{T(n)=\sum_{m=1}^{n}\sum_{s=0}^{2} w_s \binom{m-1}{g_2} m! (m-1)! (s+g_2)! 2^{g_2}, \qquad g_2=n-(2m-1+s),}$

with all cases outside \(0 \le g_2 \le m-1\) discarded. For \(n=4\), the only feasible triples are \((m,s,g_2)=(2,0,1)\) and \((2,1,0)\). Their contributions are \(4\) and \(4\), so

$T(4)=8,$

which matches the brute-force checkpoint in the C++ source.

How the Code Works

The C++, Python, and Java files all implement exactly this sum. They precompute factorials, inverse factorials, and powers of \(2\) modulo \(P=100000007\). Because \(P\) is prime, the inverse factorial table is built with Fermat's little theorem, starting from \((n+1)!^{P-2} \bmod P\). The arrays boundary_sum = [0, 1, 2] and boundary_mult = [1, 2, 1] encode the possible values of \(s\) and \(w_s\). For each \(m\), the code computes \(g_2\), skips impossible cases, evaluates \(\binom{m-1}{g_2}\) through factorial tables, and adds the corresponding term. The C++ version uses __int128 for safe intermediate products; Python and Java follow the same arithmetic formula.

The checkpoints embedded in the source are \(T(4)=8\), \(T(10)=61632\), and \(T(1000)\equiv 47255094 \pmod{100000007}\).

Complexity Analysis

The factorial, inverse-factorial, and power tables are built in \(O(n)\) time and \(O(n)\) memory. The main summation examines \(n\) values of \(m\) and only three boundary states for each value, so the total runtime is \(O(n)\) and the memory usage remains \(O(n)\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=364
2. Binomial coefficients modulo a prime: cp-algorithms
3. Fermat's little theorem: Wikipedia