Problem 895 asks for the value of \(G(9898)\) in the Gold & Silver Coin Game II, reduced modulo \(M=989898989\). The C++, Python, and Java implementations do not simulate game positions directly. Instead they evaluate an exact closed decomposition of \(G(n)\) consisting of a parity-sensitive kernel, a recurrence-defined coefficient sequence, and a short correction term.
This reformulation is what makes the computation practical. Every ingredient can be generated in a single forward pass, and the only divisions are modular inverses, so the whole calculation stays inside \(\mathbb{Z}/M\mathbb{Z}\).
Let \(u\) denote the modular inverse of \(3\), so \(3u\equiv 1\pmod M\). For \(n\ge 2\), the implementations compute \(G(n)\) from three pieces: a kernel sequence \(K(m)\), a coefficient sequence \(c_i\), and a parity-dependent prefactor \(B(n)\).
The inner term depends only on the argument \(m\) and on its parity. Written in mathematical form, the implemented kernel is
$$K(m)=\begin{cases} 0, & m\le 0,\\ 1, & m=1,\\ 14\cdot 2^{m/2}u+6m-15 \pmod M, & m\ge 2,\ m\text{ even},\\ 20\cdot 2^{(m-1)/2}u+6m-15 \pmod M, & m\ge 3,\ m\text{ odd}. \end{cases}$$
The power of \(2\) grows only with \(\lfloor m/2\rfloor\), while the coefficient in front of it switches from \(14\) to \(20\) when parity changes. That even/odd split is one of the main structural features of the final formula.
The convolution weights form a second-order recurrence:
$$c_0=1,\qquad c_1=10,$$
$$c_i\equiv \left((20i-10)c_{i-1}-(64i-64)c_{i-2}\right)i^{-1}\pmod M \qquad (i\ge 2).$$
The first few values are
$$1,\ 10,\ 118,\ 1540,\ 21286,\ \dots$$
Because \(M\) is prime and every index \(i\) used in the computation satisfies \(1\le i<M\), the inverse \(i^{-1}\) always exists modulo \(M\).
If we define
$$A(x)=\sum_{i\ge 0} c_i x^i,$$
then the recurrence is equivalent to the differential equation
$$\left(1-20x+64x^2\right)A'(x)=\left(10-64x\right)A(x),\qquad A(0)=1.$$
Solving it gives
$$A(x)=\frac{1}{\sqrt{1-20x+64x^2}}=\frac{1}{\sqrt{(1-4x)(1-16x)}}.$$
This viewpoint explains why the recurrence weights naturally appear in a one-dimensional convolution: they are exactly the coefficients of a fixed algebraic generating function.
The remaining term is a small parity-dependent correction:
$$B(n)\equiv \begin{cases} 35\cdot 2^{n/2}u-6n-35u \pmod M, & n\text{ even},\\ 50\cdot 2^{(n-1)/2}u-6n-35u \pmod M, & n\text{ odd}. \end{cases}$$
With that notation, the implemented identity is
$$\boxed{G(n)\equiv B(n)+\sum_{i=0}^{\lfloor (n-1)/2\rfloor} c_i\,K(n-2i)\pmod M.}$$
The shift by \(2\) means the parity of \(n\) is preserved throughout the sum. Even inputs only touch the even branch of the kernel, while odd inputs walk through the odd branch and finally terminate at \(K(1)=1\).
The formula contains divisions by \(3\) and by the recurrence index \(i\). In modular arithmetic these are replaced by multiplicative inverses. Since \(M=989898989\) is prime, every nonzero residue has an inverse, so the computation is exact in the finite field \(\mathbb{Z}/M\mathbb{Z}\); nothing is being approximated numerically.
The recurrence gives
$$c_2=\frac{(20\cdot 2-10)c_1-(64\cdot 2-64)c_0}{2}=\frac{30\cdot 10-64}{2}=118.$$
Because \(n=5\) is odd, the prefactor is
$$B(5)=50\cdot 2^2u-30-35u=165u-30\equiv 25\pmod M.$$
The kernel values needed by the sum are
$$K(5)=20\cdot 2^2u+15=80u+15,\qquad K(3)=20\cdot 2u+3=40u+3,\qquad K(1)=1.$$
Therefore
$$\begin{aligned} G(5)&\equiv B(5)+c_0K(5)+c_1K(3)+c_2K(1) \\ &\equiv 25+(80u+15)+10(40u+3)+118 \\ &\equiv 188+480u \\ &\equiv 188+160 \\ &\equiv 348 \pmod M. \end{aligned}$$
This matches the known checkpoint used by the implementations.
The C++, Python, and Java implementations all follow the same numerical plan. They first compute the inverse of \(3\), evaluate the parity-dependent prefactor \(B(n)\), and determine the limit \(\lfloor (n-1)/2\rfloor\). They then build the coefficient list \(c_0,c_1,\dots,c_{\lfloor (n-1)/2\rfloor}\) iteratively from the recurrence above.
After that, the implementation scans through the same index range once more, evaluates the kernel at \(n-2i\), multiplies by the stored coefficient \(c_i\), and accumulates the answer modulo \(M\). The C++ version obtains inverses with the extended Euclidean algorithm, while the Python and Java versions use fast modular exponentiation under the prime modulus. In every language, the algorithmic structure is identical.
Let \(L=\lfloor (n-1)/2\rfloor\). Building the recurrence coefficients costs \(O(L)\) arithmetic steps, and the final convolution sum costs another \(O(L)\) steps. Because the modulus is fixed for the problem, this is linear time in \(n\). If one counts modular inverse computation explicitly, the running time is \(O(L\log M)\), which is still effectively linear here. The memory usage is \(O(L)\) because the coefficient list is stored for the final pass.
Problem 895 verlangt den Wert \(G(9898)\) im Gold-&-Silver-Coin-Game II modulo \(M=989898989\). Die C++-, Python- und Java-Implementierungen simulieren die Spielzustände nicht direkt. Stattdessen verwenden sie eine exakte geschlossene Zerlegung von \(G(n)\), die aus einem paritätsabhängigen Kern, einer rekursiv erzeugten Koeffizientenfolge und einem kurzen Korrekturterm besteht.
Gerade diese Umformung macht die Berechnung effizient. Alle Bausteine lassen sich in einem einzigen Vorwärtslauf erzeugen, und jede Division wird als modulares Inverses ausgeführt.
Sei \(u\) das modulare Inverse von \(3\), also \(3u\equiv 1\pmod M\). Für \(n\ge 2\) berechnen die Implementierungen \(G(n)\) aus drei Zutaten: einer Kernfolge \(K(m)\), einer Koeffizientenfolge \(c_i\) und einem paritätsabhängigen Vorfaktor \(B(n)\).
Der innere Summand hängt nur vom Argument \(m\) und von dessen Parität ab. In mathematischer Schreibweise lautet der implementierte Kern
$$K(m)=\begin{cases} 0, & m\le 0,\\ 1, & m=1,\\ 14\cdot 2^{m/2}u+6m-15 \pmod M, & m\ge 2,\ m\text{ gerade},\\ 20\cdot 2^{(m-1)/2}u+6m-15 \pmod M, & m\ge 3,\ m\text{ ungerade}. \end{cases}$$
Die Zweierpotenz wächst also nur mit \(\lfloor m/2\rfloor\), während der Vorfaktor je nach Parität zwischen \(14\) und \(20\) wechselt. Diese Aufspaltung in gerade und ungerade Fälle ist ein zentraler Strukturpunkt der Formel.
Die Gewichte der Faltung erfüllen eine Rekursion zweiter Ordnung:
$$c_0=1,\qquad c_1=10,$$
$$c_i\equiv \left((20i-10)c_{i-1}-(64i-64)c_{i-2}\right)i^{-1}\pmod M \qquad (i\ge 2).$$
Die ersten Werte sind
$$1,\ 10,\ 118,\ 1540,\ 21286,\ \dots$$
Da \(M\) prim ist und jeder verwendete Index \(i\) die Bedingung \(1\le i<M\) erfüllt, existiert das Inverse \(i^{-1}\) modulo \(M\) immer.
Definieren wir
$$A(x)=\sum_{i\ge 0} c_i x^i,$$
dann ist die Rekursion äquivalent zur Differentialgleichung
$$\left(1-20x+64x^2\right)A'(x)=\left(10-64x\right)A(x),\qquad A(0)=1.$$
Ihre Lösung ist
$$A(x)=\frac{1}{\sqrt{1-20x+64x^2}}=\frac{1}{\sqrt{(1-4x)(1-16x)}}.$$
Damit wird sichtbar, warum die Rekursionswerte als eindimensionale Faltung auftreten: Sie sind genau die Koeffizienten einer festen algebraischen erzeugenden Funktion.
Der verbleibende Korrekturterm ist klein und wieder paritätsabhängig:
$$B(n)\equiv \begin{cases} 35\cdot 2^{n/2}u-6n-35u \pmod M, & n\text{ gerade},\\ 50\cdot 2^{(n-1)/2}u-6n-35u \pmod M, & n\text{ ungerade}. \end{cases}$$
Damit gilt die implementierte Identität
$$\boxed{G(n)\equiv B(n)+\sum_{i=0}^{\lfloor (n-1)/2\rfloor} c_i\,K(n-2i)\pmod M.}$$
Die Verschiebung um \(2\) sorgt dafür, dass die Parität von \(n\) in der gesamten Summe erhalten bleibt. Gerade \(n\) benutzen nur den geraden Zweig des Kerns, ungerade \(n\) nur den ungeraden Zweig und enden bei \(K(1)=1\).
In der Formel wird durch \(3\) und durch den Rekursionsindex \(i\) dividiert. Im modularen Rechnen bedeutet das Multiplikation mit dem jeweiligen Inversen. Weil \(M=989898989\) prim ist, besitzt jede von \(0\) verschiedene Restklasse ein Inverses. Die Rechnung ist also exakt im Körper \(\mathbb{Z}/M\mathbb{Z}\) und nicht numerisch approximiert.
Aus der Rekursion folgt
$$c_2=\frac{(20\cdot 2-10)c_1-(64\cdot 2-64)c_0}{2}=\frac{30\cdot 10-64}{2}=118.$$
Da \(n=5\) ungerade ist, lautet der Vorfaktor
$$B(5)=50\cdot 2^2u-30-35u=165u-30\equiv 25\pmod M.$$
Für die Summe braucht man
$$K(5)=20\cdot 2^2u+15=80u+15,\qquad K(3)=20\cdot 2u+3=40u+3,\qquad K(1)=1.$$
Damit erhält man
$$\begin{aligned} G(5)&\equiv B(5)+c_0K(5)+c_1K(3)+c_2K(1) \\ &\equiv 25+(80u+15)+10(40u+3)+118 \\ &\equiv 188+480u \\ &\equiv 188+160 \\ &\equiv 348 \pmod M. \end{aligned}$$
Das stimmt mit dem bekannten Kontrollwert der Implementierungen überein.
Die C++-, Python- und Java-Implementierungen folgen demselben Ablauf. Zuerst wird das Inverse von \(3\) bestimmt, dann der paritätsabhängige Vorfaktor \(B(n)\) ausgewertet und die Grenze \(\lfloor (n-1)/2\rfloor\) festgelegt. Anschließend wird die Koeffizientenliste \(c_0,c_1,\dots,c_{\lfloor (n-1)/2\rfloor}\) iterativ aus der Rekursion aufgebaut.
Danach durchläuft die Implementierung denselben Indexbereich noch einmal, berechnet den Kern bei \(n-2i\), multipliziert mit dem gespeicherten Koeffizienten \(c_i\) und akkumuliert alles modulo \(M\). Die C++-Version verwendet für Inverse den erweiterten euklidischen Algorithmus, während Python und Java wegen des primen Moduls schnelle modulare Potenzierung verwenden. Die algorithmische Struktur ist in allen drei Sprachen gleich.
Sei \(L=\lfloor (n-1)/2\rfloor\). Das Erzeugen der Rekursionskoeffizienten benötigt \(O(L)\) Rechenschritte, und die abschließende Faltungssumme benötigt nochmals \(O(L)\) Schritte. Da der Modulus im Problem fest ist, ist das insgesamt linear in \(n\). Zählt man die Berechnung modularer Inversen explizit mit, erhält man \(O(L\log M)\), was hier ebenfalls praktisch linear ist. Der Speicherverbrauch beträgt \(O(L)\), weil die Koeffizientenliste für den zweiten Durchlauf gespeichert wird.
Problem 895, Gold & Silver Coin Game II için \(G(9898)\) değerini \(M=989898989\) modunda istiyor. C++, Python ve Java uygulamaları oyun durumlarını tek tek üretmiyor. Bunun yerine \(G(n)\) için pariteye duyarlı bir çekirdek dizi, reküransla tanımlanan katsayılar ve kısa bir düzeltme teriminden oluşan kapalı bir ayrışım kullanıyor.
Hesabı uygulanabilir yapan şey bu yeniden yazımdır. Tüm bileşenler tek yönlü bir geçişte üretilebiliyor ve tüm bölmeler modüler ters üzerinden yapıldığı için hesap bütünüyle \(\mathbb{Z}/M\mathbb{Z}\) içinde kalıyor.
\(u\), \(3\)'ün modüler tersi olsun; yani \(3u\equiv 1\pmod M\). \(n\ge 2\) için uygulamalar \(G(n)\)'yi üç parçadan kuruyor: bir çekirdek dizi \(K(m)\), bir katsayı dizisi \(c_i\) ve pariteye bağlı bir ön terim \(B(n)\).
İç terim yalnızca \(m\) argümanına ve onun tek/çift oluşuna bağlıdır. Uygulanan çekirdek matematiksel olarak şöyledir:
$$K(m)=\begin{cases} 0, & m\le 0,\\ 1, & m=1,\\ 14\cdot 2^{m/2}u+6m-15 \pmod M, & m\ge 2,\ m\text{ çift},\\ 20\cdot 2^{(m-1)/2}u+6m-15 \pmod M, & m\ge 3,\ m\text{ tek}. \end{cases}$$
Burada \(2\)'nin kuvveti yalnızca \(\lfloor m/2\rfloor\) ile büyür; önündeki katsayı ise parite değişince \(14\)'ten \(20\)'ye çıkar. Nihai formülün en önemli yapısal noktalarından biri budur.
Konvolüsyon ağırlıkları ikinci dereceden bir rekürans sağlar:
$$c_0=1,\qquad c_1=10,$$
$$c_i\equiv \left((20i-10)c_{i-1}-(64i-64)c_{i-2}\right)i^{-1}\pmod M \qquad (i\ge 2).$$
İlk birkaç değer
$$1,\ 10,\ 118,\ 1540,\ 21286,\ \dots$$
şeklindedir. \(M\) asal olduğundan ve kullanılan her \(i\) için \(1\le i<M\) geçerli olduğundan, \(i^{-1}\) her zaman vardır.
Şunu tanımlayalım:
$$A(x)=\sum_{i\ge 0} c_i x^i.$$
Bu durumda rekürans aşağıdaki diferansiyel denkleme denktir:
$$\left(1-20x+64x^2\right)A'(x)=\left(10-64x\right)A(x),\qquad A(0)=1.$$
Buradan
$$A(x)=\frac{1}{\sqrt{1-20x+64x^2}}=\frac{1}{\sqrt{(1-4x)(1-16x)}}$$
elde edilir. Bu bakış açısı, rekürans katsayılarının neden tek boyutlu bir konvolüsyon içinde ortaya çıktığını açıklar: Bunlar sabit bir cebirsel üreteç fonksiyonunun katsayılarıdır.
Kalan küçük düzeltme terimi de pariteye bağlıdır:
$$B(n)\equiv \begin{cases} 35\cdot 2^{n/2}u-6n-35u \pmod M, & n\text{ çift},\\ 50\cdot 2^{(n-1)/2}u-6n-35u \pmod M, & n\text{ tek}. \end{cases}$$
Böylece uygulanan özdeşlik
$$\boxed{G(n)\equiv B(n)+\sum_{i=0}^{\lfloor (n-1)/2\rfloor} c_i\,K(n-2i)\pmod M.}$$
\(n-2i\) biçimi nedeniyle toplam boyunca parite korunur. Çift \(n\) yalnızca çekirdeğin çift kolunu kullanır; tek \(n\) ise tek kol boyunca ilerler ve sonunda \(K(1)=1\) noktasına iner.
Formülde \(3\)'e ve rekürans indeksi \(i\)'ye bölme vardır. Modüler aritmetikte bunlar çarpımsal ters ile değiştirilir. \(M=989898989\) asal olduğu için sıfır dışındaki her kalanın tersi vardır. Dolayısıyla hesap sonlu cisim \(\mathbb{Z}/M\mathbb{Z}\) içinde tam olarak yapılır; yaklaşık hesap yoktur.
Reküranstan
$$c_2=\frac{(20\cdot 2-10)c_1-(64\cdot 2-64)c_0}{2}=\frac{30\cdot 10-64}{2}=118$$
bulunur. \(n=5\) tek olduğu için ön terim
$$B(5)=50\cdot 2^2u-30-35u=165u-30\equiv 25\pmod M$$
olur. Toplamda gereken çekirdek değerleri
$$K(5)=20\cdot 2^2u+15=80u+15,\qquad K(3)=20\cdot 2u+3=40u+3,\qquad K(1)=1$$
şeklindedir. Böylece
$$\begin{aligned} G(5)&\equiv B(5)+c_0K(5)+c_1K(3)+c_2K(1) \\ &\equiv 25+(80u+15)+10(40u+3)+118 \\ &\equiv 188+480u \\ &\equiv 188+160 \\ &\equiv 348 \pmod M. \end{aligned}$$
Bu sonuç uygulamalardaki doğrulama değeriyle aynıdır.
C++, Python ve Java uygulamaları aynı sayısal akışı izler. Önce \(3\)'ün tersi hesaplanır, sonra pariteye bağlı \(B(n)\) terimi değerlendirilir ve \(\lfloor (n-1)/2\rfloor\) sınırı belirlenir. Ardından yukarıdaki rekürans kullanılarak \(c_0,c_1,\dots,c_{\lfloor (n-1)/2\rfloor}\) listesi üretilir.
Sonrasında uygulama aynı indis aralığını bir kez daha dolaşır, \(n-2i\) noktasındaki çekirdeği hesaplar, bunu saklanan \(c_i\) ile çarpar ve sonucu mod \(M\) altında toplar. C++ sürümü tersleri genişletilmiş Öklid algoritmasıyla bulur; Python ve Java sürümleri asal mod altında hızlı üs alma kullanır. Üç dilde de algoritmanın yapısı aynıdır.
\(L=\lfloor (n-1)/2\rfloor\) olsun. Rekürans katsayılarını üretmek \(O(L)\) aritmetik adım, son konvolüsyon toplamı da ek olarak \(O(L)\) adım gerektirir. Modül problem için sabit olduğundan toplam süre \(n\) cinsinden doğrusaldır. Modüler ters maliyetini açık yazarsak süre \(O(L\log M)\) olur; burada bu da pratikte doğrusal kabul edilir. Bellek kullanımı \(O(L)\)'dir, çünkü katsayı listesi ikinci geçiş için saklanır.
El problema 895 pide el valor de \(G(9898)\) para Gold & Silver Coin Game II, reducido módulo \(M=989898989\). Las implementaciones en C++, Python y Java no simulan directamente los estados del juego. En su lugar evalúan una descomposición exacta de \(G(n)\) formada por un núcleo sensible a la paridad, una sucesión de coeficientes definida por recurrencia y un término correctivo corto.
Esa reformulación es la razón de que el cálculo sea viable. Todos los ingredientes se generan en una sola pasada hacia adelante y todas las divisiones se hacen mediante inversos modulares.
Sea \(u\) el inverso modular de \(3\), de modo que \(3u\equiv 1\pmod M\). Para \(n\ge 2\), las implementaciones calculan \(G(n)\) a partir de tres piezas: una sucesión núcleo \(K(m)\), una sucesión de coeficientes \(c_i\) y un prefactor dependiente de la paridad \(B(n)\).
El término interno depende solo del argumento \(m\) y de si es par o impar. El núcleo implementado es
$$K(m)=\begin{cases} 0, & m\le 0,\\ 1, & m=1,\\ 14\cdot 2^{m/2}u+6m-15 \pmod M, & m\ge 2,\ m\text{ par},\\ 20\cdot 2^{(m-1)/2}u+6m-15 \pmod M, & m\ge 3,\ m\text{ impar}. \end{cases}$$
La potencia de \(2\) solo crece con \(\lfloor m/2\rfloor\), mientras que el coeficiente delantero cambia de \(14\) a \(20\) cuando cambia la paridad. Esa separación es una de las claves estructurales de la fórmula final.
Los pesos de la convolución satisfacen una recurrencia de segundo orden:
$$c_0=1,\qquad c_1=10,$$
$$c_i\equiv \left((20i-10)c_{i-1}-(64i-64)c_{i-2}\right)i^{-1}\pmod M \qquad (i\ge 2).$$
Los primeros valores son
$$1,\ 10,\ 118,\ 1540,\ 21286,\ \dots$$
Como \(M\) es primo y cada índice usado cumple \(1\le i<M\), el inverso \(i^{-1}\) existe siempre módulo \(M\).
Definamos
$$A(x)=\sum_{i\ge 0} c_i x^i.$$
Entonces la recurrencia equivale a la ecuación diferencial
$$\left(1-20x+64x^2\right)A'(x)=\left(10-64x\right)A(x),\qquad A(0)=1.$$
Su solución es
$$A(x)=\frac{1}{\sqrt{1-20x+64x^2}}=\frac{1}{\sqrt{(1-4x)(1-16x)}}.$$
Esta interpretación explica por qué los coeficientes aparecen en una convolución unidimensional: son exactamente los coeficientes de una función generadora algebraica fija.
El término correctivo restante también depende de la paridad:
$$B(n)\equiv \begin{cases} 35\cdot 2^{n/2}u-6n-35u \pmod M, & n\text{ par},\\ 50\cdot 2^{(n-1)/2}u-6n-35u \pmod M, & n\text{ impar}. \end{cases}$$
Con esta notación, la identidad implementada es
$$\boxed{G(n)\equiv B(n)+\sum_{i=0}^{\lfloor (n-1)/2\rfloor} c_i\,K(n-2i)\pmod M.}$$
El desplazamiento por \(2\) conserva la paridad de \(n\) a lo largo de toda la suma. Las entradas pares solo usan la rama par del núcleo, mientras que las impares recorren la rama impar y terminan en \(K(1)=1\).
La fórmula divide por \(3\) y por el índice \(i\) de la recurrencia. En aritmética modular eso significa multiplicar por inversos. Como \(M=989898989\) es primo, todo residuo no nulo tiene inverso. Por tanto, el cálculo es exacto dentro del cuerpo finito \(\mathbb{Z}/M\mathbb{Z}\).
La recurrencia da
$$c_2=\frac{(20\cdot 2-10)c_1-(64\cdot 2-64)c_0}{2}=\frac{30\cdot 10-64}{2}=118.$$
Como \(n=5\) es impar, el prefactor es
$$B(5)=50\cdot 2^2u-30-35u=165u-30\equiv 25\pmod M.$$
Los valores del núcleo que intervienen son
$$K(5)=20\cdot 2^2u+15=80u+15,\qquad K(3)=20\cdot 2u+3=40u+3,\qquad K(1)=1.$$
Por lo tanto,
$$\begin{aligned} G(5)&\equiv B(5)+c_0K(5)+c_1K(3)+c_2K(1) \\ &\equiv 25+(80u+15)+10(40u+3)+118 \\ &\equiv 188+480u \\ &\equiv 188+160 \\ &\equiv 348 \pmod M. \end{aligned}$$
Ese resultado coincide con el punto de control conocido de las implementaciones.
Las implementaciones en C++, Python y Java siguen el mismo plan numérico. Primero calculan el inverso de \(3\), evalúan el prefactor \(B(n)\) según la paridad y fijan el límite \(\lfloor (n-1)/2\rfloor\). Luego generan iterativamente la lista \(c_0,c_1,\dots,c_{\lfloor (n-1)/2\rfloor}\) usando la recurrencia anterior.
Después recorren una vez más el mismo rango de índices, evalúan el núcleo en \(n-2i\), multiplican por el coeficiente almacenado \(c_i\) y acumulan el resultado módulo \(M\). La versión en C++ obtiene los inversos con el algoritmo extendido de Euclides, mientras que las versiones en Python y Java usan exponenciación modular rápida bajo el hecho de que el módulo es primo. La estructura algorítmica es la misma en los tres casos.
Sea \(L=\lfloor (n-1)/2\rfloor\). Construir los coeficientes de la recurrencia cuesta \(O(L)\) operaciones aritméticas y la suma final de convolución cuesta otras \(O(L)\). Como el módulo es fijo en este problema, el tiempo total es lineal en \(n\). Si se cuenta explícitamente el coste de los inversos modulares, el tiempo es \(O(L\log M)\), que aquí sigue siendo efectivamente lineal. La memoria es \(O(L)\) porque la lista de coeficientes se conserva para la pasada final.
第 895 题要求在 Gold & Silver Coin Game II 中计算 \(G(9898)\)，并对 \(M=989898989\) 取模。现有的 C++、Python 和 Java 实现都没有直接枚举游戏状态，而是把 \(G(n)\) 改写成一个完全显式的公式：其中包含一个与奇偶性有关的核序列、一条递推生成的系数序列，以及一个很短的修正项。
真正让问题变得可计算的就是这一步改写。所有量都可以按顺序在线性时间内生成，而且所有“除法”都在模意义下用逆元完成，因此整个计算始终停留在 \(\mathbb{Z}/M\mathbb{Z}\) 里。
记 \(u\) 为 \(3\) 在模 \(M\) 下的逆元，即 \(3u\equiv 1\pmod M\)。对 \(n\ge 2\)，实现实际上是由三个部分拼出 \(G(n)\)：核序列 \(K(m)\)、系数序列 \(c_i\)、以及一个依赖于奇偶性的前置项 \(B(n)\)。
卷积中的“被卷积对象”只依赖于参数 \(m\) 以及 \(m\) 的奇偶性。实现中的核可以写成
$$K(m)=\begin{cases} 0, & m\le 0,\\ 1, & m=1,\\ 14\cdot 2^{m/2}u+6m-15 \pmod M, & m\ge 2,\ m\text{ 为偶数},\\ 20\cdot 2^{(m-1)/2}u+6m-15 \pmod M, & m\ge 3,\ m\text{ 为奇数}. \end{cases}$$
可以看到，指数部分只随着 \(\lfloor m/2\rfloor\) 增长，而前面的系数在偶数情形是 \(14\)，奇数情形是 \(20\)。这种奇偶分裂并不是表面现象，而是整个公式组织方式的核心。
卷积权重满足一条二阶递推：
$$c_0=1,\qquad c_1=10,$$
$$c_i\equiv \left((20i-10)c_{i-1}-(64i-64)c_{i-2}\right)i^{-1}\pmod M \qquad (i\ge 2).$$
前几项是
$$1,\ 10,\ 118,\ 1540,\ 21286,\ \dots$$
由于 \(M\) 是素数，而且实际计算中所有下标都满足 \(1\le i<M\)，所以 \(i^{-1}\) 在模 \(M\) 下总是存在。也就是说，这条递推在模意义下是完全合法的。
设
$$A(x)=\sum_{i\ge 0} c_i x^i.$$
把递推乘上 \(x^i\) 并求和，可以得到对应的微分方程
$$\left(1-20x+64x^2\right)A'(x)=\left(10-64x\right)A(x),\qquad A(0)=1.$$
解出来就是
$$A(x)=\frac{1}{\sqrt{1-20x+64x^2}}=\frac{1}{\sqrt{(1-4x)(1-16x)}}.$$
这个写法非常有帮助，因为它说明 \(c_i\) 并不是一串偶然出现的数，而是一个固定代数型生成函数的系数。于是最后出现一维卷积就变得很自然了：本质上就是把这组系数与核序列按相同步长配对。
除了卷积本身之外，实现还加入了一个很短的修正项，它同样依赖于 \(n\) 的奇偶性：
$$B(n)\equiv \begin{cases} 35\cdot 2^{n/2}u-6n-35u \pmod M, & n\text{ 为偶数},\\ 50\cdot 2^{(n-1)/2}u-6n-35u \pmod M, & n\text{ 为奇数}. \end{cases}$$
于是，对所有 \(n\ge 2\)，程序实现的就是
$$\boxed{G(n)\equiv B(n)+\sum_{i=0}^{\lfloor (n-1)/2\rfloor} c_i\,K(n-2i)\pmod M.}$$
这里的关键是参数写成 \(n-2i\)。这意味着在整个求和过程中奇偶性不会改变：当 \(n\) 为偶数时，只会访问核序列的偶数分支；当 \(n\) 为奇数时，只会访问奇数分支，并最终落到特殊值 \(K(1)=1\)。这正是实现能保持简单线性结构的原因。
公式里需要“除以” \(3\) 和“除以”递推下标 \(i\)。在模运算里，这其实就是乘上相应的逆元。因为 \(M=989898989\) 是素数，所以所有非零剩余类都有乘法逆元。换句话说，整个过程不是数值近似，而是在有限域 \(\mathbb{Z}/M\mathbb{Z}\) 中进行的精确运算。
先用递推算出
$$c_2=\frac{(20\cdot 2-10)c_1-(64\cdot 2-64)c_0}{2}=\frac{30\cdot 10-64}{2}=118.$$
因为 \(n=5\) 是奇数，所以前置项为
$$B(5)=50\cdot 2^2u-30-35u=165u-30\equiv 25\pmod M.$$
卷积里需要的核值是
$$K(5)=20\cdot 2^2u+15=80u+15,\qquad K(3)=20\cdot 2u+3=40u+3,\qquad K(1)=1.$$
因此
$$\begin{aligned} G(5)&\equiv B(5)+c_0K(5)+c_1K(3)+c_2K(1) \\ &\equiv 25+(80u+15)+10(40u+3)+118 \\ &\equiv 188+480u \\ &\equiv 188+160 \\ &\equiv 348 \pmod M. \end{aligned}$$
这与实现里使用的已知校验值完全一致。
C++、Python 和 Java 三个实现使用的是同一套流程。首先求出 \(3\) 的模逆，并根据 \(n\) 的奇偶性计算前置项 \(B(n)\)，再确定上界 \(\lfloor (n-1)/2\rfloor\)。随后按照上面的递推从前往后生成 \(c_0,c_1,\dots,c_{\lfloor (n-1)/2\rfloor}\) 这一整列系数。
接下来，程序再扫描一遍同样的下标范围，把每个 \(i\) 对应的核值 \(K(n-2i)\) 算出来，与已经保存的 \(c_i\) 相乘，再累加到答案中并持续对 \(M\) 取模。C++ 实现用扩展欧几里得算法求逆元；Python 和 Java 实现则利用模数为素数这一事实，通过快速幂求逆。除此之外，三种语言的算法结构完全一致。
设 \(L=\lfloor (n-1)/2\rfloor\)。生成递推系数需要 \(O(L)\) 次模运算，最后的卷积求和也需要 \(O(L)\) 次模运算，因此在本题固定模数的前提下，总时间复杂度对 \(n\) 是线性的。如果把每次求逆元的代价单独写出来，则为 \(O(L\log M)\)，在这里依然可以视为近似线性。空间复杂度是 \(O(L)\)，因为实现需要把整列系数保存下来供最后一遍求和使用。
В задаче 895 требуется найти значение \(G(9898)\) для Gold & Silver Coin Game II по модулю \(M=989898989\). Реализации на C++, Python и Java не перебирают игровые состояния напрямую. Вместо этого они используют точное замкнутое разложение \(G(n)\), состоящее из ядра с разветвлением по четности, рекуррентной последовательности коэффициентов и короткого поправочного члена.
Именно это преобразование делает вычисление практичным. Все нужные величины строятся за один линейный проход, а все деления выполняются как умножение на обратные элементы по модулю.
Пусть \(u\) обозначает обратный элемент к \(3\) по модулю \(M\), то есть \(3u\equiv 1\pmod M\). Для \(n\ge 2\) реализации вычисляют \(G(n)\) из трех составляющих: ядра \(K(m)\), последовательности коэффициентов \(c_i\) и зависящего от четности префактора \(B(n)\).
Внутренний член зависит только от аргумента \(m\) и его четности. Реализованное ядро имеет вид
$$K(m)=\begin{cases} 0, & m\le 0,\\ 1, & m=1,\\ 14\cdot 2^{m/2}u+6m-15 \pmod M, & m\ge 2,\ m\text{ четно},\\ 20\cdot 2^{(m-1)/2}u+6m-15 \pmod M, & m\ge 3,\ m\text{ нечетно}. \end{cases}$$
Степень двойки растет только как \(\lfloor m/2\rfloor\), а коэффициент перед ней меняется с \(14\) на \(20\) при смене четности. Это одна из ключевых особенностей всей формулы.
Весовые коэффициенты свертки задаются рекурсией второго порядка:
$$c_0=1,\qquad c_1=10,$$
$$c_i\equiv \left((20i-10)c_{i-1}-(64i-64)c_{i-2}\right)i^{-1}\pmod M \qquad (i\ge 2).$$
Первые значения таковы:
$$1,\ 10,\ 118,\ 1540,\ 21286,\ \dots$$
Поскольку \(M\) простое и все используемые индексы удовлетворяют \(1\le i<M\), обратный элемент \(i^{-1}\) всегда существует.
Введем
$$A(x)=\sum_{i\ge 0} c_i x^i.$$
Тогда рекурсия эквивалентна дифференциальному уравнению
$$\left(1-20x+64x^2\right)A'(x)=\left(10-64x\right)A(x),\qquad A(0)=1.$$
Его решение имеет вид
$$A(x)=\frac{1}{\sqrt{1-20x+64x^2}}=\frac{1}{\sqrt{(1-4x)(1-16x)}}.$$
Это объясняет, почему коэффициенты естественным образом входят в одномерную свертку: они являются коэффициентами фиксированной алгебраической производящей функции.
Оставшийся поправочный член тоже зависит от четности:
$$B(n)\equiv \begin{cases} 35\cdot 2^{n/2}u-6n-35u \pmod M, & n\text{ четно},\\ 50\cdot 2^{(n-1)/2}u-6n-35u \pmod M, & n\text{ нечетно}. \end{cases}$$
В этих обозначениях реализованная формула такова:
$$\boxed{G(n)\equiv B(n)+\sum_{i=0}^{\lfloor (n-1)/2\rfloor} c_i\,K(n-2i)\pmod M.}$$
Сдвиг на \(2\) сохраняет четность аргумента по всей сумме. Для четных \(n\) используются только четные значения ядра, а для нечетных \(n\) только нечетные, причем цепочка завершается в точке \(K(1)=1\).
В формуле есть деление на \(3\) и на индекс рекурсии \(i\). В арифметике по модулю это означает умножение на обратные элементы. Так как \(M=989898989\) простое, любая ненулевая вычетная класс имеет обратный элемент. Следовательно, вычисление выполняется точно в поле \(\mathbb{Z}/M\mathbb{Z}\).
Из рекурсии получаем
$$c_2=\frac{(20\cdot 2-10)c_1-(64\cdot 2-64)c_0}{2}=\frac{30\cdot 10-64}{2}=118.$$
Так как \(n=5\) нечетно, префактор равен
$$B(5)=50\cdot 2^2u-30-35u=165u-30\equiv 25\pmod M.$$
Нужные значения ядра:
$$K(5)=20\cdot 2^2u+15=80u+15,\qquad K(3)=20\cdot 2u+3=40u+3,\qquad K(1)=1.$$
Тогда
$$\begin{aligned} G(5)&\equiv B(5)+c_0K(5)+c_1K(3)+c_2K(1) \\ &\equiv 25+(80u+15)+10(40u+3)+118 \\ &\equiv 188+480u \\ &\equiv 188+160 \\ &\equiv 348 \pmod M. \end{aligned}$$
Это в точности совпадает с контрольным значением, используемым реализациями.
Реализации на C++, Python и Java следуют одному и тому же вычислительному плану. Сначала находится обратный элемент к \(3\), затем вычисляется префактор \(B(n)\) в зависимости от четности и устанавливается граница \(\lfloor (n-1)/2\rfloor\). После этого по рекурсии строится список коэффициентов \(c_0,c_1,\dots,c_{\lfloor (n-1)/2\rfloor}\).
Затем реализация еще раз проходит по тому же диапазону индексов, вычисляет ядро в точке \(n-2i\), умножает на сохраненный коэффициент \(c_i\) и добавляет результат к ответу по модулю \(M\). В версии на C++ обратные элементы находятся расширенным алгоритмом Евклида, а в версиях на Python и Java используется быстрое возведение в степень благодаря простоте модуля. Во всем остальном структура алгоритма одинакова.
Пусть \(L=\lfloor (n-1)/2\rfloor\). Построение коэффициентов рекурсии требует \(O(L)\) арифметических действий, а итоговая свертка требует еще \(O(L)\) действий. Поскольку модуль фиксирован для всей задачи, общее время линейно по \(n\). Если отдельно учитывать стоимость вычисления обратных элементов, получится \(O(L\log M)\), что здесь все равно практически линейно. Память равна \(O(L)\), потому что список коэффициентов хранится для финального прохода.
تطلب المسألة 895 إيجاد قيمة \(G(9898)\) في Gold & Silver Coin Game II بترديد \(M=989898989\). لا تقوم تطبيقات C++ وPython وJava بمحاكاة حالات اللعبة مباشرة، بل تعتمد على تفكيك مغلق ودقيق لـ \(G(n)\) يتكوّن من نواة تعتمد على فردية العدد أو زوجيته، ومتتالية معاملات تُبنى بعلاقة تكرارية، وحد تصحيح قصير.
هذه الصياغة هي التي تجعل الحساب ممكنًا عمليًا. فجميع المكونات تُولَّد في مرور خطي واحد، وكل عملية قسمة تُنفَّذ على صورة ضرب في معكوس معياري.
لنرمز بـ \(u\) إلى المعكوس المعياري للعدد \(3\)، أي \(3u\equiv 1\pmod M\). عندما \(n\ge 2\)، تحسب التطبيقات \(G(n)\) من ثلاثة أجزاء: نواة \(K(m)\)، ومتتالية معاملات \(c_i\)، ومقدّمة \(B(n)\) تعتمد على فردية \(n\) أو زوجيته.
الحد الداخلي يعتمد فقط على الوسيط \(m\) وعلى كونه زوجيًا أو فرديًا. النواة المطبقة في الحل هي
$$K(m)=\begin{cases} 0, & m\le 0,\\ 1, & m=1,\\ 14\cdot 2^{m/2}u+6m-15 \pmod M, & m\ge 2,\ m\text{ even},\\ 20\cdot 2^{(m-1)/2}u+6m-15 \pmod M, & m\ge 3,\ m\text{ odd}. \end{cases}$$
قوة العدد \(2\) تنمو فقط مع \(\lfloor m/2\rfloor\)، بينما يتبدل المعامل الأمامي بين \(14\) و\(20\) بحسب الفردية والزوجية. هذا الانقسام هو أحد المحاور الأساسية في الصيغة النهائية.
أوزان الالتفاف تحقق علاقة تكرارية من الرتبة الثانية:
$$c_0=1,\qquad c_1=10,$$
$$c_i\equiv \left((20i-10)c_{i-1}-(64i-64)c_{i-2}\right)i^{-1}\pmod M \qquad (i\ge 2).$$
وأوائل الحدود هي
$$1,\ 10,\ 118,\ 1540,\ 21286,\ \dots$$
وبما أن \(M\) عدد أولي، وكل فهرس مستخدم يحقق \(1\le i<M\)، فإن المعكوس \(i^{-1}\) موجود دائمًا بترديد \(M\).
لنعرّف
$$A(x)=\sum_{i\ge 0} c_i x^i.$$
عند جمع العلاقة التكرارية بعد ضربها في \(x^i\)، نحصل على المعادلة التفاضلية
$$\left(1-20x+64x^2\right)A'(x)=\left(10-64x\right)A(x),\qquad A(0)=1.$$
ومنها نستنتج
$$A(x)=\frac{1}{\sqrt{1-20x+64x^2}}=\frac{1}{\sqrt{(1-4x)(1-16x)}}.$$
هذا يوضح أن المعاملات ليست أعدادًا معزولة ظهرت بالمصادفة، بل هي معاملات دالة مولدة جبرية ثابتة. لذلك يظهر الالتفاف أحادي البعد بصورة طبيعية في الصيغة النهائية.
يبقى حد تصحيح صغير يعتمد أيضًا على فردية \(n\) أو زوجيته:
$$B(n)\equiv \begin{cases} 35\cdot 2^{n/2}u-6n-35u \pmod M, & n\text{ even},\\ 50\cdot 2^{(n-1)/2}u-6n-35u \pmod M, & n\text{ odd}. \end{cases}$$
وعندئذ تكون الهوية التي تنفذها التطبيقات هي
$$\boxed{G(n)\equiv B(n)+\sum_{i=0}^{\lfloor (n-1)/2\rfloor} c_i\,K(n-2i)\pmod M.}$$
وجود الإزاحة \(n-2i\) يعني أن فردية \(n\) تبقى ثابتة داخل المجموع كله. فإذا كان \(n\) زوجيًا فلن نستخدم إلا الفرع الزوجي من النواة، وإذا كان فرديًا فسنستخدم الفرع الفردي وننتهي عند القيمة الخاصة \(K(1)=1\).
تتضمن الصيغة قسمة على \(3\) وعلى الفهرس \(i\). في الحساب المعياري تتحول هذه العملية إلى ضرب في معكوس ضربي. ولأن \(M=989898989\) عدد أولي، فلكل باقي غير صفري معكوس. لذا فالحساب يتم بدقة تامة داخل الحقل المنتهي \(\mathbb{Z}/M\mathbb{Z}\).
تعطينا العلاقة التكرارية
$$c_2=\frac{(20\cdot 2-10)c_1-(64\cdot 2-64)c_0}{2}=\frac{30\cdot 10-64}{2}=118.$$
وبما أن \(n=5\) فردي، فإن المقدمة تساوي
$$B(5)=50\cdot 2^2u-30-35u=165u-30\equiv 25\pmod M.$$
وقيم النواة المطلوبة هي
$$K(5)=20\cdot 2^2u+15=80u+15,\qquad K(3)=20\cdot 2u+3=40u+3,\qquad K(1)=1.$$
ومن ثم
$$\begin{aligned} G(5)&\equiv B(5)+c_0K(5)+c_1K(3)+c_2K(1) \\ &\equiv 25+(80u+15)+10(40u+3)+118 \\ &\equiv 188+480u \\ &\equiv 188+160 \\ &\equiv 348 \pmod M. \end{aligned}$$
وهذه بالضبط قيمة التحقق المعروفة في التطبيقات.
تتبع تطبيقات C++ وPython وJava الخطة الحسابية نفسها. أولًا تحسب معكوس \(3\)، ثم تقيم الحد \(B(n)\) بحسب فردية \(n\) أو زوجيته، وتحدد الحد الأعلى \(\lfloor (n-1)/2\rfloor\). بعد ذلك تُبنى قائمة المعاملات \(c_0,c_1,\dots,c_{\lfloor (n-1)/2\rfloor}\) تدريجيًا بواسطة العلاقة التكرارية السابقة.
ثم يمر التنفيذ مرة ثانية على المجال نفسه، فيحسب قيمة النواة عند \(n-2i\)، ويضربها في المعامل المخزن \(c_i\)، ويضيف الناتج إلى المجموع الكلي مع الاختزال المستمر بترديد \(M\). تستخدم نسخة C++ خوارزمية إقليدس الممتدة لإيجاد المعكوسات، بينما تستخدم نسختا Python وJava الأس المعياري السريع اعتمادًا على أن المودول عدد أولي. بخلاف ذلك، تبقى البنية الخوارزمية واحدة في اللغات الثلاث.
إذا وضعنا \(L=\lfloor (n-1)/2\rfloor\)، فإن بناء معاملات العلاقة التكرارية يحتاج إلى \(O(L)\) خطوة حسابية، كما أن مجموع الالتفاف النهائي يحتاج إلى \(O(L)\) خطوة أخرى. وبما أن المودول ثابت في هذه المسألة، فإن الزمن الكلي خطي في \(n\). وإذا فُصلت كلفة إيجاد المعكوسات المعيارية، أصبح الزمن \(O(L\log M)\)، وهو هنا لا يزال عمليًا شبه خطي. أما الذاكرة فهي \(O(L)\) لأن قائمة المعاملات تحفظ لاستخدامها في المرور الأخير.