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.
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.
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.$$
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}.$$
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}.$$
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.
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}\).
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)\).
Es gibt \(n\) Sitze in einer Reihe, und die Personen setzen sich nacheinander. In jedem Schritt sind genau die leeren Sitze erlaubt, die die kleinste mögliche Zahl besetzter Nachbarn haben. Bezeichne mit \(T(n)\) die Anzahl aller vollständigen Sitzreihenfolgen. Das Programm soll \(T(10^6) \bmod 100000007\) berechnen. Eine direkte Zustandsenumeration wäre exponentiell, daher zählt die Lösung die Reihenfolgen über das Lückenmuster, das nach dem letzten Sitz mit null besetzten Nachbarn entsteht.
Die Nachbarzahl eines leeren Sitzes kann nur \(0\), \(1\) oder \(2\) sein. Weil immer das Minimum gewählt wird, zerfällt jede gültige Reihenfolge in drei aufeinanderfolgende Phasen: zuerst alle Sitze mit \(0\) besetzten Nachbarn, danach alle Sitze mit \(1\) besetztem Nachbarn und zuletzt alle Sitze mit \(2\) besetzten Nachbarn. Ein Zug aus einer späteren Phase ist unmöglich, solange noch ein Zug aus einer früheren Phase existiert.
Stoppe den Prozess genau dann, wenn kein Sitz mit \(0\) besetzten Nachbarn mehr vorhanden ist. Die bereits belegten Sitze sind dann isolierte Einzelplätze; ihre Anzahl sei \(m\). Zwischen zwei aufeinanderfolgenden Einzelplätzen liegen \(m-1\) innere Lücken. Jede dieser Lücken hat Länge \(1\) oder \(2\), denn eine längere innere Lücke würde noch einen Sitz mit null besetzten Nachbarn enthalten. An den beiden Rändern dürfen die Lücken nur Länge \(0\) oder \(1\) haben.
Sei \(g_2\) die Anzahl der inneren Lücken der Länge \(2\). Für die linken und rechten Randlücken schreiben wir \(\ell,r \in \{0,1\}\) und setzen
$$s=\ell+r \in \{0,1,2\}.$$
Durch Abzählen der belegten Sitze, inneren Lücken und Randlücken erhält man
$$n = m + \bigl((m-1-g_2)\cdot 1 + g_2\cdot 2\bigr) + s = 2m - 1 + s + g_2.$$
Damit ist \(g_2\) für feste Werte von \(m\) und \(s\) bereits bestimmt:
$$g_2 = n - (2m - 1 + s), \qquad 0 \le g_2 \le m - 1.$$
Der Wert \(s\) legt die beiden Randlücken nicht eindeutig fest. Für \(s=0\) gibt es genau ein Randmuster, für \(s=1\) zwei Muster und für \(s=2\) wieder ein Muster. Also
$$w_0=1,\qquad w_1=2,\qquad w_2=1.$$
Ist der Randtyp gewählt, muss man festlegen, welche \(g_2\) der \(m-1\) inneren Lücken die Länge \(2\) haben. Somit ist die Anzahl der Skelette
$$N_{\mathrm{shape}} = w_s \binom{m-1}{g_2}.$$
Phase 1 besteht aus den \(m\) isolierten Einzelplätzen. Da sie im Skelett paarweise nicht benachbart sind, dürfen sie in beliebiger Reihenfolge gewählt werden; das liefert den Faktor \(m!\).
In Phase 2 liefert jede Randlücke der Länge \(1\) genau einen erzwungenen Sitz mit einem besetzten Nachbarn. Jede innere Lücke der Länge \(2\) liefert genau einen Ein-Nachbar-Zug und zusätzlich eine Links-Rechts-Entscheidung. Daher gibt es \(s+g_2\) Ereignisse in Phase 2, sie können beliebig ineinander verschachtelt werden, und jede lange innere Lücke liefert einen Faktor \(2\):
$$N_1 = (s+g_2)! \, 2^{g_2}.$$
Nach Phase 2 bleibt in jeder inneren Lücke genau ein leerer Sitz zwischen zwei besetzten Sitzen zurück. Phase 3 enthält also \(m-1\) unabhängige Zwei-Nachbar-Züge, deren Reihenfolge beliebig ist:
$$N_2 = (m-1)!.$$
Damit trägt ein zulässiges Tripel \((m,s,g_2)\) den Faktor
$$w_s \binom{m-1}{g_2} m! (m-1)! (s+g_2)! 2^{g_2}$$
zum Gesamtergebnis bei.
Durch Summation über alle \(m\) und alle \(s \in \{0,1,2\}\) erhält man
$$\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),}$$
wobei alle Fälle mit \(g_2\lt 0\) oder \(g_2>m-1\) verworfen werden. Für \(n=4\) sind nur \((m,s,g_2)=(2,0,1)\) und \((2,1,0)\) möglich. Beide Beiträge sind \(4\), also
$$T(4)=8,$$
genau wie im Brute-Force-Kontrollwert der C++-Datei.
Die C++-, Python- und Java-Implementierungen berechnen exakt diese Summe. Vorab werden Fakultäten, inverse Fakultäten und Zweierpotenzen modulo \(P=100000007\) berechnet. Da \(P\) eine Primzahl ist, wird die Tabelle der inversen Fakultäten mit dem kleinen Satz von Fermat aufgebaut; Startwert ist \((n+1)!^{P-2} \bmod P\). Die Arrays boundary_sum = [0, 1, 2] und boundary_mult = [1, 2, 1] kodieren die möglichen Werte von \(s\) und \(w_s\). Für jedes \(m\) berechnet der Code \(g_2\), überspringt unzulässige Fälle, wertet \(\binom{m-1}{g_2}\) mit den Fakultätstabellen aus und addiert den passenden Term. Die C++-Version nutzt __int128 für sichere Zwischenprodukte; Python und Java folgen derselben Formel.
Die im Quelltext verankerten Kontrollwerte sind \(T(4)=8\), \(T(10)=61632\) und \(T(1000)\equiv 47255094 \pmod{100000007}\).
Die Tabellen für Fakultäten, inverse Fakultäten und Zweierpotenzen benötigen \(O(n)\) Zeit und \(O(n)\) Speicher. Die Hauptsumme betrachtet \(n\) Werte von \(m\) und pro Wert nur drei Randzustände. Insgesamt ergibt sich also \(O(n)\) Laufzeit bei \(O(n)\) Speicherverbrauch.
Bir sırada \(n\) koltuk vardır ve insanlar tek tek oturur. Her adımda yalnızca dolu komşu sayısı en küçük olan boş koltuklar seçilebilir. Tüm tam oturma sıralarının sayısını \(T(n)\) ile gösterelim. Programın görevi \(T(10^6) \bmod 100000007\) değerini hesaplamaktır. Doğrudan durum ağacı üstel büyüdüğü için çözüm, sıfır dolu komşulu son seçimden sonra oluşan boşluk iskeletini sayar.
Boş bir koltuğun dolu komşu sayısı yalnızca \(0\), \(1\) veya \(2\) olabilir. Kural her zaman minimumu seçtiği için her geçerli oturma sırası üç ardışık fazdan oluşur: önce \(0\) dolu komşulu seçimler, sonra \(1\) dolu komşulu seçimler ve en sonda \(2\) dolu komşulu seçimler. Erken bir fazda seçenek varken daha geç bir fazdan seçim yapılamaz.
Hiç \(0\) dolu komşulu koltuk kalmadığı anda süreci durduralım. O anda dolu olan koltukların hepsi birbirinden ayrık tekli bloklardır; sayıları \(m\) olsun. Ardışık iki tekli blok arasında \(m-1\) iç boşluk vardır. Her iç boşluğun uzunluğu yalnızca \(1\) veya \(2\) olabilir; daha uzun bir iç boşluk içinde hâlâ \(0\) dolu komşulu bir koltuk bulunurdu. Sol ve sağ sınır boşlukları da sadece \(0\) veya \(1\) uzunluğunda olabilir.
Uzunluğu \(2\) olan iç boşlukların sayısına \(g_2\) diyelim. Sol ve sağ sınır boşluklarını \(\ell,r \in \{0,1\}\) ile gösterip
$$s=\ell+r \in \{0,1,2\}$$
tanımını yapalım. Dolu koltukları, iç boşlukları ve sınır boşluklarını sayarsak
$$n = m + \bigl((m-1-g_2)\cdot 1 + g_2\cdot 2\bigr) + s = 2m - 1 + s + g_2$$
elde edilir. Böylece \(m\) ve \(s\) sabitken \(g_2\) artık zorunlu olarak
$$g_2 = n - (2m - 1 + s), \qquad 0 \le g_2 \le m - 1$$
olur.
\(s\) değeri iki sınır boşluğunu tek başına belirlemez. \(s=0\) için \(1\) desen, \(s=1\) için \(2\) desen ve \(s=2\) için yine \(1\) desen vardır. Dolayısıyla
$$w_0=1,\qquad w_1=2,\qquad w_2=1.$$
Sınır tipi seçildikten sonra \(m-1\) iç boşluktan hangilerinin uzunluk \(2\) olacağını seçeriz. İskelet sayısı bu yüzden
$$N_{\mathrm{shape}} = w_s \binom{m-1}{g_2}$$
olur.
Birinci fazda \(m\) adet tekli blok seçilir. Bu koltuklar iskelette yan yana olmadıkları için istenen sırada alınabilir; katkı \(m!\) olur.
İkinci fazda uzunluğu \(1\) olan her sınır boşluğu tam bir adet zorunlu bir-komşulu seçim verir. Uzunluğu \(2\) olan her iç boşluk ise tam bir adet bir-komşulu seçim ve ayrıca sol-sağ tercihi verir. Bu nedenle ikinci fazda toplam \(s+g_2\) olay vardır; bunlar serbestçe iç içe geçebilir ve her uzun iç boşluk bir \(2\) katsayısı üretir:
$$N_1 = (s+g_2)! \, 2^{g_2}.$$
İkinci faz bittiğinde her iç boşlukta iki dolu koltuk arasında tam bir boş koltuk kalır. Üçüncü faz bu yüzden \(m-1\) adet iki-komşulu seçim içerir ve bunların sırası serbesttir:
$$N_2 = (m-1)!.$$
Böylece uygun bir \((m,s,g_2)\) üçlüsünün katkısı
$$w_s \binom{m-1}{g_2} m! (m-1)! (s+g_2)! 2^{g_2}$$
olur.
Tüm \(m\) değerleri ve \(s \in \{0,1,2\}\) için toplarsak
$$\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),}$$
elde edilir; burada \(g_2\lt 0\) veya \(g_2>m-1\) olan durumlar atılır. \(n=4\) için yalnızca \((2,0,1)\) ve \((2,1,0)\) mümkündür. Bu iki durumun katkıları \(4\) ve \(4\) olduğundan
$$T(4)=8$$
çıkar; bu da C++ dosyasındaki kaba kuvvet kontrolüyle aynıdır.
C++, Python ve Java çözümleri aynı toplamı uygular. Önce \(P=100000007\) modunda faktöriyel, ters faktöriyel ve \(2\) kuvvetleri önceden hesaplanır. \(P\) asal olduğu için ters faktöriyel tablosu Fermat'ın küçük teoremi ile, \((n+1)!^{P-2} \bmod P\) değerinden başlayarak oluşturulur. boundary_sum = [0, 1, 2] ve boundary_mult = [1, 2, 1] dizileri \(s\) ve \(w_s\) değerlerini kodlar. Ana döngü her \(m\) için \(g_2\)'yi hesaplar, geçersiz durumları atlar, \(\binom{m-1}{g_2}\) değerini tablo yardımıyla bulur ve yukarıdaki terimi toplama ekler. C++ sürümü ara çarpımlarda güvenlik için __int128 kullanır; Python ve Java aynı aritmetik formülü izler.
Kaynak dosyalardaki kontrol değerleri \(T(4)=8\), \(T(10)=61632\) ve \(T(1000)\equiv 47255094 \pmod{100000007}\) şeklindedir.
Faktöriyel, ters faktöriyel ve kuvvet tabloları \(O(n)\) zamanda ve \(O(n)\) bellekte hazırlanır. Ana toplam \(m=1,\dots,n\) için çalışır ve her \(m\) başına yalnızca üç sınır durumu inceler. Bu yüzden toplam süre \(O(n)\), bellek kullanımı da \(O(n)\) olur.
Hay \(n\) asientos en una fila y las personas se sientan una por una. En cada paso solo se permiten los asientos vacíos cuyo número de vecinos ocupados es mínimo. Si \(T(n)\) denota el número de órdenes completos de ocupación, el programa debe calcular \(T(10^6) \bmod 100000007\). Un recorrido directo del árbol de estados sería exponencial, así que la solución cuenta los órdenes a partir del patrón de huecos que aparece justo después de tomar el último asiento con cero vecinos ocupados.
El número de vecinos ocupados de un asiento vacío solo puede ser \(0\), \(1\) o \(2\). Como la regla siempre elige el mínimo, cualquier orden válido se separa en tres fases consecutivas: primero todas las elecciones con \(0\) vecinos ocupados, después todas las elecciones con \(1\) vecino ocupado y por último todas las elecciones con \(2\) vecinos ocupados. Ningún movimiento de una fase posterior puede ocurrir mientras siga existiendo un movimiento de una fase anterior.
Detengamos el proceso exactamente cuando ya no queda ningún asiento con \(0\) vecinos ocupados. Los asientos ocupados forman entonces bloques aislados de tamaño \(1\); sea \(m\) su número. Entre dos bloques consecutivos hay \(m-1\) huecos internos. Cada hueco interno debe tener longitud \(1\) o \(2\), porque un hueco más largo todavía contendría un asiento con cero vecinos ocupados. En los extremos, los huecos de borde solo pueden tener longitud \(0\) o \(1\).
Sea \(g_2\) el número de huecos internos de longitud \(2\). Si los huecos de la izquierda y la derecha son \(\ell,r \in \{0,1\}\), definimos
$$s=\ell+r \in \{0,1,2\}.$$
Al contar asientos ocupados, huecos internos y huecos de borde obtenemos
$$n = m + \bigl((m-1-g_2)\cdot 1 + g_2\cdot 2\bigr) + s = 2m - 1 + s + g_2.$$
Por tanto, fijados \(m\) y \(s\), el valor de \(g_2\) queda determinado por
$$g_2 = n - (2m - 1 + s), \qquad 0 \le g_2 \le m - 1.$$
El valor de \(s\) no determina de forma única los dos huecos de borde. Hay una posibilidad para \(s=0\), dos para \(s=1\) y una para \(s=2\). Por eso
$$w_0=1,\qquad w_1=2,\qquad w_2=1.$$
Una vez fijado el tipo de borde, debemos elegir cuáles \(g_2\) de los \(m-1\) huecos internos tienen longitud \(2\). El número de esqueletos es entonces
$$N_{\mathrm{shape}} = w_s \binom{m-1}{g_2}.$$
La Fase 1 contiene los \(m\) asientos aislados. Como en el esqueleto nunca son adyacentes entre sí, pueden elegirse en cualquier orden, lo que aporta \(m!\).
En la Fase 2, cada hueco de borde de longitud \(1\) aporta un asiento forzado con un vecino ocupado. Cada hueco interno de longitud \(2\) aporta exactamente una elección de un vecino ocupado y además una decisión izquierda-derecha. Por tanto, hay \(s+g_2\) eventos de la Fase 2, pueden intercalarse arbitrariamente y cada hueco interno largo aporta un factor \(2\):
$$N_1 = (s+g_2)! \, 2^{g_2}.$$
Después de la Fase 2, cada hueco interno deja exactamente un asiento vacío entre dos asientos ocupados. La Fase 3 contiene entonces \(m-1\) elecciones independientes con dos vecinos ocupados, y su orden es libre:
$$N_2 = (m-1)!.$$
Así, un triple factible \((m,s,g_2)\) contribuye con
$$w_s \binom{m-1}{g_2} m! (m-1)! (s+g_2)! 2^{g_2}.$$
Al sumar sobre todos los \(m\) y todos los \(s \in \{0,1,2\}\) se obtiene
$$\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),}$$
omitiendo los casos con \(g_2\lt 0\) o \(g_2>m-1\). Para \(n=4\), los únicos triples posibles son \((2,0,1)\) y \((2,1,0)\). Sus contribuciones son \(4\) y \(4\), así que
$$T(4)=8,$$
exactamente el valor de comprobación por fuerza bruta del código C++.
Las versiones en C++, Python y Java implementan exactamente esta suma. Primero precalculan factoriales, factoriales inversos y potencias de \(2\) módulo \(P=100000007\). Como \(P\) es primo, la tabla de factoriales inversos se construye con el pequeño teorema de Fermat, empezando por \((n+1)!^{P-2} \bmod P\). Los arreglos boundary_sum = [0, 1, 2] y boundary_mult = [1, 2, 1] codifican los valores posibles de \(s\) y \(w_s\). Para cada \(m\), el programa calcula \(g_2\), descarta los casos imposibles, evalúa \(\binom{m-1}{g_2}\) con las tablas factoriales y acumula el término correspondiente. La versión en C++ usa __int128 para evitar desbordamientos intermedios; Python y Java siguen la misma fórmula aritmética.
Los puntos de control presentes en el código son \(T(4)=8\), \(T(10)=61632\) y \(T(1000)\equiv 47255094 \pmod{100000007}\).
Las tablas de factoriales, factoriales inversos y potencias se construyen en \(O(n)\) tiempo y \(O(n)\) memoria. La suma principal recorre \(n\) valores de \(m\) y solo tres estados de borde por cada uno. Por tanto, el tiempo total es \(O(n)\) y la memoria también es \(O(n)\).
一排共有 \(n\) 个座位，人员依次入座。每一步只能选择“已占邻座数最少”的空位。记所有完整入座顺序的数量为 \(T(n)\)。程序需要计算 \(T(10^6) \bmod 100000007\)。如果直接搜索状态树，规模会呈指数增长，因此实现采用的是组合计数：先观察所有“零个已占邻座”的选择结束后会形成什么样的空隙骨架，再对这种骨架进行计数。
空位的已占邻座数只可能是 \(0\)、\(1\) 或 \(2\)。因为规则总是选最小值，所以任何合法入座顺序都会自然分成三个连续阶段：先完成所有 \(0\) 邻座选择，再完成所有 \(1\) 邻座选择，最后才会出现 \(2\) 邻座选择。只要前一阶段还有可选位置，后一阶段的位置就绝不可能被选中。
当不存在任何 \(0\) 邻座空位时暂时停止。此时所有已占座位都是彼此分离的单点块；设它们的个数为 \(m\)。相邻两个单点块之间共有 \(m-1\) 个内部空隙。每个内部空隙的长度只能是 \(1\) 或 \(2\)，因为如果长度至少为 \(3\)，其中间仍然会存在一个 \(0\) 邻座空位。左右两个边界空隙的长度也只能是 \(0\) 或 \(1\)。
设长度为 \(2\) 的内部空隙有 \(g_2\) 个。左、右边界空隙分别记为 \(\ell,r \in \{0,1\}\)，并定义
$$s=\ell+r \in \{0,1,2\}.$$
把已占座位、内部空隙和边界空隙全部加起来，就得到
$$n = m + \bigl((m-1-g_2)\cdot 1 + g_2\cdot 2\bigr) + s = 2m - 1 + s + g_2.$$
因此，一旦 \(m\) 和 \(s\) 固定，\(g_2\) 就被唯一确定为
$$g_2 = n - (2m - 1 + s), \qquad 0 \le g_2 \le m - 1.$$
\(s\) 只给出左右边界空隙长度之和，并不能唯一确定两侧。\(s=0\) 时有 \(1\) 种边界模式，\(s=1\) 时有 \(2\) 种，\(s=2\) 时有 \(1\) 种，所以
$$w_0=1,\qquad w_1=2,\qquad w_2=1.$$
选定边界类型后，还要从 \(m-1\) 个内部空隙中选出哪 \(g_2\) 个长度为 \(2\)。因此骨架数量为
$$N_{\mathrm{shape}} = w_s \binom{m-1}{g_2}.$$
第一阶段包含 \(m\) 个彼此分离的单点座位。由于这些座位在骨架中互不相邻，所以可以按任意顺序选择，贡献因子为 \(m!\)。
第二阶段中，每个长度为 \(1\) 的边界空隙贡献一个唯一的一邻座选择；每个长度为 \(2\) 的内部空隙贡献恰好一个一邻座选择，并附带一个“先填左边还是先填右边”的二选一。因此第二阶段一共有 \(s+g_2\) 个事件，它们可以任意交错，而每个长度为 \(2\) 的内部空隙额外提供一个因子 \(2\)：
$$N_1 = (s+g_2)! \, 2^{g_2}.$$
第二阶段结束后，每个内部空隙都只剩下一个夹在两个已占座位之间的空位，所以第三阶段有 \(m-1\) 个互不影响的二邻座选择，其顺序任意：
$$N_2 = (m-1)!.$$
于是，一个可行三元组 \((m,s,g_2)\) 的总贡献就是
$$w_s \binom{m-1}{g_2} m! (m-1)! (s+g_2)! 2^{g_2}.$$
对所有 \(m\) 以及所有 \(s \in \{0,1,2\}\) 求和，得到
$$\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),}$$
其中不满足 \(0 \le g_2 \le m-1\) 的项直接跳过。以 \(n=4\) 为例，只有 \((2,0,1)\) 和 \((2,1,0)\) 两个可行三元组。它们的贡献分别为 \(4\) 与 \(4\)，因此
$$T(4)=8,$$
与 C++ 文件中的暴力校验结果完全一致。
C++、Python 和 Java 三个版本实现的是同一个求和公式。它们先在模 \(P=100000007\) 下预处理阶乘、逆阶乘以及 \(2\) 的幂。由于 \(P\) 是素数，逆阶乘表通过费马小定理构造，起点是 \((n+1)!^{P-2} \bmod P\)。数组 boundary_sum = [0, 1, 2] 与 boundary_mult = [1, 2, 1] 分别编码 \(s\) 和 \(w_s\) 的三个可能取值。主循环枚举 \(m\)，计算 \(g_2\)，跳过非法情况，用阶乘表求出 \(\binom{m-1}{g_2}\)，再把对应项累加到答案中。C++ 版本为了安全处理中间乘法使用了 __int128；Python 和 Java 遵循完全相同的算术结构。
源码中的检查点为 \(T(4)=8\)、\(T(10)=61632\)，以及 \(T(1000)\equiv 47255094 \pmod{100000007}\)。
阶乘表、逆阶乘表和幂表的预处理都需要 \(O(n)\) 时间和 \(O(n)\) 空间。主求和对每个 \(m\) 只检查 \(3\) 个边界状态，因此总时间复杂度为 \(O(n)\)，空间复杂度同样为 \(O(n)\)。
Есть ряд из \(n\) мест, и люди садятся по одному. На каждом шаге разрешены только те пустые места, у которых число занятых соседей минимально. Обозначим через \(T(n)\) количество всех полных допустимых порядков посадки. Программа должна вычислить \(T(10^6) \bmod 100000007\). Полный перебор состояний растет экспоненциально, поэтому решение считает не сами траектории, а конфигурацию промежутков, которая возникает сразу после того, как сделан последний ход с нулем занятых соседей.
У пустого места число занятых соседей может быть только \(0\), \(1\) или \(2\). Так как всегда выбирается минимум, любой корректный порядок автоматически делится на три последовательные фазы: сначала все ходы с \(0\) занятых соседей, затем все ходы с \(1\) занятым соседом и только потом ходы с \(2\) занятыми соседями. Пока есть хотя бы один ход более ранней фазы, ход более поздней фазы невозможен.
Остановим процесс в тот момент, когда мест с \(0\) занятых соседей больше нет. Тогда все занятые места являются изолированными одиночками; пусть их число равно \(m\). Между соседними одиночками расположено \(m-1\) внутренних промежутков. Каждый внутренний промежуток имеет длину \(1\) или \(2\), потому что при большей длине внутри еще оставалось бы место с нулем занятых соседей. На левом и правом краях промежутки могут иметь только длину \(0\) или \(1\).
Обозначим через \(g_2\) число внутренних промежутков длины \(2\). Пусть длины левого и правого краевых промежутков равны \(\ell,r \in \{0,1\}\), а
$$s=\ell+r \in \{0,1,2\}.$$
Подсчет занятых мест, внутренних промежутков и краев дает формулу
$$n = m + \bigl((m-1-g_2)\cdot 1 + g_2\cdot 2\bigr) + s = 2m - 1 + s + g_2.$$
Значит, при фиксированных \(m\) и \(s\) величина \(g_2\) однозначно определяется:
$$g_2 = n - (2m - 1 + s), \qquad 0 \le g_2 \le m - 1.$$
Значение \(s\) не определяет пару краевых промежутков однозначно. Для \(s=0\) существует \(1\) вариант, для \(s=1\) существуют \(2\) варианта, для \(s=2\) снова \(1\) вариант. Поэтому
$$w_0=1,\qquad w_1=2,\qquad w_2=1.$$
После выбора краевого типа нужно определить, какие именно \(g_2\) из \(m-1\) внутренних промежутков имеют длину \(2\). Число возможных скелетов равно
$$N_{\mathrm{shape}} = w_s \binom{m-1}{g_2}.$$
Первая фаза состоит из \(m\) изолированных одиночек. Поскольку в скелете они попарно не соседствуют, их можно выбирать в любом порядке; это дает множитель \(m!\).
Во второй фазе каждый краевой промежуток длины \(1\) дает один вынужденный ход с одним занятым соседом. Каждый внутренний промежуток длины \(2\) дает ровно один ход типа \(1\) и дополнительно выбор: сначала заполнить левую или правую сторону. Поэтому во второй фазе имеется \(s+g_2\) событий, их можно перемешивать произвольно, а каждый длинный внутренний промежуток дает множитель \(2\):
$$N_1 = (s+g_2)! \, 2^{g_2}.$$
После второй фазы в каждом внутреннем промежутке остается ровно одно пустое место между двумя занятыми. Значит, третья фаза содержит \(m-1\) независимых ходов с двумя занятыми соседями, и их порядок произволен:
$$N_2 = (m-1)!.$$
Итак, вклад одного допустимого тройного параметра \((m,s,g_2)\) равен
$$w_s \binom{m-1}{g_2} m! (m-1)! (s+g_2)! 2^{g_2}.$$
Суммируя по всем \(m\) и по всем \(s \in \{0,1,2\}\), получаем
$$\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),}$$
где случаи с \(g_2\lt 0\) или \(g_2>m-1\) отбрасываются. Для \(n=4\) допустимы только \((2,0,1)\) и \((2,1,0)\). Их вклады равны \(4\) и \(4\), следовательно
$$T(4)=8,$$
что совпадает с переборной проверкой из файла C++.
Во всех трех реализациях на C++, Python и Java вычисляется именно эта сумма. Сначала предвычисляются факториалы, обратные факториалы и степени двойки по модулю \(P=100000007\). Поскольку \(P\) является простым, таблица обратных факториалов строится по малой теореме Ферма, начиная с \((n+1)!^{P-2} \bmod P\). Массивы boundary_sum = [0, 1, 2] и boundary_mult = [1, 2, 1] кодируют возможные значения \(s\) и \(w_s\). Для каждого \(m\) программа вычисляет \(g_2\), пропускает невозможные случаи, находит \(\binom{m-1}{g_2}\) через факториальные таблицы и прибавляет нужный член. В версии C++ для безопасных промежуточных произведений используется __int128; версии на Python и Java повторяют ту же арифметическую формулу.
Контрольные значения в исходном коде: \(T(4)=8\), \(T(10)=61632\) и \(T(1000)\equiv 47255094 \pmod{100000007}\).
Предвычисление таблиц факториалов, обратных факториалов и степеней требует \(O(n)\) времени и \(O(n)\) памяти. Основная сумма перебирает \(n\) значений \(m\) и только три граничных состояния для каждого. Поэтому общая сложность равна \(O(n)\), а память также составляет \(O(n)\).
لدينا صف من \(n\) مقاعد، ويجلس الأشخاص واحدًا بعد الآخر. في كل خطوة لا يُسمح إلا بالمقاعد الفارغة التي تملك أقل عدد ممكن من الجيران المشغولين. إذا رمزنا بعدد ترتيبات الجلوس الكاملة بـ \(T(n)\)، فالمطلوب أن يحسب البرنامج \(T(10^6) \bmod 100000007\). البحث المباشر في شجرة الحالات يتضخم أسيًا، لذلك يعتمد الحل على عدّ بنية الفجوات التي تظهر مباشرة بعد آخر اختيار لمقعد له صفر من الجيران المشغولين.
عدد الجيران المشغولين لأي مقعد فارغ لا يمكن أن يكون إلا \(0\) أو \(1\) أو \(2\). وبما أن القاعدة تختار دائمًا الحد الأدنى، فإن أي ترتيب صالح ينقسم تلقائيًا إلى ثلاث مراحل متتالية: أولًا جميع الاختيارات ذات \(0\) جيران مشغولين، ثم جميع الاختيارات ذات \(1\) جار مشغول، ثم أخيرًا الاختيارات ذات \(2\) جارين مشغولين. لا يمكن حدوث خطوة من مرحلة متأخرة ما دامت هناك خطوة متاحة من مرحلة أسبق.
لنوقف العملية عند اللحظة التي لا يبقى فيها أي مقعد فارغ له \(0\) جيران مشغولين. عندئذ تكون جميع المقاعد المشغولة مقاعد منفردة غير متجاورة، ولنسَمِّ عددها \(m\). بين كل مقعدين منفردين متتاليين توجد \(m-1\) فجوات داخلية. طول كل فجوة داخلية لا بد أن يكون \(1\) أو \(2\)، لأن فجوة أطول من ذلك ستحتوي ما يزال على مقعد ذي صفر من الجيران المشغولين. أما فجوتا الطرفين فلا يمكن أن يزيد طولهما على \(1\).
لنرمز بعدد الفجوات الداخلية ذات الطول \(2\) بـ \(g_2\). وإذا كانت فجوتا اليسار واليمين هما \(\ell,r \in \{0,1\}\)، فنعرّف
$$s=\ell+r \in \{0,1,2\}.$$
بعد عدّ المقاعد المشغولة والفجوات الداخلية وفجوتي الطرفين نحصل على
$$n = m + \bigl((m-1-g_2)\cdot 1 + g_2\cdot 2\bigr) + s = 2m - 1 + s + g_2.$$
وهكذا، إذا ثبتت \(m\) و\(s\)، فإن قيمة \(g_2\) تصبح محددة بالكامل:
$$g_2 = n - (2m - 1 + s), \qquad 0 \le g_2 \le m - 1.$$
القيمة \(s\) لا تحدد فجوتي الطرفين تحديدًا وحيدًا. توجد حالة واحدة عندما \(s=0\)، وحالتان عندما \(s=1\)، وحالة واحدة عندما \(s=2\). لذلك
$$w_0=1,\qquad w_1=2,\qquad w_2=1.$$
بعد اختيار نوع الطرفين، نختار أي \(g_2\) من الفجوات الداخلية وعددها \(m-1\) ستكون بطول \(2\). ومن ثم يكون عدد الأشكال الممكنة هو
$$N_{\mathrm{shape}} = w_s \binom{m-1}{g_2}.$$
في المرحلة الأولى توجد \(m\) مقاعد منفردة معزولة. وبما أنها غير متجاورة في الهيكل، فيمكن اختيارها بأي ترتيب، وهذا يعطي العامل \(m!\).
في المرحلة الثانية، كل فجوة طرفية بطول \(1\) تعطي اختيارًا وحيدًا لمقعد له جار مشغول واحد. وكل فجوة داخلية بطول \(2\) تعطي بالضبط اختيارًا واحدًا من نوع الجار الواحد، مع قرار إضافي: هل نملأ الجهة اليسرى أولًا أم اليمنى. لذلك يوجد في المرحلة الثانية \(s+g_2\) أحداث، ويمكن ترتيبها بأي تداخل، كما أن كل فجوة داخلية طويلة تعطي عامل \(2\):
$$N_1 = (s+g_2)! \, 2^{g_2}.$$
بعد انتهاء المرحلة الثانية، تترك كل فجوة داخلية مقعدًا فارغًا واحدًا بين مقعدين مشغولين. إذًا تحتوي المرحلة الثالثة على \(m-1\) اختيارات مستقلة من نوع الجارين المشغولين، وترتيبها حر:
$$N_2 = (m-1)!.$$
وبالتالي فإن مساهمة الثلاثي الممكن \((m,s,g_2)\) هي
$$w_s \binom{m-1}{g_2} m! (m-1)! (s+g_2)! 2^{g_2}.$$
بجمع جميع قيم \(m\) وجميع قيم \(s \in \{0,1,2\}\) نحصل على
$$\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),}$$
مع تجاهل كل حالة لا تحقق \(0 \le g_2 \le m-1\). عندما \(n=4\)، لا يوجد إلا الحالتان \((2,0,1)\) و\((2,1,0)\). مساهمة كل منهما هي \(4\)، ولذلك
$$T(4)=8,$$
وهو تمامًا مقدار التحقق بالقوة الغاشمة الموجود في ملف C++.
تطبق ملفات C++ وPython وJava هذه الصيغة نفسها حرفيًا. يجري أولًا حساب المضروبات، والمضروبات العكسية، وقوى العدد \(2\) بترديد \(P=100000007\). وبما أن \(P\) عدد أولي، فإن جدول المضروبات العكسية يُبنى باستخدام مبرهنة فيرما الصغرى بدءًا من \((n+1)!^{P-2} \bmod P\). المصفوفتان boundary_sum = [0, 1, 2] وboundary_mult = [1, 2, 1] تمثلان القيم الممكنة لـ \(s\) و\(w_s\). بعد ذلك تمر الشفرة على جميع قيم \(m\)، وتحسب \(g_2\)، وتتجاوز الحالات غير الممكنة، وتحسب \(\binom{m-1}{g_2}\) عبر جداول المضروبات، ثم تجمع الحد الموافق. نسخة C++ تستخدم __int128 لحماية الضربات الوسيطة من الفيض؛ أما Python وJava فتستخدمان الصيغة الحسابية نفسها.
قيم التحقق الموجودة في المصدر هي \(T(4)=8\)، و\(T(10)=61632\)، و\(T(1000)\equiv 47255094 \pmod{100000007}\).
بناء جداول المضروبات والمضروبات العكسية والقوى يحتاج إلى \(O(n)\) زمنًا و\(O(n)\) ذاكرة. أما المجموع الرئيسي فيفحص \(n\) قيمة لـ \(m\)، ولكل قيمة ثلاث حالات حدية فقط. لذلك يكون الزمن الكلي \(O(n)\)، وتبقى الذاكرة أيضًا \(O(n)\).