A fair coin is tossed until two consecutive heads appear for the first time. Let \(M\) be the index of the second toss in that first \(HH\) block, so \(M\ge 2\). For a positive integer \(n\), define \(P(n)=\Pr(n\mid M)\), the probability that \(n\) divides the stopping time. If \(P(n)=a/b\) in lowest terms and \(p\) is prime, then \(Q(P(n),p)\) is the least positive residue \(q\) such that \(a\equiv bq\pmod p\).
The target is \(Q(P(10^{18}),10^9+9)\). The number \(10^{18}\) is far too large for direct summation over all multiples of \(n\), so the solution turns the stopping-time question into a 2x2 linear algebra problem and evaluates it directly in modular arithmetic.
Before the first appearance of \(HH\), only one piece of history matters: whether the last toss was a head. That observation collapses the probabilistic process to two transient states.
Use two non-absorbing states:
\(S\): the last toss was not a head, or no toss has happened yet.
\(H\): the last toss was a head, but the process has not stopped yet.
From \(S\), a tail keeps the process in \(S\), while a head moves it to \(H\). From \(H\), a tail returns to \(S\), while a head creates the first \(HH\) and ends the experiment. Therefore the transient transition matrix is
$$T=\begin{bmatrix}\frac12 & \frac12\\[4pt]\frac12 & 0\end{bmatrix}.$$
If
$$v_t=\begin{bmatrix}s_t\\ h_t\end{bmatrix}$$
is the transient-state vector after \(t\) tosses, then
$$v_{t+1}=T\,v_t,\qquad v_0=\begin{bmatrix}1\\0\end{bmatrix}.$$
The process ends at toss \(t+1\) exactly when, after \(t\) tosses, it is in state \(H\) and the next toss is another head. Hence
$$\Pr(M=t+1)=\frac12\,h_t=\frac12\begin{bmatrix}0&1\end{bmatrix}v_t.$$
Substituting \(v_t=T^t v_0\) gives
$$\Pr(M=t+1)=\frac12\begin{bmatrix}0&1\end{bmatrix}T^t\begin{bmatrix}1\\0\end{bmatrix}.$$
The matrix \(T\) is one half of the standard Fibonacci companion matrix, so its powers satisfy
$$T^t=\frac{1}{2^t}\begin{bmatrix}F_{t+1}&F_t\\ F_t&F_{t-1}\end{bmatrix}.$$
Therefore the exact stopping distribution is
$$\Pr(M=m)=\frac{F_{m-1}}{2^m}\qquad (m\ge 2).$$
The first values are \(1/4,1/8,1/8,3/32,\dots\), which agrees with a direct case split.
By definition,
$$P(n)=\sum_{k\ge 1}\Pr(M=kn)=\frac12\sum_{k\ge 1}\begin{bmatrix}0&1\end{bmatrix}T^{kn-1}\begin{bmatrix}1\\0\end{bmatrix}.$$
Using the Fibonacci form, the same quantity can be written as
$$P(n)=\sum_{k\ge 1}\frac{F_{kn-1}}{2^{kn}}.$$
This identity is useful conceptually, but for \(n=10^{18}\) it is still not computationally practical. The crucial step is to rewrite the infinite sum as a matrix geometric series.
Set
$$B=T^n,\qquad w=T^{n-1}\begin{bmatrix}1\\0\end{bmatrix}.$$
Then
$$T^{kn-1}=T^{(k-1)n}T^{n-1}=B^{k-1}w,$$
so
$$P(n)=\frac12\begin{bmatrix}0&1\end{bmatrix}\left(\sum_{j\ge 0}B^j\right)w.$$
Over the real numbers, every eigenvalue of \(T\) has absolute value less than \(1\), so the series converges and
$$\sum_{j\ge 0}B^j=(I-B)^{-1}.$$
This yields the exact closed form used by the implementations:
$$\boxed{P(n)=\frac12\begin{bmatrix}0&1\end{bmatrix}(I-T^n)^{-1}T^{n-1}\begin{bmatrix}1\\0\end{bmatrix}.}$$
If \(P(n)=a/b\) in lowest terms, then \(Q(P(n),p)\) is simply the fraction \(a/b\) interpreted in the field \(\mathbb F_p\):
$$Q(P(n),p)\equiv a\,b^{-1}\pmod p.$$
So the computation never has to reconstruct the rational number explicitly. Every division by \(2\) or by a 2x2 determinant can be replaced by a modular inverse. That is why the same matrix formula can be evaluated directly modulo \(10^9+9\).
For \(n=2\),
$$T^2=\begin{bmatrix}\frac12&\frac14\\[4pt]\frac14&\frac14\end{bmatrix},\qquad T\begin{bmatrix}1\\0\end{bmatrix}=\begin{bmatrix}\frac12\\[4pt]\frac12\end{bmatrix}.$$
Hence
$$I-T^2=\begin{bmatrix}\frac12&-\frac14\\[4pt]-\frac14&\frac34\end{bmatrix}.$$
Inverting this matrix and multiplying by \(T(1,0)^T\) gives
$$ (I-T^2)^{-1}T\begin{bmatrix}1\\0\end{bmatrix}=\begin{bmatrix}\frac85\\[4pt]\frac65\end{bmatrix}. $$
Taking the second component and multiplying by \(1/2\) yields
$$P(2)=\frac12\cdot\frac65=\frac35.$$
Modulo \(109\), the inverse of \(5\) is \(22\), so
$$Q(P(2),109)\equiv 3\cdot 22\equiv 66\pmod{109}.$$
A second small checkpoint is \(P(3)=9/31\), which reduces to \(46\) modulo \(109\).
The C++, Python, and Java implementations all encode the same 2x2 matrix over the prime field \(\mathbb F_{10^9+9}\). The value \(1/2\) is represented by the modular inverse of \(2\), so no floating-point arithmetic is used anywhere.
They compute \(T^n\) and \(T^{n-1}\) with binary exponentiation, form the matrix \(I-T^n\), invert that 2x2 matrix with the determinant formula, and multiply the result by the starting-state column vector. The component corresponding to state \(H\) is then multiplied by \(1/2\) to obtain the stopping probability on the next toss. Because the whole computation already lives in a prime field, the final residue is exactly \(Q(P(n),10^9+9)\).
Every matrix is 2x2, so each multiplication and inversion costs constant time. The dominant work is binary exponentiation for \(T^n\) and \(T^{n-1}\), which takes \(O(\log n)\) matrix multiplications. The memory usage is \(O(1)\).
Eine faire Münze wird so lange geworfen, bis erstmals zwei Köpfe hintereinander erscheinen. Sei \(M\) der Index des zweiten Wurfs in diesem ersten \(HH\)-Block, also \(M\ge 2\). Für eine positive ganze Zahl \(n\) ist \(P(n)=\Pr(n\mid M)\), also die Wahrscheinlichkeit, dass \(n\) die Stoppzeit teilt. Schreibt man \(P(n)=a/b\) in vollständig gekürzter Form und ist \(p\) prim, dann ist \(Q(P(n),p)\) der kleinste positive Rest \(q\) mit \(a\equiv bq\pmod p\).
Gesucht ist \(Q(P(10^{18}),10^9+9)\). Wegen der Größe von \(10^{18}\) ist eine direkte Summation über alle Vielfachen von \(n\) unbrauchbar. Die Lösung reduziert das Problem deshalb auf lineare Algebra mit einer 2x2-Matrix und wertet alles direkt modulo einer Primzahl aus.
Vor dem ersten Auftreten von \(HH\) muss man sich nur merken, ob der letzte Wurf ein Kopf war. Damit schrumpft der Prozess auf zwei transiente Zustände.
Wir verwenden zwei nicht absorbierende Zustände:
\(S\): der letzte Wurf war kein Kopf, oder es wurde noch gar nicht geworfen.
\(H\): der letzte Wurf war ein Kopf, aber \(HH\) ist noch nicht entstanden.
Von \(S\) führt Zahl wieder nach \(S\), Kopf nach \(H\). Von \(H\) führt Zahl zurück nach \(S\), während ein weiterer Kopf den ersten \(HH\)-Block erzeugt und den Prozess beendet. Die transiente Übergangsmatrix lautet daher
$$T=\begin{bmatrix}\frac12 & \frac12\\[4pt]\frac12 & 0\end{bmatrix}.$$
Ist
$$v_t=\begin{bmatrix}s_t\\ h_t\end{bmatrix}$$
der Zustandsvektor nach \(t\) Würfen, dann gilt
$$v_{t+1}=T\,v_t,\qquad v_0=\begin{bmatrix}1\\0\end{bmatrix}.$$
Der Prozess endet beim Wurf \(t+1\) genau dann, wenn er nach \(t\) Würfen im Zustand \(H\) ist und der nächste Wurf wieder Kopf zeigt. Also
$$\Pr(M=t+1)=\frac12\,h_t=\frac12\begin{bmatrix}0&1\end{bmatrix}v_t.$$
Mit \(v_t=T^t v_0\) folgt
$$\Pr(M=t+1)=\frac12\begin{bmatrix}0&1\end{bmatrix}T^t\begin{bmatrix}1\\0\end{bmatrix}.$$
Da \(T\) gleich der halben Fibonacci-Begleitmatrix ist, besitzen die Potenzen die Form
$$T^t=\frac{1}{2^t}\begin{bmatrix}F_{t+1}&F_t\\ F_t&F_{t-1}\end{bmatrix}.$$
Daraus erhält man
$$\Pr(M=m)=\frac{F_{m-1}}{2^m}\qquad (m\ge 2).$$
Die ersten Werte \(1/4,1/8,1/8,3/32,\dots\) passen genau zur direkten Fallunterscheidung.
Nach Definition gilt
$$P(n)=\sum_{k\ge 1}\Pr(M=kn)=\frac12\sum_{k\ge 1}\begin{bmatrix}0&1\end{bmatrix}T^{kn-1}\begin{bmatrix}1\\0\end{bmatrix}.$$
Mit der Fibonacci-Darstellung lässt sich dieselbe Größe auch als
$$P(n)=\sum_{k\ge 1}\frac{F_{kn-1}}{2^{kn}}$$
schreiben. Diese Reihe ist mathematisch aufschlussreich, aber bei \(n=10^{18}\) immer noch nicht direkt berechenbar. Deshalb wird sie als geometrische Matrixreihe umgeschrieben.
Setze
$$B=T^n,\qquad w=T^{n-1}\begin{bmatrix}1\\0\end{bmatrix}.$$
Dann ist
$$T^{kn-1}=T^{(k-1)n}T^{n-1}=B^{k-1}w,$$
also
$$P(n)=\frac12\begin{bmatrix}0&1\end{bmatrix}\left(\sum_{j\ge 0}B^j\right)w.$$
Über den reellen Zahlen haben alle Eigenwerte von \(T\) Betrag kleiner als \(1\), daher konvergiert die geometrische Reihe und liefert
$$\sum_{j\ge 0}B^j=(I-B)^{-1}.$$
Somit ergibt sich die exakte geschlossene Formel
$$\boxed{P(n)=\frac12\begin{bmatrix}0&1\end{bmatrix}(I-T^n)^{-1}T^{n-1}\begin{bmatrix}1\\0\end{bmatrix}.}$$
Ist \(P(n)=a/b\) vollständig gekürzt, dann ist \(Q(P(n),p)\) einfach der Rest der rationalen Zahl \(a/b\) im Körper \(\mathbb F_p\):
$$Q(P(n),p)\equiv a\,b^{-1}\pmod p.$$
Man muss die rationale Zahl also nie explizit rekonstruieren. Jede Division durch \(2\) oder durch eine 2x2-Determinante wird durch ein modulares Inverses ersetzt. Genau deshalb kann dieselbe Matrixformel direkt modulo \(10^9+9\) ausgewertet werden.
Für \(n=2\) gilt
$$T^2=\begin{bmatrix}\frac12&\frac14\\[4pt]\frac14&\frac14\end{bmatrix},\qquad T\begin{bmatrix}1\\0\end{bmatrix}=\begin{bmatrix}\frac12\\[4pt]\frac12\end{bmatrix}.$$
Daher
$$I-T^2=\begin{bmatrix}\frac12&-\frac14\\[4pt]-\frac14&\frac34\end{bmatrix}.$$
Nach der Inversion und Multiplikation mit \(T(1,0)^T\) erhält man
$$ (I-T^2)^{-1}T\begin{bmatrix}1\\0\end{bmatrix}=\begin{bmatrix}\frac85\\[4pt]\frac65\end{bmatrix}. $$
Die zweite Komponente liefert nach Multiplikation mit \(1/2\)
$$P(2)=\frac12\cdot\frac65=\frac35.$$
Modulo \(109\) ist das Inverse von \(5\) gleich \(22\), also
$$Q(P(2),109)\equiv 3\cdot 22\equiv 66\pmod{109}.$$
Ein zweiter kleiner Kontrollwert ist \(P(3)=9/31\), was modulo \(109\) den Rest \(46\) ergibt.
Die C++-, Python- und Java-Implementierungen benutzen dieselbe 2x2-Matrix über dem Primkörper \(\mathbb F_{10^9+9}\). Der Wert \(1/2\) wird dabei als modulares Inverses von \(2\) gespeichert, sodass keine Gleitkommazahlen benötigt werden.
Anschließend werden \(T^n\) und \(T^{n-1}\) mit binärer Exponentiation berechnet, dann die Matrix \(I-T^n\) gebildet und per geschlossener 2x2-Determinantenformel invertiert. Das Produkt mit dem Startvektor liefert einen Zustandsvektor, aus dem die Komponente des Zustands \(H\) genommen und noch einmal mit \(1/2\) multipliziert wird. Weil die gesamte Rechnung bereits in einem Primkörper stattfindet, ist der ausgegebene Rest genau \(Q(P(n),10^9+9)\).
Alle Matrizen sind 2x2, daher kosten sowohl Multiplikation als auch Inversion konstante Zeit. Der Hauptaufwand ist die binäre Exponentiation für \(T^n\) und \(T^{n-1}\), also \(O(\log n)\) Matrixmultiplikationen. Der Speicherverbrauch ist \(O(1)\).
Adil bir para, ilk kez art arda iki yazı gelene kadar atılıyor. Bu ilk \(HH\) bloğundaki ikinci yazının atış indeksine \(M\) diyelim; dolayısıyla \(M\ge 2\). Pozitif bir \(n\) için \(P(n)=\Pr(n\mid M)\), yani \(n\)'in durma zamanını bölme olasılığıdır. Eğer \(P(n)=a/b\) sade halde yazılır ve \(p\) asal ise, \(Q(P(n),p)\), \(a\equiv bq\pmod p\) koşulunu sağlayan en küçük pozitif kalıntıdır.
Hedef değer \(Q(P(10^{18}),10^9+9)\)'dur. \(10^{18}\) çok büyük olduğu için \(n\)'in tüm katları üzerindeki olasılıkları doğrudan toplamak mümkün değildir. Çözüm, durma zamanı problemini 2x2 matrisli bir doğrusal cebir problemine indirger ve hesabı doğrudan modüler aritmetikte yapar.
İlk \(HH\) ortaya çıkmadan önce geçmişten gerçekten önemli olan tek bilgi, son atışın yazı olup olmadığıdır. Bu gözlem olasılık sürecini iki transient duruma indirir.
İki adet soğurulmayan durum kullanalım:
\(S\): son atış yazı değildir ya da henüz hiç atış yapılmamıştır.
\(H\): son atış yazıdır, fakat süreç henüz bitmemiştir.
\(S\) durumundan tura gelirse yine \(S\)'de kalırız, yazı gelirse \(H\)'ye geçeriz. \(H\) durumundan tura gelirse \(S\)'ye döneriz, yazı gelirse ilk \(HH\) oluşur ve deney biter. Bu yüzden transient geçiş matrisi
$$T=\begin{bmatrix}\frac12 & \frac12\\[4pt]\frac12 & 0\end{bmatrix}$$
olur. Eğer
$$v_t=\begin{bmatrix}s_t\\ h_t\end{bmatrix}$$
\(t\) atıştan sonraki transient durum vektörü ise
$$v_{t+1}=T\,v_t,\qquad v_0=\begin{bmatrix}1\\0\end{bmatrix}$$
yazabiliriz.
Süreç \(t+1\). atışta ancak ve ancak ilk \(t\) atıştan sonra \(H\) durumundaysak ve bir sonraki atış yine yazıysa biter. Dolayısıyla
$$\Pr(M=t+1)=\frac12\,h_t=\frac12\begin{bmatrix}0&1\end{bmatrix}v_t.$$
\(v_t=T^t v_0\) yerine konursa
$$\Pr(M=t+1)=\frac12\begin{bmatrix}0&1\end{bmatrix}T^t\begin{bmatrix}1\\0\end{bmatrix}$$
elde edilir. \(T\), Fibonacci eşlik matrisinin yarısı olduğu için üsleri
$$T^t=\frac{1}{2^t}\begin{bmatrix}F_{t+1}&F_t\\ F_t&F_{t-1}\end{bmatrix}$$
şeklindedir. Buradan
$$\Pr(M=m)=\frac{F_{m-1}}{2^m}\qquad (m\ge 2)$$
sonucu çıkar. İlk birkaç değer \(1/4,1/8,1/8,3/32,\dots\) olup doğrudan sayımla uyumludur.
Tanım gereği
$$P(n)=\sum_{k\ge 1}\Pr(M=kn)=\frac12\sum_{k\ge 1}\begin{bmatrix}0&1\end{bmatrix}T^{kn-1}\begin{bmatrix}1\\0\end{bmatrix}.$$
Fibonacci biçimiyle aynı nicelik
$$P(n)=\sum_{k\ge 1}\frac{F_{kn-1}}{2^{kn}}$$
olarak da yazılabilir. Bu ifade matematiksel olarak temizdir ama \(n=10^{18}\) için hesaplamaya uygun değildir. Asıl kritik adım, bu sonsuz toplamı geometrik matris serisine çevirmektir.
Şimdi
$$B=T^n,\qquad w=T^{n-1}\begin{bmatrix}1\\0\end{bmatrix}$$
tanımlarını yapalım. Böylece
$$T^{kn-1}=T^{(k-1)n}T^{n-1}=B^{k-1}w$$
ve dolayısıyla
$$P(n)=\frac12\begin{bmatrix}0&1\end{bmatrix}\left(\sum_{j\ge 0}B^j\right)w$$
olur. Gerçek sayılar üzerinde \(T\)'nin tüm özdeğerlerinin mutlak değeri \(1\)'den küçüktür, bu yüzden seri yakınsar ve
$$\sum_{j\ge 0}B^j=(I-B)^{-1}$$
yazarız. Sonuçta implementasyonun kullandığı kapalı form
$$\boxed{P(n)=\frac12\begin{bmatrix}0&1\end{bmatrix}(I-T^n)^{-1}T^{n-1}\begin{bmatrix}1\\0\end{bmatrix}.}$$
Eğer \(P(n)=a/b\) sade haldeyse, \(Q(P(n),p)\) aslında \(a/b\) kesrinin \(\mathbb F_p\) içindeki karşılığıdır:
$$Q(P(n),p)\equiv a\,b^{-1}\pmod p.$$
Yani kesri açıkça üretmeye gerek yoktur. \(2\)'ye ya da 2x2 determinantına bölmek gerektiğinde modüler ters alınır. Bu nedenle aynı matris formülü doğrudan \(10^9+9\) modunda değerlendirilebilir.
\(n=2\) için
$$T^2=\begin{bmatrix}\frac12&\frac14\\[4pt]\frac14&\frac14\end{bmatrix},\qquad T\begin{bmatrix}1\\0\end{bmatrix}=\begin{bmatrix}\frac12\\[4pt]\frac12\end{bmatrix}.$$
Buna göre
$$I-T^2=\begin{bmatrix}\frac12&-\frac14\\[4pt]-\frac14&\frac34\end{bmatrix}.$$
Bu matris terslenip \(T(1,0)^T\) ile çarpıldığında
$$ (I-T^2)^{-1}T\begin{bmatrix}1\\0\end{bmatrix}=\begin{bmatrix}\frac85\\[4pt]\frac65\end{bmatrix} $$
çıkar. İkinci bileşeni alıp \(1/2\) ile çarptığımızda
$$P(2)=\frac12\cdot\frac65=\frac35$$
bulunur. \(109\) modunda \(5\)'in tersi \(22\) olduğundan
$$Q(P(2),109)\equiv 3\cdot 22\equiv 66\pmod{109}$$
elde edilir. Bir başka küçük kontrol de \(P(3)=9/31\) olup bunun \(109\) modundaki kalıntısı \(46\)'dır.
C++, Python ve Java implementasyonları aynı 2x2 matrisi asal cisim \(\mathbb F_{10^9+9}\) üzerinde temsil eder. \(1/2\) değeri, \(2\)'nin modüler tersi olarak tutulur; böylece kayan nokta kullanılmaz.
Daha sonra \(T^n\) ve \(T^{n-1}\) ikili üs alma ile hesaplanır, \(I-T^n\) matrisi oluşturulur ve klasik 2x2 determinant formülüyle terslenir. Başlangıç durum vektörüyle çarpım yapıldıktan sonra \(H\) durumuna karşılık gelen bileşen alınır ve son kez \(1/2\) ile çarpılır. Hesabın tamamı zaten asal bir cisimde yapıldığı için çıkan son kalıntı doğrudan \(Q(P(n),10^9+9)\) değeridir.
Tüm matrisler 2x2 boyutundadır; dolayısıyla her çarpma ve ters alma sabit zamanda gerçekleşir. Ana maliyet \(T^n\) ve \(T^{n-1}\) için yapılan ikili üs almadır; bu da \(O(\log n)\) matris çarpımı gerektirir. Bellek kullanımı \(O(1)\)'dir.
Se lanza una moneda justa hasta que aparecen por primera vez dos caras consecutivas. Sea \(M\) la posición del segundo lanzamiento dentro de ese primer bloque \(HH\), de modo que \(M\ge 2\). Para un entero positivo \(n\), definimos \(P(n)=\Pr(n\mid M)\), la probabilidad de que \(n\) divida el tiempo de parada. Si \(P(n)=a/b\) está en forma reducida y \(p\) es primo, entonces \(Q(P(n),p)\) es el menor residuo positivo \(q\) que satisface \(a\equiv bq\pmod p\).
Hay que calcular \(Q(P(10^{18}),10^9+9)\). Como \(10^{18}\) es enorme, no se puede sumar directamente sobre todos los múltiplos de \(n\). La solución transforma la pregunta probabilística en un problema de álgebra lineal de dimensión 2 y lo evalúa directamente en aritmética modular.
Antes de que aparezca el primer \(HH\), solo importa un dato del pasado: si el último lanzamiento fue cara o no. Eso reduce todo el proceso a dos estados transitorios.
Usamos dos estados no absorbentes:
\(S\): el último lanzamiento no fue cara, o todavía no ha habido lanzamientos.
\(H\): el último lanzamiento fue cara, pero el proceso aún no terminó.
Desde \(S\), una cruz deja el proceso en \(S\) y una cara lo lleva a \(H\). Desde \(H\), una cruz lo devuelve a \(S\), mientras que una nueva cara produce el primer \(HH\) y detiene el experimento. Por tanto, la matriz de transición transitoria es
$$T=\begin{bmatrix}\frac12 & \frac12\\[4pt]\frac12 & 0\end{bmatrix}.$$
Si
$$v_t=\begin{bmatrix}s_t\\ h_t\end{bmatrix}$$
es el vector de estado después de \(t\) lanzamientos, entonces
$$v_{t+1}=T\,v_t,\qquad v_0=\begin{bmatrix}1\\0\end{bmatrix}.$$
El proceso termina en el lanzamiento \(t+1\) exactamente cuando, tras \(t\) lanzamientos, estamos en el estado \(H\) y el siguiente lanzamiento vuelve a ser cara. Por eso
$$\Pr(M=t+1)=\frac12\,h_t=\frac12\begin{bmatrix}0&1\end{bmatrix}v_t.$$
Sustituyendo \(v_t=T^t v_0\), se obtiene
$$\Pr(M=t+1)=\frac12\begin{bmatrix}0&1\end{bmatrix}T^t\begin{bmatrix}1\\0\end{bmatrix}.$$
Como \(T\) es la mitad de la matriz compañera de Fibonacci, sus potencias satisfacen
$$T^t=\frac{1}{2^t}\begin{bmatrix}F_{t+1}&F_t\\ F_t&F_{t-1}\end{bmatrix}.$$
Por tanto, la distribución exacta queda
$$\Pr(M=m)=\frac{F_{m-1}}{2^m}\qquad (m\ge 2).$$
Los primeros términos \(1/4,1/8,1/8,3/32,\dots\) coinciden con una enumeración directa.
Por definición,
$$P(n)=\sum_{k\ge 1}\Pr(M=kn)=\frac12\sum_{k\ge 1}\begin{bmatrix}0&1\end{bmatrix}T^{kn-1}\begin{bmatrix}1\\0\end{bmatrix}.$$
Usando la forma con Fibonacci, la misma cantidad es
$$P(n)=\sum_{k\ge 1}\frac{F_{kn-1}}{2^{kn}}.$$
Esta serie explica bien la estructura del problema, pero sigue siendo inútil para \(n=10^{18}\). El paso decisivo es reagruparla como una serie geométrica matricial.
Definimos
$$B=T^n,\qquad w=T^{n-1}\begin{bmatrix}1\\0\end{bmatrix}.$$
Entonces
$$T^{kn-1}=T^{(k-1)n}T^{n-1}=B^{k-1}w,$$
de modo que
$$P(n)=\frac12\begin{bmatrix}0&1\end{bmatrix}\left(\sum_{j\ge 0}B^j\right)w.$$
Sobre los números reales, todos los autovalores de \(T\) tienen módulo menor que \(1\), así que la serie converge y
$$\sum_{j\ge 0}B^j=(I-B)^{-1}.$$
Esto produce la fórmula cerrada exacta utilizada por la implementación:
$$\boxed{P(n)=\frac12\begin{bmatrix}0&1\end{bmatrix}(I-T^n)^{-1}T^{n-1}\begin{bmatrix}1\\0\end{bmatrix}.}$$
Si \(P(n)=a/b\) en forma reducida, entonces \(Q(P(n),p)\) no es más que la fracción \(a/b\) interpretada en \(\mathbb F_p\):
$$Q(P(n),p)\equiv a\,b^{-1}\pmod p.$$
No hace falta reconstruir el número racional. Cada división por \(2\) o por el determinante de una matriz 2x2 se reemplaza por un inverso modular. Por eso la misma fórmula matricial puede evaluarse directamente módulo \(10^9+9\).
Para \(n=2\),
$$T^2=\begin{bmatrix}\frac12&\frac14\\[4pt]\frac14&\frac14\end{bmatrix},\qquad T\begin{bmatrix}1\\0\end{bmatrix}=\begin{bmatrix}\frac12\\[4pt]\frac12\end{bmatrix}.$$
Así,
$$I-T^2=\begin{bmatrix}\frac12&-\frac14\\[4pt]-\frac14&\frac34\end{bmatrix}.$$
Al invertir esta matriz y multiplicar por \(T(1,0)^T\), resulta
$$ (I-T^2)^{-1}T\begin{bmatrix}1\\0\end{bmatrix}=\begin{bmatrix}\frac85\\[4pt]\frac65\end{bmatrix}. $$
Tomando la segunda componente y multiplicando por \(1/2\), se obtiene
$$P(2)=\frac12\cdot\frac65=\frac35.$$
Módulo \(109\), el inverso de \(5\) es \(22\), luego
$$Q(P(2),109)\equiv 3\cdot 22\equiv 66\pmod{109}.$$
Otro punto de control pequeño es \(P(3)=9/31\), cuyo residuo módulo \(109\) es \(46\).
Las implementaciones en C++, Python y Java siguen exactamente el mismo plan. Representan la matriz 2x2 en el cuerpo primo \(\mathbb F_{10^9+9}\), donde \(1/2\) se guarda como el inverso modular de \(2\). Así se evita por completo la aritmética en coma flotante.
Después calculan \(T^n\) y \(T^{n-1}\) mediante exponenciación binaria, construyen la matriz \(I-T^n\), la invierten con la fórmula cerrada del determinante 2x2 y multiplican por el vector columna del estado inicial. La componente asociada al estado \(H\) se multiplica una vez más por \(1/2\) para convertirla en la probabilidad de terminar en el siguiente lanzamiento. Como toda la cuenta ya se hace en un cuerpo primo, el residuo final coincide exactamente con \(Q(P(n),10^9+9)\).
Todas las matrices son 2x2, así que cada multiplicación y cada inversión cuestan tiempo constante. El trabajo dominante es la exponenciación binaria necesaria para \(T^n\) y \(T^{n-1}\), lo que requiere \(O(\log n)\) multiplicaciones matriciales. La memoria utilizada es \(O(1)\).
不断抛一枚公平硬币，直到第一次出现连续两个正面。记这个第一次 \(HH\) 中第二个正面的抛掷位置为 \(M\)，因此 \(M\ge 2\)。对正整数 \(n\)，定义 \(P(n)=\Pr(n\mid M)\)，也就是 \(n\) 整除停止时刻的概率。若把 \(P(n)\) 约成最简分数 \(a/b\)，并给定素数 \(p\)，则 \(Q(P(n),p)\) 是满足 \(a\equiv bq\pmod p\) 的最小正整数 \(q\)。
题目要求的是 \(Q(P(10^{18}),10^9+9)\)。因为 \(10^{18}\) 极大，不能直接把所有 \(n\) 的倍数位置逐一求和，所以解法必须把“随机停止时间”改写成一个可以用快速幂处理的 2x2 线性代数问题，并且直接在模素数的有限域里完成计算。
在第一次出现 \(HH\) 之前，历史信息里真正有用的只有一件事：上一掷是不是正面。利用这一点，原问题可以压缩成两个瞬态状态的矩阵递推。
定义两个尚未停止的状态：
\(S\)：上一掷不是正面，或者还没有开始抛。
\(H\)：上一掷是正面，但目前还没有出现过 \(HH\)。
从 \(S\) 出发，再抛出反面仍然留在 \(S\)，抛出正面则转到 \(H\)。从 \(H\) 出发，抛出反面会回到 \(S\)，而再抛出一个正面就会第一次形成 \(HH\)，实验立即结束。因此，只看未停止部分时，转移矩阵为
$$T=\begin{bmatrix}\frac12 & \frac12\\[4pt]\frac12 & 0\end{bmatrix}.$$
若
$$v_t=\begin{bmatrix}s_t\\ h_t\end{bmatrix}$$
表示进行了 \(t\) 次抛掷之后仍未停止时的状态向量，那么满足
$$v_{t+1}=T\,v_t,\qquad v_0=\begin{bmatrix}1\\0\end{bmatrix}.$$
这里初始向量表示“一开始肯定处在状态 \(S\)”。
过程在第 \(t+1\) 次抛掷结束，当且仅当前 \(t\) 次之后处于状态 \(H\)，并且下一次又抛出正面。因此
$$\Pr(M=t+1)=\frac12\,h_t=\frac12\begin{bmatrix}0&1\end{bmatrix}v_t.$$
再把 \(v_t=T^t v_0\) 代入，就得到
$$\Pr(M=t+1)=\frac12\begin{bmatrix}0&1\end{bmatrix}T^t\begin{bmatrix}1\\0\end{bmatrix}.$$
由于 \(T\) 正好是 Fibonacci 伴随矩阵的一半，所以它的幂具有标准形式
$$T^t=\frac{1}{2^t}\begin{bmatrix}F_{t+1}&F_t\\ F_t&F_{t-1}\end{bmatrix}.$$
于是停止时间的精确分布可化成一个非常紧凑的公式：
$$\Pr(M=m)=\frac{F_{m-1}}{2^m}\qquad (m\ge 2).$$
前几项分别是 \(1/4,1/8,1/8,3/32,\dots\)。这和手工枚举长度较短的序列是完全一致的。
按照定义，
$$P(n)=\sum_{k\ge 1}\Pr(M=kn)=\frac12\sum_{k\ge 1}\begin{bmatrix}0&1\end{bmatrix}T^{kn-1}\begin{bmatrix}1\\0\end{bmatrix}.$$
如果把上面的 Fibonacci 形式代进去，还可以写成
$$P(n)=\sum_{k\ge 1}\frac{F_{kn-1}}{2^{kn}}.$$
这个表达式很好地说明了概率结构，但对 \(n=10^{18}\) 来说仍然不能直接算，因为需要涉及无穷多项。真正高效的做法，是把它重新组织成一个矩阵几何级数。
设
$$B=T^n,\qquad w=T^{n-1}\begin{bmatrix}1\\0\end{bmatrix}.$$
那么
$$T^{kn-1}=T^{(k-1)n}T^{n-1}=B^{k-1}w,$$
因此
$$P(n)=\frac12\begin{bmatrix}0&1\end{bmatrix}\left(\sum_{j\ge 0}B^j\right)w.$$
在实数意义下，\(T\) 的所有特征值绝对值都小于 \(1\)，于是该几何级数收敛，并且有
$$\sum_{j\ge 0}B^j=(I-B)^{-1}.$$
这样就得到实现中真正使用的闭式：
$$\boxed{P(n)=\frac12\begin{bmatrix}0&1\end{bmatrix}(I-T^n)^{-1}T^{n-1}\begin{bmatrix}1\\0\end{bmatrix}.}$$
这一步非常关键，因为一旦把问题压缩成 \(T^n\)、\(T^{n-1}\) 和一个 2x2 矩阵求逆，计算量就只剩下对数级的快速幂。
若 \(P(n)=a/b\) 是最简分数，那么
$$Q(P(n),p)\equiv a\,b^{-1}\pmod p.$$
也就是说，\(Q\) 只是把这个有理数看成有限域 \(\mathbb F_p\) 中的元素。于是计算时根本不需要先把 \(a\) 和 \(b\) 写出来；所有“除以 \(2\)”或“除以 2x2 行列式”的动作，都可以直接改成取模逆元。这正是实现能够直接在模 \(10^9+9\) 下完成全部运算的原因。
取 \(n=2\) 时，先算出
$$T^2=\begin{bmatrix}\frac12&\frac14\\[4pt]\frac14&\frac14\end{bmatrix},\qquad T\begin{bmatrix}1\\0\end{bmatrix}=\begin{bmatrix}\frac12\\[4pt]\frac12\end{bmatrix}.$$
于是
$$I-T^2=\begin{bmatrix}\frac12&-\frac14\\[4pt]-\frac14&\frac34\end{bmatrix}.$$
把这个矩阵求逆，再乘以 \(T(1,0)^T\)，得到
$$ (I-T^2)^{-1}T\begin{bmatrix}1\\0\end{bmatrix}=\begin{bmatrix}\frac85\\[4pt]\frac65\end{bmatrix}. $$
取第二个分量，再乘上最后那个 \(1/2\)，便有
$$P(2)=\frac12\cdot\frac65=\frac35.$$
若模数取 \(109\)，则 \(5^{-1}\equiv 22\pmod{109}\)，所以
$$Q(P(2),109)\equiv 3\cdot 22\equiv 66\pmod{109}.$$
这和小规模校验完全一致。类似地，\(P(3)=9/31\)，在模 \(109\) 下对应的结果是 \(46\)。
C++、Python 和 Java 实现采用的是同一套思路。它们都在素域 \(\mathbb F_{10^9+9}\) 中表示上面的 2x2 矩阵，其中 \(1/2\) 不是用浮点数，而是直接用 \(2\) 的模逆元来表示。
随后，实现用二进制快速幂分别求出 \(T^n\) 和 \(T^{n-1}\)，构造矩阵 \(I-T^n\)，再用 2x2 矩阵的显式行列式公式求逆。把逆矩阵乘到起始列向量之后，就能得到一个两维结果向量；取其中表示状态 \(H\) 的分量，再乘一次 \(1/2\)，就得到“下一次抛掷正好结束”的概率。由于整个过程始终都在模素数的有限域里进行，最后输出的元素恰好就是题目定义的 \(Q(P(n),10^9+9)\)。
所有矩阵都是 2x2，因此单次矩阵乘法和单次求逆都只需要常数时间。真正的主要开销是对 \(T^n\) 和 \(T^{n-1}\) 做快速幂，这需要 \(O(\log n)\) 次矩阵乘法。额外空间始终是 \(O(1)\)。
Честную монету бросают до тех пор, пока впервые не появятся два орла подряд. Пусть \(M\) — номер второго броска в этом первом блоке \(HH\), так что \(M\ge 2\). Для положительного целого \(n\) определим \(P(n)=\Pr(n\mid M)\), то есть вероятность того, что \(n\) делит момент остановки. Если \(P(n)=a/b\) в несократимом виде и \(p\) — простое число, то \(Q(P(n),p)\) — это наименьший положительный остаток \(q\), удовлетворяющий сравнению \(a\equiv bq\pmod p\).
Нужно найти \(Q(P(10^{18}),10^9+9)\). Поскольку \(10^{18}\) слишком велико, напрямую суммировать вероятности по всем кратным \(n\) нельзя. Поэтому решение переводит задачу о времени остановки в задачу линейной алгебры с матрицей 2x2 и выполняет все вычисления сразу по модулю простого числа.
До первого появления \(HH\) нужно помнить только одну вещь: был ли последний бросок орлом. Это позволяет свести весь процесс к двум транзиентным состояниям.
Используем два не поглощающих состояния:
\(S\): последний бросок не был орлом, либо бросков еще не было.
\(H\): последний бросок был орлом, но процесс еще не завершился.
Из \(S\) решка оставляет нас в \(S\), а орел переводит в \(H\). Из \(H\) решка возвращает в \(S\), а следующий орел впервые образует \(HH\) и завершает эксперимент. Поэтому матрица переходов по транзиентным состояниям равна
$$T=\begin{bmatrix}\frac12 & \frac12\\[4pt]\frac12 & 0\end{bmatrix}.$$
Если
$$v_t=\begin{bmatrix}s_t\\ h_t\end{bmatrix}$$
— вектор состояний после \(t\) бросков, то
$$v_{t+1}=T\,v_t,\qquad v_0=\begin{bmatrix}1\\0\end{bmatrix}.$$
Процесс заканчивается на броске \(t+1\) тогда и только тогда, когда после \(t\) бросков он находится в состоянии \(H\), а следующий бросок снова дает орла. Следовательно,
$$\Pr(M=t+1)=\frac12\,h_t=\frac12\begin{bmatrix}0&1\end{bmatrix}v_t.$$
Подставляя \(v_t=T^t v_0\), получаем
$$\Pr(M=t+1)=\frac12\begin{bmatrix}0&1\end{bmatrix}T^t\begin{bmatrix}1\\0\end{bmatrix}.$$
Поскольку \(T\) есть половина стандартной матрицы Фибоначчи, его степени имеют вид
$$T^t=\frac{1}{2^t}\begin{bmatrix}F_{t+1}&F_t\\ F_t&F_{t-1}\end{bmatrix}.$$
Значит, точная формула для распределения такова:
$$\Pr(M=m)=\frac{F_{m-1}}{2^m}\qquad (m\ge 2).$$
Первые значения \(1/4,1/8,1/8,3/32,\dots\) совпадают с прямым перебором коротких последовательностей.
По определению
$$P(n)=\sum_{k\ge 1}\Pr(M=kn)=\frac12\sum_{k\ge 1}\begin{bmatrix}0&1\end{bmatrix}T^{kn-1}\begin{bmatrix}1\\0\end{bmatrix}.$$
Используя форму через числа Фибоначчи, то же самое можно записать как
$$P(n)=\sum_{k\ge 1}\frac{F_{kn-1}}{2^{kn}}.$$
Эта запись наглядна, но при \(n=10^{18}\) по-прежнему непригодна для прямого вычисления. Поэтому ряд нужно перегруппировать в матрическую геометрическую прогрессию.
Положим
$$B=T^n,\qquad w=T^{n-1}\begin{bmatrix}1\\0\end{bmatrix}.$$
Тогда
$$T^{kn-1}=T^{(k-1)n}T^{n-1}=B^{k-1}w,$$
и потому
$$P(n)=\frac12\begin{bmatrix}0&1\end{bmatrix}\left(\sum_{j\ge 0}B^j\right)w.$$
Над вещественными числами все собственные значения \(T\) по модулю меньше \(1\), поэтому ряд сходится и
$$\sum_{j\ge 0}B^j=(I-B)^{-1}.$$
Отсюда получается точная формула, которую и реализуют программы:
$$\boxed{P(n)=\frac12\begin{bmatrix}0&1\end{bmatrix}(I-T^n)^{-1}T^{n-1}\begin{bmatrix}1\\0\end{bmatrix}.}$$
Если \(P(n)=a/b\) в несократимом виде, то \(Q(P(n),p)\) — это просто дробь \(a/b\), интерпретированная в поле \(\mathbb F_p\):
$$Q(P(n),p)\equiv a\,b^{-1}\pmod p.$$
Поэтому саму рациональную дробь восстанавливать не нужно. Любое деление на \(2\) или на определитель матрицы 2x2 заменяется взятием обратного элемента по модулю. Именно так одна и та же матричная формула напрямую вычисляется по модулю \(10^9+9\).
При \(n=2\) имеем
$$T^2=\begin{bmatrix}\frac12&\frac14\\[4pt]\frac14&\frac14\end{bmatrix},\qquad T\begin{bmatrix}1\\0\end{bmatrix}=\begin{bmatrix}\frac12\\[4pt]\frac12\end{bmatrix}.$$
Следовательно,
$$I-T^2=\begin{bmatrix}\frac12&-\frac14\\[4pt]-\frac14&\frac34\end{bmatrix}.$$
После обращения этой матрицы и умножения на \(T(1,0)^T\) получаем
$$ (I-T^2)^{-1}T\begin{bmatrix}1\\0\end{bmatrix}=\begin{bmatrix}\frac85\\[4pt]\frac65\end{bmatrix}. $$
Берем вторую компоненту и умножаем на \(1/2\):
$$P(2)=\frac12\cdot\frac65=\frac35.$$
По модулю \(109\) обратный к \(5\) равен \(22\), поэтому
$$Q(P(2),109)\equiv 3\cdot 22\equiv 66\pmod{109}.$$
Еще одна маленькая проверка: \(P(3)=9/31\), а соответствующий остаток по модулю \(109\) равен \(46\).
Реализации на C++, Python и Java выполняют один и тот же алгоритм. Они представляют матрицу 2x2 в поле \(\mathbb F_{10^9+9}\), где значение \(1/2\) заменено на обратный к \(2\) элемент по модулю, так что вычисления с плавающей точкой вообще не нужны.
Далее с помощью бинарного возведения в степень вычисляются \(T^n\) и \(T^{n-1}\), строится матрица \(I-T^n\), затем она обращается по явной формуле для матрицы 2x2. Результат умножается на начальный столбец состояния, после чего выбирается компонента, соответствующая состоянию \(H\), и еще раз умножается на \(1/2\). Поскольку все действия изначально происходят в простом поле, финальный элемент и есть искомое значение \(Q(P(n),10^9+9)\).
Все матрицы имеют размер 2x2, поэтому умножение и обращение стоят константное время. Основная работа — бинарное возведение в степень для \(T^n\) и \(T^{n-1}\), то есть \(O(\log n)\) матричных умножений. Память используется в объеме \(O(1)\).
نرمي قطعة نقد عادلة حتى يظهر لأول مرة زوج متتالٍ من الوجهين \(HH\). نرمز بـ \(M\) إلى موضع الرمية الثانية داخل أول ظهور لهذا الزوج، ولذلك يكون \(M\ge 2\). لكل عدد صحيح موجب \(n\)، نعرّف \(P(n)=\Pr(n\mid M)\)، أي احتمال أن يقسم \(n\) زمن التوقف. وإذا كتبنا \(P(n)=a/b\) في أبسط صورة، وكان \(p\) عددًا أوليًا، فإن \(Q(P(n),p)\) هو أصغر باقٍ موجب \(q\) يحقق \(a\equiv bq\pmod p\).
المطلوب هو حساب \(Q(P(10^{18}),10^9+9)\). وبما أن \(10^{18}\) ضخم جدًا، فلا يمكن جمع الاحتمالات على جميع مضاعفات \(n\) مباشرة. لذلك تحوّل الحل المسألة إلى نموذج خطي بمصفوفة \(2\times 2\)، ثم يجري الحساب كله داخل حسابيات معيارية على حقل أولي.
قبل ظهور \(HH\) لأول مرة، لا نحتاج من التاريخ السابق إلا معلومة واحدة: هل كانت الرمية الأخيرة وجهًا أم لا. وهذه الملاحظة تختزل العملية كلها إلى حالتين عابرتين فقط.
نستخدم حالتين غير ماصتين:
\(S\): الرمية الأخيرة ليست وجهًا، أو لم تبدأ الرميات بعد.
\(H\): الرمية الأخيرة كانت وجهًا، لكن \(HH\) لم يظهر بعد.
من الحالة \(S\)، إذا ظهرت كتابة نبقى في \(S\)، وإذا ظهر وجه ننتقل إلى \(H\). ومن الحالة \(H\)، إذا ظهرت كتابة نعود إلى \(S\)، أما إذا ظهر وجه آخر فإن أول \(HH\) يتكوّن وتنتهي العملية فورًا. لذلك تكون مصفوفة الانتقال على الحالات العابرة
$$T=\begin{bmatrix}\frac12 & \frac12\\[4pt]\frac12 & 0\end{bmatrix}.$$
وإذا كان
$$v_t=\begin{bmatrix}s_t\\ h_t\end{bmatrix}$$
هو متجه الحالة بعد \(t\) رميات، فإن
$$v_{t+1}=T\,v_t,\qquad v_0=\begin{bmatrix}1\\0\end{bmatrix}.$$
تنتهي العملية عند الرمية \(t+1\) تحديدًا إذا كنا بعد \(t\) رميات في الحالة \(H\)، ثم جاءت الرمية التالية وجهًا مرة أخرى. ومن ثم
$$\Pr(M=t+1)=\frac12\,h_t=\frac12\begin{bmatrix}0&1\end{bmatrix}v_t.$$
وبالتعويض عن \(v_t=T^t v_0\) نحصل على
$$\Pr(M=t+1)=\frac12\begin{bmatrix}0&1\end{bmatrix}T^t\begin{bmatrix}1\\0\end{bmatrix}.$$
ولأن \(T\) يساوي نصف مصفوفة فيبوناتشي القياسية، فإن قواه تأخذ الشكل
$$T^t=\frac{1}{2^t}\begin{bmatrix}F_{t+1}&F_t\\ F_t&F_{t-1}\end{bmatrix}.$$
ومن هنا ينتج التوزيع الدقيق
$$\Pr(M=m)=\frac{F_{m-1}}{2^m}\qquad (m\ge 2).$$
وأول القيم هي \(1/4,1/8,1/8,3/32,\dots\)، وهي متوافقة تمامًا مع العد المباشر للحالات القصيرة.
بحسب التعريف،
$$P(n)=\sum_{k\ge 1}\Pr(M=kn)=\frac12\sum_{k\ge 1}\begin{bmatrix}0&1\end{bmatrix}T^{kn-1}\begin{bmatrix}1\\0\end{bmatrix}.$$
وباستخدام صيغة فيبوناتشي يمكن كتابة ذلك أيضًا على الصورة
$$P(n)=\sum_{k\ge 1}\frac{F_{kn-1}}{2^{kn}}.$$
هذا التعبير يوضح البنية الرياضية للمسألة، لكنه لا يزال غير عملي عندما يكون \(n=10^{18}\). والخطوة الحاسمة هي إعادة ترتيب هذا المجموع اللانهائي على هيئة متسلسلة هندسية للمصفوفات.
لنضع
$$B=T^n,\qquad w=T^{n-1}\begin{bmatrix}1\\0\end{bmatrix}.$$
عندئذٍ
$$T^{kn-1}=T^{(k-1)n}T^{n-1}=B^{k-1}w,$$
ومن ثم
$$P(n)=\frac12\begin{bmatrix}0&1\end{bmatrix}\left(\sum_{j\ge 0}B^j\right)w.$$
وعلى الأعداد الحقيقية، كل القيم الذاتية لـ \(T\) أصغر من \(1\) في القيمة المطلقة، لذا تتقارب السلسلة ويكون
$$\sum_{j\ge 0}B^j=(I-B)^{-1}.$$
وبذلك نحصل على الصيغة المغلقة الدقيقة التي تعتمدها التطبيقات:
$$\boxed{P(n)=\frac12\begin{bmatrix}0&1\end{bmatrix}(I-T^n)^{-1}T^{n-1}\begin{bmatrix}1\\0\end{bmatrix}.}$$
إذا كان \(P(n)=a/b\) في أبسط صورة، فإن
$$Q(P(n),p)\equiv a\,b^{-1}\pmod p.$$
أي أن \(Q\) ليس إلا تمثيل هذا الكسر داخل الحقل \(\mathbb F_p\). لذلك لا حاجة إلى إعادة بناء الكسر نفسه بشكل صريح. كل عملية قسمة على \(2\) أو على محدد مصفوفة \(2\times 2\) تُستبدل بأخذ المعكوس الضربي المعياري. ولهذا تعمل الصيغة نفسها مباشرة modulo \(10^9+9\).
عندما \(n=2\)، نجد أن
$$T^2=\begin{bmatrix}\frac12&\frac14\\[4pt]\frac14&\frac14\end{bmatrix},\qquad T\begin{bmatrix}1\\0\end{bmatrix}=\begin{bmatrix}\frac12\\[4pt]\frac12\end{bmatrix}.$$
ومن ثم
$$I-T^2=\begin{bmatrix}\frac12&-\frac14\\[4pt]-\frac14&\frac34\end{bmatrix}.$$
وبعد عكس هذه المصفوفة وضربها في \(T(1,0)^T\)، نحصل على
$$ (I-T^2)^{-1}T\begin{bmatrix}1\\0\end{bmatrix}=\begin{bmatrix}\frac85\\[4pt]\frac65\end{bmatrix}. $$
نأخذ المركبة الثانية ثم نضرب في \(1/2\)، فنحصل على
$$P(2)=\frac12\cdot\frac65=\frac35.$$
وبترديد \(109\)، يكون معكوس \(5\) هو \(22\)، ولذلك
$$Q(P(2),109)\equiv 3\cdot 22\equiv 66\pmod{109}.$$
وهناك فحص صغير آخر هو \(P(3)=9/31\)، والذي يعطي الباقي \(46\) modulo \(109\).
تتبع تطبيقات C++ وPython وJava الخطة نفسها تمامًا. فهي تمثل المصفوفة \(2\times 2\) داخل الحقل الأولي \(\mathbb F_{10^9+9}\)، حيث يُخزَّن \(1/2\) على أنه المعكوس المعياري للعدد \(2\)، وبذلك لا تُستخدم الأعداد العائمة إطلاقًا.
بعد ذلك تُحسب \(T^n\) و\(T^{n-1}\) باستعمال الرفع السريع للأس، ثم تُبنى المصفوفة \(I-T^n\)، وتُعكس بصيغة المحدد الخاصة بالمصفوفات \(2\times 2\). ثم يُضرب الناتج في متجه حالة البداية، وتُؤخذ المركبة الموافقة للحالة \(H\)، وتُضرب أخيرًا في \(1/2\) لتحويلها إلى احتمال الانتهاء في الرمية التالية. وبما أن جميع العمليات تتم أصلًا داخل حقل أولي، فإن الباقي النهائي الناتج هو بالضبط \(Q(P(n),10^9+9)\).
كل المصفوفات هنا من الحجم \(2\times 2\)، لذلك فإن كل عملية ضرب أو عكس تتم في زمن ثابت. أما الكلفة الأساسية فتأتي من الرفع الثنائي السريع لحساب \(T^n\) و\(T^{n-1}\)، وهو ما يحتاج إلى \(O(\log n)\) عملية ضرب مصفوفي. واستهلاك الذاكرة ثابت \(O(1)\).