We have \(n\) ordered stacks, each containing exactly two coins colored gold or silver. Gary may remove only gold coins, Sally may remove only silver coins, and removing a coin also removes every coin above it in the same stack. An arrangement is called fair if the first player loses regardless of whether Gary or Sally is the one who starts. The goal is to compute \(F(n)\), the number of fair arrangements, for \(n=9898\) modulo \(989898989\).
The key simplification is that each height-2 stack has a small numerical game value. Since the full position is the disjunctive sum of the \(n\) stacks, counting fair arrangements becomes a coefficient-extraction problem for those local values.
Let \(0\) denote the empty stack. A single gold coin has value \(\{0 \mid\}=1\), because Gary can move to \(0\) while Sally has no move. Similarly, a single silver coin has value \(\{\mid 0\}=-1\).
Now consider a stack of height \(2\), written from bottom to top:
$$\begin{aligned} GG&=\{0,1 \mid\}=2,\\ GS&=\{0 \mid 1\}=\frac{1}{2},\\ SG&=\{-1 \mid 0\}=-\frac{1}{2},\\ SS&=\{\mid -1,0\}=-2. \end{aligned}$$
The implementations do not work with fractions. Multiplying every local value by \(2\) clears the denominators and does not change which total sums are zero, so the four stack types become the integer step set
$$\{4,1,-1,-4\}.$$
The whole arrangement is the sum of the \(n\) local games. Because all four local games are numbers, their disjunctive sum is just ordinary addition. Therefore an arrangement is fair exactly when the sum of the scaled local values is \(0\).
If the stacks contribute scaled values \(a_1,\dots,a_n\in\{4,1,-1,-4\}\), then the fairness condition is simply
$$a_1+\cdots+a_n=0.$$
So \(F(n)\) is the number of ordered length-\(n\) sequences over \(\{4,1,-1,-4\}\) whose total is zero.
Introduce the Laurent polynomial
$$P(x)=x^4+x+x^{-1}+x^{-4}.$$
Choosing one stack means choosing one monomial from \(P(x)\). After \(n\) stacks, the exponent records the scaled total, so the number of fair arrangements is the constant term
$$F(n)=[x^0]P(x)^n.$$
If one prefers ordinary polynomials only, multiply by \(x^{4n}\) and rewrite this as
$$F(n)=[x^{4n}](1+x^3+x^5+x^8)^n.$$
The two forms are equivalent; the implementation follows the centered constant-term viewpoint.
Let \(D_k(s)\) be the number of length-\(k\) stack sequences whose scaled total is \(s\). Then
$$D_0(0)=1,$$
$$D_0(s)=0 \quad \text{for } s\ne 0,$$
and each new stack contributes one of the four steps, giving
$$D_{k+1}(s)=D_k(s-4)+D_k(s-1)+D_k(s+1)+D_k(s+4).$$
The answer is therefore
$$F(n)=D_n(0)\pmod{989898989}.$$
After \(k\) stacks the total must lie in \([-4k,4k]\), so the reachable state space grows only linearly with \(k\).
With two stacks, we need ordered pairs from \(\{4,1,-1,-4\}\) whose sum is zero. The only possibilities are
$$ (4,-4),\quad (-4,4),\quad (1,-1),\quad (-1,1). $$
Hence
$$F(2)=4.$$
This is the first useful checkpoint for the recurrence, and a larger checkpoint is \(F(10)=63594\).
The C++, Python, and Java implementations all use the same rolling dynamic program. They allocate two arrays large enough to hold every reachable total together with a small safety margin for the \(\pm 4\) transitions. A fixed center index represents total \(0\), negative totals sit to the left, and positive totals sit to the right.
The current layer starts with only the center entry equal to \(1\). For each of the \(n\) stacks, the implementation clears the next layer, restricts the loop to the currently reachable interval \([-4k,4k]\), and fills each state by summing the four predecessor states corresponding to the four possible stack types. Every update is reduced modulo \(989898989\), then the two layers are swapped. After the last stack, the center entry is exactly \(F(n)\).
At step \(k\), there are \(8k+1\) reachable totals. Therefore the total number of state updates is
$$\sum_{k=1}^{n}(8k+1)=4n(n+1)+n=O(n^2).$$
Only two layers are stored, each of size \(O(n)\), so the memory usage is \(O(n)\).
Es gibt \(n\) geordnete Stapel mit jeweils genau zwei Münzen, die gold oder silbern sein können. Gary darf nur goldene Münzen entfernen, Sally nur silberne, und wenn eine Münze entfernt wird, verschwinden auch alle Münzen darüber aus demselben Stapel. Eine Anordnung heißt fair, wenn der Startspieler verliert, unabhängig davon, ob Gary oder Sally beginnt. Gesucht ist also \(F(n)\), die Anzahl fairer Anordnungen für \(n=9898\), modulo \(989898989\).
Die entscheidende Vereinfachung ist, dass jeder Stapel der Höhe \(2\) einen kleinen numerischen Spielwert besitzt. Da die Gesamtstellung die disjunktive Summe dieser \(n\) Einzelspiele ist, wird das Zählen fairer Anordnungen zu einem Problem der Koeffizientenextraktion.
Sei \(0\) der leere Stapel. Eine einzelne Goldmünze hat den Wert \(\{0 \mid\}=1\), weil Gary nach \(0\) ziehen kann und Sally keinen Zug hat. Entsprechend hat eine einzelne Silbermünze den Wert \(\{\mid 0\}=-1\).
Nun betrachten wir alle Stapel der Höhe \(2\), von unten nach oben geschrieben:
$$\begin{aligned} GG&=\{0,1 \mid\}=2,\\ GS&=\{0 \mid 1\}=\frac{1}{2},\\ SG&=\{-1 \mid 0\}=-\frac{1}{2},\\ SS&=\{\mid -1,0\}=-2. \end{aligned}$$
Die Implementierungen rechnen nicht mit Brüchen. Multipliziert man alle lokalen Werte mit \(2\), verschwinden die Nenner, und die Bedingung „Gesamtsumme gleich null“ bleibt unverändert. Daher arbeiten wir mit der ganzzahligen Schrittmenge
$$\{4,1,-1,-4\}.$$
Die gesamte Anordnung ist die Summe der \(n\) lokalen Spiele. Weil alle vier lokalen Spiele Zahlen sind, ist ihre disjunktive Summe einfach gewöhnliche Addition. Deshalb ist eine Anordnung genau dann fair, wenn die Summe der skalierten lokalen Werte \(0\) ergibt.
Tragen die Stapel die skalierten Werte \(a_1,\dots,a_n\in\{4,1,-1,-4\}\), so lautet die Bedingung
$$a_1+\cdots+a_n=0.$$
Also zählt \(F(n)\) die geordneten Folgen der Länge \(n\) über \(\{4,1,-1,-4\}\), deren Summe null ist.
Wir definieren das Laurent-Polynom
$$P(x)=x^4+x+x^{-1}+x^{-4}.$$
Die Wahl eines Stapels entspricht der Wahl eines Monoms aus \(P(x)\). Nach \(n\) Stapeln codiert der Exponent die skalierte Gesamtsumme. Damit ist die Anzahl fairer Anordnungen gerade der konstante Term
$$F(n)=[x^0]P(x)^n.$$
Wer lieber nur gewöhnliche Polynome verwendet, kann mit \(x^{4n}\) multiplizieren und erhält äquivalent
$$F(n)=[x^{4n}](1+x^3+x^5+x^8)^n.$$
Die Implementierung benutzt die zentrierte Sicht auf den konstanten Term.
Sei \(D_k(s)\) die Anzahl der Folgen aus \(k\) Stapeln mit skalierter Summe \(s\). Dann gilt
$$D_0(0)=1,$$
$$D_0(s)=0 \quad \text{für } s\ne 0,$$
und jeder neue Stapel fügt einen der vier Schritte hinzu. Also
$$D_{k+1}(s)=D_k(s-4)+D_k(s-1)+D_k(s+1)+D_k(s+4).$$
Gesucht ist damit
$$F(n)=D_n(0)\pmod{989898989}.$$
Nach \(k\) Stapeln kann die Gesamtsumme nur im Intervall \([-4k,4k]\) liegen. Der Zustandsraum wächst also nur linear mit \(k\).
Für zwei Stapel brauchen wir geordnete Paare aus \(\{4,1,-1,-4\}\), deren Summe null ist. Die einzigen Möglichkeiten sind
$$ (4,-4),\quad (-4,4),\quad (1,-1),\quad (-1,1). $$
Daher gilt
$$F(2)=4.$$
Das ist der erste sinnvolle Kontrollwert der Rekursion; ein weiterer Kontrollwert ist \(F(10)=63594\).
Die Implementierungen in C++, Python und Java verwenden alle dieselbe rollierende dynamische Programmierung. Sie reservieren zwei Felder, die alle erreichbaren Summen sowie einen kleinen Sicherheitsrand für die \(\pm 4\)-Übergänge aufnehmen. Ein fester Mittelpunkt steht für die Summe \(0\), negative Summen liegen links davon, positive rechts.
Zu Beginn ist nur der Mittelpunkt mit \(1\) belegt. Für jeden der \(n\) Stapel wird die nächste Ebene geleert, dann wird nur über das aktuell erreichbare Intervall \([-4k,4k]\) iteriert. Jeder Zustand erhält Beiträge aus genau vier Vorgängerzuständen, entsprechend den vier möglichen Stapeltypen. Nach jeder Addition wird modulo \(989898989\) reduziert, anschließend werden die beiden Ebenen vertauscht. Nach dem letzten Stapel ist der Mittelpunkt genau \(F(n)\).
Im Schritt \(k\) gibt es \(8k+1\) erreichbare Summen. Die Gesamtzahl der Zustandsaktualisierungen ist also
$$\sum_{k=1}^{n}(8k+1)=4n(n+1)+n=O(n^2).$$
Gespeichert werden nur zwei Ebenen der Größe \(O(n)\), also beträgt der Speicherverbrauch \(O(n)\).
Her biri tam iki madeni paradan oluşan, sıralı \(n\) yığın vardır. Gary yalnızca altın paraları, Sally yalnızca gümüş paraları kaldırabilir; seçilen parayla birlikte aynı yığındaki üstündeki tüm paralar da oyundan çıkar. Bir dizilim, ilk oyuncu kim olursa olsun kaybediyorsa fair kabul edilir. Amaç, \(n=9898\) için fair dizilim sayısı olan \(F(n)\)'yi \(989898989\) modunda hesaplamaktır.
Asıl kolaylaştırıcı nokta şudur: Yüksekliği \(2\) olan her yığın küçük bir sayısal oyun değeri taşır. Tüm düzen, bu \(n\) yerel oyunun ayrık toplamı olduğundan, fair dizilimleri sayma işi katsayı çıkarımına dönüşür.
Boş yığını \(0\) ile gösterelim. Tek bir altın para \(\{0 \mid\}=1\) değerine sahiptir; çünkü Gary \(0\)'a hamle yapabilir, Sally'nin ise hamlesi yoktur. Benzer biçimde tek bir gümüş para \(\{\mid 0\}=-1\) değerine sahiptir.
Şimdi aşağıdan yukarıya yazılmış yükseklik \(2\) yığınlarını inceleyelim:
$$\begin{aligned} GG&=\{0,1 \mid\}=2,\\ GS&=\{0 \mid 1\}=\frac{1}{2},\\ SG&=\{-1 \mid 0\}=-\frac{1}{2},\\ SS&=\{\mid -1,0\}=-2. \end{aligned}$$
Uygulamalar kesirlerle çalışmaz. Tüm yerel değerleri \(2\) ile çarpmak paydaları temizler ve “toplam değer sıfır mı?” sorusunu değiştirmez. Böylece dört yığın tipi şu tam sayı adımlarına dönüşür:
$$\{4,1,-1,-4\}.$$
Tüm dizilim, \(n\) yerel oyunun toplamıdır. Bu dört yerel oyunun her biri sayı olduğundan, ayrık toplam sıradan toplama ile aynıdır. Bu yüzden bir dizilim ancak ve ancak ölçeklenmiş yerel değerlerin toplamı \(0\) ise fair olur.
Yığınların katkıları \(a_1,\dots,a_n\in\{4,1,-1,-4\}\) ise koşul
$$a_1+\cdots+a_n=0$$
şeklindedir. Dolayısıyla \(F(n)\), \(\{4,1,-1,-4\}\) kümesinden seçilen ve toplamı sıfır olan sıralı uzunluk-\(n\) dizilerin sayısıdır.
Şu Laurent polinomunu tanımlayalım:
$$P(x)=x^4+x+x^{-1}+x^{-4}.$$
Bir yığın seçmek, \(P(x)\) içinden bir terim seçmek demektir. \(n\) yığından sonra üs, ölçeklenmiş toplamı kaydeder. Bu nedenle fair dizilim sayısı tam olarak sabit terimdir:
$$F(n)=[x^0]P(x)^n.$$
Yalnızca sıradan polinomlarla çalışmak istersek \(x^{4n}\) ile çarpar ve eşdeğer biçimde
$$F(n)=[x^{4n}](1+x^3+x^5+x^8)^n$$
yazarız. Uygulama ise merkezlenmiş sabit-terim bakışını izler.
\(D_k(s)\), ölçeklenmiş toplamı \(s\) olan uzunluk-\(k\) yığın dizilerinin sayısı olsun. O halde
$$D_0(0)=1,$$
$$D_0(s)=0 \quad \text{\(s\ne 0\) için},$$
ve her yeni yığın dört adımdan birini eklediği için
$$D_{k+1}(s)=D_k(s-4)+D_k(s-1)+D_k(s+1)+D_k(s+4).$$
Aranan cevap
$$F(n)=D_n(0)\pmod{989898989}$$
olur. \(k\) yığından sonra toplam ancak \([-4k,4k]\) aralığında olabilir; yani durum uzayı \(k\) ile doğrusal büyür.
İki yığın için, \(\{4,1,-1,-4\}\) kümesinden toplamı sıfır olan sıralı çiftleri ararız. Tek olasılıklar şunlardır:
$$ (4,-4),\quad (-4,4),\quad (1,-1),\quad (-1,1). $$
Bu yüzden
$$F(2)=4.$$
Bu, özyineleme için ilk anlamlı kontrol değeridir; daha büyük bir kontrol de \(F(10)=63594\) değeridir.
C++, Python ve Java uygulamaları aynı dönen dinamik programlama yapısını kullanır. Ulaşılabilir tüm toplamları ve \(\pm 4\) geçişleri için küçük bir güvenlik payını tutacak kadar büyük iki dizi ayrılır. Sabit bir merkez indis toplam \(0\)'ı temsil eder; negatif toplamlar solda, pozitif toplamlar sağdadır.
Başlangıçta yalnızca merkez hücre \(1\)'dir. \(n\) yığının her biri için sonraki katman sıfırlanır, döngü yalnızca o anda erişilebilir olan \([-4k,4k]\) aralığında çalıştırılır ve her durum dört olası yığın tipine karşılık gelen dört öncül durumun toplamı olarak doldurulur. Her toplama adımında \(989898989\) moduna göre indirgeme yapılır, sonra iki katman yer değiştirir. Son yığın işlendiğinde merkez hücre tam olarak \(F(n)\) olur.
\(k\). adımda \(8k+1\) adet erişilebilir toplam vardır. Dolayısıyla toplam durum güncelleme sayısı
$$\sum_{k=1}^{n}(8k+1)=4n(n+1)+n=O(n^2)$$
olur. Yalnızca iki katman saklandığı için bellek kullanımı \(O(n)\)'dir.
Hay \(n\) pilas ordenadas, cada una con exactamente dos monedas, coloreadas en oro o plata. Gary solo puede retirar monedas de oro, Sally solo puede retirar monedas de plata, y al retirar una moneda también desaparecen todas las que están por encima dentro de la misma pila. Una disposición se llama fair si el jugador que mueve primero pierde tanto si empieza Gary como si empieza Sally. Se pide calcular \(F(n)\), el número de disposiciones fair, para \(n=9898\) módulo \(989898989\).
La simplificación decisiva es que cada pila de altura \(2\) tiene un pequeño valor numérico de juego. Como la posición total es la suma disyunta de esas \(n\) pilas, contar disposiciones fair se convierte en un problema de extracción de coeficientes.
Sea \(0\) la pila vacía. Una sola moneda de oro tiene valor \(\{0 \mid\}=1\), porque Gary puede mover a \(0\) y Sally no tiene movimiento. De forma análoga, una sola moneda de plata tiene valor \(\{\mid 0\}=-1\).
Ahora estudiamos las cuatro pilas de altura \(2\), escritas de abajo arriba:
$$\begin{aligned} GG&=\{0,1 \mid\}=2,\\ GS&=\{0 \mid 1\}=\frac{1}{2},\\ SG&=\{-1 \mid 0\}=-\frac{1}{2},\\ SS&=\{\mid -1,0\}=-2. \end{aligned}$$
Las implementaciones no trabajan con fracciones. Si multiplicamos todos los valores locales por \(2\), desaparecen los denominadores y no cambia la condición de que la suma total sea cero. Por eso usamos el conjunto de pasos enteros
$$\{4,1,-1,-4\}.$$
La disposición completa es la suma de los \(n\) juegos locales. Como los cuatro juegos locales son números, su suma disyunta coincide con la suma aritmética ordinaria. Por tanto, una disposición es fair exactamente cuando la suma de los valores locales escalados es \(0\).
Si las pilas aportan \(a_1,\dots,a_n\in\{4,1,-1,-4\}\), la condición es
$$a_1+\cdots+a_n=0.$$
Así, \(F(n)\) cuenta las secuencias ordenadas de longitud \(n\) sobre \(\{4,1,-1,-4\}\) cuya suma total es cero.
Introducimos el polinomio de Laurent
$$P(x)=x^4+x+x^{-1}+x^{-4}.$$
Elegir una pila equivale a elegir un monomio de \(P(x)\). Después de \(n\) pilas, el exponente registra la suma escalada, de modo que el número de disposiciones fair es el término constante
$$F(n)=[x^0]P(x)^n.$$
Si se prefieren polinomios ordinarios, basta multiplicar por \(x^{4n}\) y escribir de forma equivalente
$$F(n)=[x^{4n}](1+x^3+x^5+x^8)^n.$$
La implementación sigue la interpretación centrada en el término constante.
Sea \(D_k(s)\) el número de secuencias de \(k\) pilas cuya suma escalada es \(s\). Entonces
$$D_0(0)=1,$$
$$D_0(s)=0 \quad \text{para } s\ne 0,$$
y cada nueva pila añade uno de los cuatro pasos, así que
$$D_{k+1}(s)=D_k(s-4)+D_k(s-1)+D_k(s+1)+D_k(s+4).$$
El valor buscado es
$$F(n)=D_n(0)\pmod{989898989}.$$
Tras \(k\) pilas, la suma total solo puede estar en \([-4k,4k]\), por lo que el espacio de estados crece linealmente con \(k\).
Con dos pilas necesitamos pares ordenados de \(\{4,1,-1,-4\}\) cuya suma sea cero. Las únicas posibilidades son
$$ (4,-4),\quad (-4,4),\quad (1,-1),\quad (-1,1). $$
Por tanto,
$$F(2)=4.$$
Ese es el primer control útil de la recurrencia, y un control mayor es \(F(10)=63594\).
Las implementaciones en C++, Python y Java usan la misma programación dinámica con dos capas rodantes. Reservan dos arreglos lo bastante grandes para contener todas las sumas alcanzables, junto con un pequeño margen de seguridad para las transiciones \(\pm 4\). Un índice central fijo representa la suma \(0\); las sumas negativas quedan a la izquierda y las positivas a la derecha.
Al principio solo la celda central vale \(1\). Para cada una de las \(n\) pilas, la implementación limpia la siguiente capa, recorre solo el intervalo alcanzable \([-4k,4k]\) y rellena cada estado sumando los cuatro estados predecesores asociados a los cuatro tipos de pila posibles. Cada actualización se reduce módulo \(989898989\) y luego se intercambian las dos capas. Tras procesar la última pila, la entrada central es exactamente \(F(n)\).
En el paso \(k\) hay \(8k+1\) sumas alcanzables. Por ello, el número total de actualizaciones es
$$\sum_{k=1}^{n}(8k+1)=4n(n+1)+n=O(n^2).$$
Solo se almacenan dos capas de tamaño \(O(n)\), así que la memoria utilizada es \(O(n)\).
题目给出 \(n\) 个有序栈，每个栈里恰好有两枚硬币，颜色为金或银。Gary 只能移除金币，Sally 只能移除银币；一旦移除某枚硬币，它上方的硬币也会一起被移除。如果无论先手是 Gary 还是 Sally，先行动的一方都会输，那么这个排列就称为 fair。目标是计算 \(n=9898\) 时 fair 排列的数量 \(F(n)\)，并对 \(989898989\) 取模。
真正把问题降下来的一步是：每一个两层栈都可以看成一个很小的数值型博弈。整个局面就是这 \(n\) 个局面的离散和，因此“统计 fair 排列”最终会变成一个关于系数提取的问题。
记空栈的值为 \(0\)。单独一枚金币的博弈值是 \(\{0 \mid\}=1\)，因为 Gary 可以一步走到 \(0\)，而 Sally 没有合法行动。同理，单独一枚银币的值是 \(\{\mid 0\}=-1\)。
现在把两层栈按照“从下到上”的顺序写出来，可以得到四种情况：
$$\begin{aligned} GG&=\{0,1 \mid\}=2,\\ GS&=\{0 \mid 1\}=\frac{1}{2},\\ SG&=\{-1 \mid 0\}=-\frac{1}{2},\\ SS&=\{\mid -1,0\}=-2. \end{aligned}$$
实现里并不直接处理分数。把所有局部数值统一乘以 \(2\) 之后，分母被清掉，而“总和是否等于 \(0\)”这一判定不会改变。所以四种两层栈可以统一编码成整数步长
$$\{4,1,-1,-4\}.$$
整个排列的值是这 \(n\) 个局部博弈值的和。因为上面四个局部局面全都是“数”，它们的离散和就等同于普通加法。因此，一个排列是 fair，当且仅当所有局部缩放值加起来恰好为 \(0\)。
如果第 \(i\) 个栈贡献的缩放值记为 \(a_i\)，其中
$$a_i\in\{4,1,-1,-4\},$$
那么 fair 条件就是
$$a_1+\cdots+a_n=0.$$
于是 \(F(n)\) 等价于：从 \(\{4,1,-1,-4\}\) 中选出长度为 \(n\) 的有序序列，使得总和为 \(0\) 的方案数。
定义 Laurent 多项式
$$P(x)=x^4+x+x^{-1}+x^{-4}.$$
选择一个栈，就等于从 \(P(x)\) 中选择一个单项式。选完 \(n\) 个栈后，指数正好记录了缩放总和。因此 fair 排列数就是常数项：
$$F(n)=[x^0]P(x)^n.$$
如果更喜欢只写普通多项式，可以整体乘上 \(x^{4n}\)，得到完全等价的形式
$$F(n)=[x^{4n}](1+x^3+x^5+x^8)^n.$$
实现采用的是“把零和放在中心位置”的常数项视角。
令 \(D_k(s)\) 表示长度为 \(k\) 的栈序列中，缩放总和等于 \(s\) 的方案数。初始条件是
$$D_0(0)=1,$$
$$D_0(s)=0 \quad \text{当 } s\ne 0.$$
每加入一个新栈，总和只可能增加 \(4\)、\(1\)、\(-1\) 或 \(-4\)。因此递推式为
$$D_{k+1}(s)=D_k(s-4)+D_k(s-1)+D_k(s+1)+D_k(s+4).$$
最终答案就是
$$F(n)=D_n(0)\pmod{989898989}.$$
加入 \(k\) 个栈之后，总和一定落在 \([-4k,4k]\) 之间，所以状态范围只会随着 \(k\) 线性扩张。
当 \(n=2\) 时，我们要找的是来自 \(\{4,1,-1,-4\}\) 的有序二元组，且它们的和为 \(0\)。唯一可行的四种情况是
$$ (4,-4),\quad (-4,4),\quad (1,-1),\quad (-1,1). $$
因此
$$F(2)=4.$$
这是递推最直接的校验点之一，更大的校验值是 \(F(10)=63594\)。
C++、Python 和 Java 三种实现使用的是同一个滚动动态规划模型。程序分配两个数组，长度足以覆盖所有可达总和，并额外留出一小段缓冲区来处理 \(\pm 4\) 的转移。数组中央的固定位置表示总和 \(0\)，左侧表示负数总和，右侧表示正数总和。
开始时只有中央位置的计数是 \(1\)。随后依次处理 \(n\) 个栈：先把下一层清零，再只遍历当前真正可达的区间 \([-4k,4k]\)，并把每个状态更新为四个前驱状态之和，对应四种可能的栈类型。每次加法之后都立刻对 \(989898989\) 取模，然后交换“当前层”和“下一层”。全部处理结束后，中央位置的值就是 \(F(n)\)。
第 \(k\) 步一共有 \(8k+1\) 个可达总和，因此总状态更新次数为
$$\sum_{k=1}^{n}(8k+1)=4n(n+1)+n=O(n^2).$$
算法只保留两层数组，每层大小都是 \(O(n)\)，所以空间复杂度为 \(O(n)\)。
Дано \(n\) упорядоченных стопок, и в каждой стопке ровно две монеты, золотые или серебряные. Gary может снимать только золотые монеты, Sally только серебряные, причем при снятии монеты удаляются и все монеты выше нее в той же стопке. Расклад называется fair, если первый игрок проигрывает независимо от того, начинает Gary или Sally. Нужно вычислить \(F(n)\), число fair-раскладов, для \(n=9898\) по модулю \(989898989\).
Главное упрощение состоит в том, что каждая стопка высоты \(2\) имеет небольшой числовой игровой вес. Вся позиция является дизъюнктивной суммой этих \(n\) локальных игр, поэтому подсчет fair-раскладов сводится к задаче извлечения коэффициента.
Обозначим пустую стопку через \(0\). Одна золотая монета имеет значение \(\{0 \mid\}=1\), потому что Gary может перейти в \(0\), а у Sally нет хода. Аналогично одна серебряная монета имеет значение \(\{\mid 0\}=-1\).
Теперь рассмотрим все стопки высоты \(2\), записанные снизу вверх:
$$\begin{aligned} GG&=\{0,1 \mid\}=2,\\ GS&=\{0 \mid 1\}=\frac{1}{2},\\ SG&=\{-1 \mid 0\}=-\frac{1}{2},\\ SS&=\{\mid -1,0\}=-2. \end{aligned}$$
Реализация не работает с дробями. Если умножить все локальные значения на \(2\), знаменатели исчезают, а условие «сумма равна нулю» не изменится. Поэтому дальше удобно использовать целочисленный набор шагов
$$\{4,1,-1,-4\}.$$
Весь расклад есть сумма \(n\) локальных игр. Поскольку все четыре локальных значения являются числами, дизъюнктивная сумма здесь совпадает с обычным сложением. Значит, расклад fair тогда и только тогда, когда сумма масштабированных локальных значений равна \(0\).
Если стопки дают вклады \(a_1,\dots,a_n\in\{4,1,-1,-4\}\), то условие имеет вид
$$a_1+\cdots+a_n=0.$$
Тем самым \(F(n)\) равно числу упорядоченных последовательностей длины \(n\) над \(\{4,1,-1,-4\}\) с нулевой суммой.
Введем Laurent-полином
$$P(x)=x^4+x+x^{-1}+x^{-4}.$$
Выбор одной стопки соответствует выбору одного монома из \(P(x)\). После выбора \(n\) стопок показатель степени хранит масштабированную сумму. Поэтому число fair-раскладов равно постоянному члену
$$F(n)=[x^0]P(x)^n.$$
Если хочется обойтись обычными полиномами, можно умножить на \(x^{4n}\) и записать эквивалентно
$$F(n)=[x^{4n}](1+x^3+x^5+x^8)^n.$$
Программа использует именно центрированную интерпретацию постоянного члена.
Пусть \(D_k(s)\) обозначает число последовательностей из \(k\) стопок с масштабированной суммой \(s\). Тогда
$$D_0(0)=1,$$
$$D_0(s)=0 \quad \text{при } s\ne 0,$$
а каждая новая стопка добавляет один из четырех шагов, так что
$$D_{k+1}(s)=D_k(s-4)+D_k(s-1)+D_k(s+1)+D_k(s+4).$$
Искомый ответ равен
$$F(n)=D_n(0)\pmod{989898989}.$$
После \(k\) стопок суммарное значение может лежать только в диапазоне \([-4k,4k]\), поэтому число состояний растет лишь линейно по \(k\).
При \(n=2\) нужны упорядоченные пары из \(\{4,1,-1,-4\}\), сумма которых равна нулю. Возможны только
$$ (4,-4),\quad (-4,4),\quad (1,-1),\quad (-1,1). $$
Следовательно,
$$F(2)=4.$$
Это первая удобная проверка рекуррентной схемы; более крупная проверка дает \(F(10)=63594\).
Реализации на C++, Python и Java используют одну и ту же скользящую динамику по слоям. Выделяются два массива, достаточно длинные, чтобы хранить все достижимые суммы, плюс небольшой запас для переходов на \(\pm 4\). Фиксированный центральный индекс соответствует сумме \(0\), отрицательные суммы расположены левее, положительные правее.
В начале только центральная ячейка равна \(1\). Для каждой из \(n\) стопок следующая слой-таблица обнуляется, затем цикл идет только по реально достижимому диапазону \([-4k,4k]\), а каждое состояние заполняется суммой четырех предшественников, соответствующих четырем возможным типам стопки. После каждого сложения применяется модуль \(989898989\), затем два слоя меняются местами. После обработки последней стопки центральная ячейка и есть \(F(n)\).
На шаге \(k\) существует \(8k+1\) достижимых сумм. Поэтому общее число обновлений состояний равно
$$\sum_{k=1}^{n}(8k+1)=4n(n+1)+n=O(n^2).$$
Хранятся только два слоя размера \(O(n)\), так что потребление памяти равно \(O(n)\).
لدينا \(n\) أكوام مرتبة، وفي كل كومة عملتان بالضبط، إما ذهبيتان أو فضيتان. يستطيع Gary إزالة العملات الذهبية فقط، وتستطيع Sally إزالة العملات الفضية فقط، وعند إزالة عملة تُزال معها كل العملات التي فوقها في الكومة نفسها. يسمى الترتيب fair إذا كان اللاعب الذي يبدأ يخسر سواء بدأ Gary أو بدأت Sally. المطلوب هو حساب \(F(n)\)، أي عدد الترتيبات العادلة، عندما \(n=9898\) مع أخذ الناتج بترديد \(989898989\).
التبسيط الحاسم هنا هو أن كل كومة من طبقتين تمتلك قيمة عددية صغيرة في نظرية الألعاب التوافقية. وبما أن الوضع الكامل هو مجموع منفصل لهذه الألعاب المحلية \(n\) مرة، فإن عدّ الترتيبات العادلة يتحول إلى مسألة استخراج معامل مناسب.
لنرمز إلى الكومة الفارغة بالرمز \(0\). العملة الذهبية المفردة قيمتها \(\{0 \mid\}=1\)، لأن Gary يستطيع الانتقال إلى \(0\) بينما لا تملك Sally أي نقلة. وبالمثل فإن العملة الفضية المفردة قيمتها \(\{\mid 0\}=-1\).
الآن ننظر إلى أكوام الارتفاع \(2\) مكتوبة من الأسفل إلى الأعلى:
$$\begin{aligned} GG&=\{0,1 \mid\}=2,\\ GS&=\{0 \mid 1\}=\frac{1}{2},\\ SG&=\{-1 \mid 0\}=-\frac{1}{2},\\ SS&=\{\mid -1,0\}=-2. \end{aligned}$$
التنفيذات لا تعمل بالكسور مباشرة. إذا ضربنا كل قيمة محلية في \(2\) اختفت المقامات، ولم يتغير شرط أن يكون المجموع الكلي صفراً. لذلك نستبدل الأنماط الأربعة بمجموعة الخطوات الصحيحة
$$\{4,1,-1,-4\}.$$
الوضع الكامل هو مجموع القيم المحلية للأكوام جميعاً. وبما أن القيم الأربع السابقة كلها أعداد، فإن المجموع المنفصل هنا يساوي الجمع العادي. لذلك يكون الترتيب fair إذا وفقط إذا كان مجموع القيم المحلية بعد التحجيم مساوياً للصفر.
إذا كانت مساهمات الأكوام هي \(a_1,\dots,a_n\) حيث
$$a_i\in\{4,1,-1,-4\},$$
فإن شرط العدالة يصبح
$$a_1+\cdots+a_n=0.$$
إذن \(F(n)\) هو عدد السلاسل المرتبة بطول \(n\) المأخوذة من \(\{4,1,-1,-4\}\) والتي يكون مجموعها صفراً.
نعرّف كثير الحدود اللوراني
$$P(x)=x^4+x+x^{-1}+x^{-4}.$$
اختيار كومة واحدة يعادل اختيار حد واحد من \(P(x)\). وبعد اختيار \(n\) أكوام، يسجل الأس مقدار المجموع بعد التحجيم. لذلك فإن عدد الترتيبات العادلة هو المعامل الثابت
$$F(n)=[x^0]P(x)^n.$$
وإذا فضلنا العمل بكثيرات حدود عادية فقط، يمكن ضرب التعبير كله في \(x^{4n}\) لنحصل على الصيغة المكافئة
$$F(n)=[x^{4n}](1+x^3+x^5+x^8)^n.$$
التنفيذ يعتمد على منظور المعامل الثابت مع فهرسة متمركزة حول الصفر.
ليكن \(D_k(s)\) عدد السلاسل المؤلفة من \(k\) أكوام والتي يساوي مجموعها بعد التحجيم القيمة \(s\). عندئذ
$$D_0(0)=1,$$
$$D_0(s)=0 \quad (s\ne 0),$$
ومع إضافة كومة جديدة نحصل على إحدى الخطوات الأربع، ومن ثم
$$D_{k+1}(s)=D_k(s-4)+D_k(s-1)+D_k(s+1)+D_k(s+4).$$
إذن الجواب المطلوب هو
$$F(n)=D_n(0)\pmod{989898989}.$$
بعد معالجة \(k\) أكوام لا يمكن أن يخرج المجموع عن المجال \([-4k,4k]\)، ولذلك ينمو فضاء الحالات خطياً فقط مع \(k\).
عندما \(n=2\)، نبحث عن الأزواج المرتبة المأخوذة من \(\{4,1,-1,-4\}\) والتي يكون مجموعها صفراً. الاحتمالات الوحيدة هي
$$ (4,-4),\quad (-4,4),\quad (1,-1),\quad (-1,1). $$
ومن ثم
$$F(2)=4.$$
وهذه أول قيمة تحقق مفيدة لهذه العلاقة التكرارية، كما أن قيمة تحقق أكبر هي \(F(10)=63594\).
التنفيذات في C++ وPython وJava تستخدم البرمجة الديناميكية نفسها مع مصفوفتين متناوبتين. تُحجز مصفوفتان بطول يكفي لتخزين جميع المجاميع الممكنة مع هامش صغير آمن من أجل انتقالات \(\pm 4\). ويمثل موضع مركزي ثابت المجموع \(0\)، بينما تقع المجاميع السالبة إلى يساره والموجبة إلى يمينه.
في البداية تكون الخانة المركزية فقط مساوية لـ \(1\). ثم لكل واحدة من الأكوام \(n\)، تُصفّر الطبقة التالية، ويجري المرور فقط على المجال الممكن حالياً \([-4k,4k]\)، وتُملأ كل حالة بجمع أربع حالات سابقة تقابل الأنماط الأربعة الممكنة للكومة. وبعد كل جمع يطبَّق الترديد \(989898989\)، ثم تتبادل الطبقتان الأدوار. وبعد معالجة آخر كومة تصبح الخانة المركزية مساوية تماماً لـ \(F(n)\).
في الخطوة \(k\) يوجد \(8k+1\) مجموعاً ممكناً. لذلك فإن العدد الكلي لتحديثات الحالات هو
$$\sum_{k=1}^{n}(8k+1)=4n(n+1)+n=O(n^2).$$
ولا تُخزَّن إلا طبقتان بحجم \(O(n)\)، لذا فإن استهلاك الذاكرة هو \(O(n)\).