In this cyclic pairwise coin-tossing game, the players are visited in a fixed cycle, each round is decided by a fair coin, and a player becomes champion as soon as that same player wins two consecutive rounds in which the player appears. Let \(P_n(k)\) be the probability that player \(k\) wins when there are \(n\) players, and let \(M_n(k)\) be the product of numerator and denominator after \(P_n(k)\) is reduced to lowest terms. The required value is the last eight digits of
$$M_{10^8+7}(10^4+7).$$
The implementations use a standard reduction of the game to a pattern-matching problem in a fair coin sequence. Once that reduction is made, the rest is an exercise in counting first occurrences and simplifying an arithmetico-geometric series.
Let \(T\) be the position where the pattern \(RL\) appears for the first time in an infinite fair-coin sequence. In the standard reformulation of the game, the decisive moment that produces the champion is exactly this first \(RL\), and the winning label depends only on the round number modulo \(n\).
Therefore player \(k\) wins exactly when
$$T=k+jn$$
for some integer \(j\ge 0\). So the whole problem becomes: compute the distribution of \(T\), then sum the probabilities over one residue class modulo \(n\).
Fix \(t\ge 2\). For the first \(RL\) to end exactly at round \(t\), the first \(t-1\) symbols must contain no earlier \(RL\), the symbol at position \(t-1\) must be \(R\), and the symbol at position \(t\) must be \(L\).
A binary word with no \(RL\) must have all \(L\)'s first and all \(R\)'s afterward, so every admissible prefix of length \(t-1\) has the form
$$L^aR^{\,t-1-a}\qquad (0\le a\le t-2).$$
There are exactly \(t-1\) such prefixes. Since all length-\(t\) coin strings have probability \(2^{-t}\), we get
$$\Pr(T=t)=\frac{t-1}{2^t}\qquad (t\ge 2).$$
Because player labels repeat every \(n\) rounds, player \(k\) collects exactly the terms with \(t\equiv k\pmod n\). Hence
$$P_n(k)=\sum_{j\ge 0}\Pr(T=k+jn)=\sum_{j\ge 0}\frac{k+jn-1}{2^{k+jn}}.$$
This is the key series used by all three implementations.
Set
$$q=2^{-n}.$$
Then factor out \(2^{-k}\):
$$P_n(k)=2^{-k}\sum_{j\ge 0}(k-1+jn)q^j.$$
Now use the standard identities
$$\sum_{j\ge 0}q^j=\frac{1}{1-q},\qquad \sum_{j\ge 0}jq^j=\frac{q}{(1-q)^2}.$$
Substituting them gives
$$P_n(k)=2^{-k}\left(\frac{k-1}{1-q}+\frac{nq}{(1-q)^2}\right).$$
Let
$$X=2^n-1.$$
Since \(q=2^{-n}\), we have
$$\frac{1}{1-q}=\frac{2^n}{X},\qquad \frac{q}{(1-q)^2}=\frac{2^n}{X^2}.$$
Therefore
$$P_n(k)=2^{-k}\left(\frac{(k-1)2^n}{X}+\frac{n2^n}{X^2}\right)=\frac{2^{n-k}\big((k-1)X+n\big)}{X^2}.$$
Replacing \(X\) by \(2^n-1\) yields the compact form
$$P_n(k)=\frac{2^{n-k}\big((k-1)2^n+(n-k+1)\big)}{(2^n-1)^2}.$$
Write
$$Y=(k-1)2^n+(n-k+1).$$
The unreduced fraction is
$$P_n(k)=\frac{2^{n-k}Y}{X^2},\qquad X=2^n-1.$$
Because \(X\) is odd, the factor \(2^{n-k}\) never cancels with the denominator. Any reduction can only come from \(\gcd(Y,X^2)\). Modulo \(X\), we have
$$Y\equiv (k-1)+(n-k+1)\equiv n\pmod X,$$
so
$$\gcd(Y,X)=\gcd(n,X).$$
For the target value \(n=10^8+7\), \(n\) is prime and Fermat's little theorem gives \(2^n\equiv 2\pmod n\). Hence
$$2^n-1\equiv 1\pmod n,$$
which implies \(\gcd(n,2^n-1)=1\), so no reduction is needed for the target instance. Therefore
$$M_n(k)\equiv 2^{n-k}\big((k-1)2^n+(n-k+1)\big)(2^n-1)^2\pmod{10^8}.$$
This example shows why the reduction step matters in general, even though the target instance is already coprime.
From the closed form,
$$P_6(2)=\frac{2^{6-2}\big((2-1)2^6+(6-2+1)\big)}{(2^6-1)^2}=\frac{16\cdot 69}{63^2}=\frac{1104}{3969}.$$
Now divide numerator and denominator by \(3\):
$$P_6(2)=\frac{368}{1323}.$$
So
$$M_6(2)=368\cdot 1323=486864,$$
which matches the small checkpoint used by the exact validation logic.
The C++, Python, and Java implementations do not simulate the game. Instead, they evaluate the closed formula directly modulo \(10^8\), because only the last eight digits are required.
First they compute \(2^n\bmod 10^8\) and \(2^{n-k}\bmod 10^8\) using binary modular exponentiation. Next they build the two closed-form factors \(2^n-1\) and \((k-1)2^n+(n-k+1)\) modulo \(10^8\). Then they multiply
$$2^{n-k}\cdot \big((k-1)2^n+(n-k+1)\big)\cdot (2^n-1)\cdot (2^n-1)\pmod{10^8}.$$
One implementation also verifies small exact examples and checks the coprimality condition that justifies skipping reduction for the target input, while the streamlined implementations rely on the fixed target parameters. The final value is formatted as an eight-digit string, including leading zeros if necessary.
The dominant work is modular exponentiation, which takes \(O(\log n)\) time. All other arithmetic is constant-time modular multiplication and addition on machine-size integers, so the total memory usage is \(O(1)\).
In diesem zyklischen Paarspiel werden die Spieler in fester Reihenfolge durchlaufen, jede Runde durch einen fairen Münzwurf entschieden, und ein Spieler ist genau dann Gesamtsieger, wenn derselbe Spieler zwei aufeinanderfolgende Runden gewinnt, an denen er beteiligt ist. Sei \(P_n(k)\) die Gewinnwahrscheinlichkeit von Spieler \(k\) bei \(n\) Spielern, und sei \(M_n(k)\) das Produkt aus Zähler und Nenner, nachdem \(P_n(k)\) vollständig gekürzt wurde. Gesucht sind die letzten acht Ziffern von
$$M_{10^8+7}(10^4+7).$$
Die Implementierungen verwenden eine Standardreduktion des Spiels auf ein Musterproblem in einer fairen Münzfolge. Danach bleibt nur noch, die erste Auftretenswahrscheinlichkeit eines bestimmten Musters zu zählen und eine arithmetisch-geometrische Reihe zu vereinfachen.
Sei \(T\) die Position, an der das Muster \(RL\) in einer unendlichen fairen Münzfolge zum ersten Mal endet. In der verwendeten Umformulierung des Spiels ist genau dieses erste \(RL\) der entscheidende Moment, und das Gewinnerlabel hängt nur von der Rundennummer modulo \(n\) ab.
Spieler \(k\) gewinnt also genau dann, wenn
$$T=k+jn$$
für ein \(j\ge 0\) gilt. Das gesamte Problem reduziert sich damit auf die Verteilung von \(T\) und auf eine Summation über eine feste Restklasse modulo \(n\).
Fixiere \(t\ge 2\). Damit das erste \(RL\) genau in Runde \(t\) endet, dürfen die ersten \(t-1\) Symbole kein früheres \(RL\) enthalten, das Symbol an Position \(t-1\) muss \(R\) sein, und das Symbol an Position \(t\) muss \(L\) sein.
Ein Binärwort ohne \(RL\) muss zuerst nur \(L\)'s und danach nur \(R\)'s enthalten. Jeder zulässige Präfix der Länge \(t-1\) hat also die Form
$$L^aR^{\,t-1-a}\qquad (0\le a\le t-2).$$
Davon gibt es genau \(t-1\). Da jede Münzfolge der Länge \(t\) die Wahrscheinlichkeit \(2^{-t}\) hat, folgt
$$\Pr(T=t)=\frac{t-1}{2^t}\qquad (t\ge 2).$$
Da sich die Spielerlabels alle \(n\) Runden wiederholen, sammelt Spieler \(k\) genau die Terme mit \(t\equiv k\pmod n\). Daher gilt
$$P_n(k)=\sum_{j\ge 0}\Pr(T=k+jn)=\sum_{j\ge 0}\frac{k+jn-1}{2^{k+jn}}.$$
Genau diese Reihe steht im Zentrum aller drei Implementierungen.
Setze
$$q=2^{-n}.$$
Dann kann man \(2^{-k}\) ausklammern:
$$P_n(k)=2^{-k}\sum_{j\ge 0}(k-1+jn)q^j.$$
Nun verwenden wir die Standardformeln
$$\sum_{j\ge 0}q^j=\frac{1}{1-q},\qquad \sum_{j\ge 0}jq^j=\frac{q}{(1-q)^2}.$$
Einsetzen liefert
$$P_n(k)=2^{-k}\left(\frac{k-1}{1-q}+\frac{nq}{(1-q)^2}\right).$$
Definiere
$$X=2^n-1.$$
Wegen \(q=2^{-n}\) gilt
$$\frac{1}{1-q}=\frac{2^n}{X},\qquad \frac{q}{(1-q)^2}=\frac{2^n}{X^2}.$$
Also
$$P_n(k)=2^{-k}\left(\frac{(k-1)2^n}{X}+\frac{n2^n}{X^2}\right)=\frac{2^{n-k}\big((k-1)X+n\big)}{X^2}.$$
Mit \(X=2^n-1\) erhält man die kompakte Endform
$$P_n(k)=\frac{2^{n-k}\big((k-1)2^n+(n-k+1)\big)}{(2^n-1)^2}.$$
Schreibe
$$Y=(k-1)2^n+(n-k+1).$$
Dann lautet der ungekürzte Bruch
$$P_n(k)=\frac{2^{n-k}Y}{X^2},\qquad X=2^n-1.$$
Da \(X\) ungerade ist, kann der Faktor \(2^{n-k}\) nie mit dem Nenner kürzen. Eine mögliche Kürzung kann nur aus \(\gcd(Y,X^2)\) kommen. Modulo \(X\) gilt
$$Y\equiv (k-1)+(n-k+1)\equiv n\pmod X,$$
also
$$\gcd(Y,X)=\gcd(n,X).$$
Für den Zielwert \(n=10^8+7\) ist \(n\) prim, und nach dem kleinen Satz von Fermat gilt \(2^n\equiv 2\pmod n\). Daher
$$2^n-1\equiv 1\pmod n,$$
woraus \(\gcd(n,2^n-1)=1\) folgt. Für den Zielparameter ist also keine Kürzung nötig. Damit ergibt sich
$$M_n(k)\equiv 2^{n-k}\big((k-1)2^n+(n-k+1)\big)(2^n-1)^2\pmod{10^8}.$$
Dieses Beispiel zeigt, warum das Kürzen im allgemeinen Fall wichtig ist, obwohl der Zielparameter bereits teilerfremd ist.
Aus der geschlossenen Formel folgt
$$P_6(2)=\frac{2^{6-2}\big((2-1)2^6+(6-2+1)\big)}{(2^6-1)^2}=\frac{16\cdot 69}{63^2}=\frac{1104}{3969}.$$
Nun kürzen wir mit \(3\):
$$P_6(2)=\frac{368}{1323}.$$
Daher
$$M_6(2)=368\cdot 1323=486864,$$
genau der kleine Kontrollwert aus der exakten Validierung.
Die C++-, Python- und Java-Implementierungen simulieren das Spiel nicht. Stattdessen werten sie die geschlossene Formel direkt modulo \(10^8\) aus, weil nur die letzten acht Ziffern gebraucht werden.
Zuerst werden \(2^n\bmod 10^8\) und \(2^{n-k}\bmod 10^8\) mit binärer modularer Exponentiation berechnet. Danach werden die beiden Faktoren \(2^n-1\) und \((k-1)2^n+(n-k+1)\) modulo \(10^8\) aufgebaut. Anschließend multipliziert der Code
$$2^{n-k}\cdot \big((k-1)2^n+(n-k+1)\big)\cdot (2^n-1)\cdot (2^n-1)\pmod{10^8}.$$
Eine Implementierung prüft zusätzlich kleine exakte Beispiele und die Teilerfremdheit, die das Überspringen einer Kürzung für den Zielparameter rechtfertigt; die schlankeren Implementierungen verlassen sich darauf, dass die Zieleingaben fest vorgegeben sind. Zum Schluss wird das Ergebnis als achtstellige Zeichenkette mit führenden Nullen ausgegeben.
Die dominante Arbeit ist die modulare Exponentiation mit Laufzeit \(O(\log n)\). Alle übrigen Schritte sind konstante viele modulare Multiplikationen und Additionen auf Maschinenwortgröße, daher beträgt der Speicherverbrauch insgesamt \(O(1)\).
Bu çevrimsel ikili para oyunda oyuncular sabit bir döngü içinde sırayla gelir, her tur adil bir para atışıyla belirlenir ve bir oyuncu, yer aldığı iki ardışık turu da kazandığında oyunun şampiyonu olur. \(n\) oyunculu durumda \(k\). oyuncunun kazanma olasılığına \(P_n(k)\), bu olasılık en sade kesre indirildiğinde pay ile paydanın çarpımına da \(M_n(k)\) diyelim. İstenen değer
$$M_{10^8+7}(10^4+7)$$
ifadesinin son sekiz basamağıdır.
Uygulamalar oyunu doğrudan simüle etmek yerine, onu adil bir para dizisinde belirli bir desenin ilk kez görülmesi problemine indirger. Geriye kalan kısım ise ilk görülme olasılığını saymak ve ortaya çıkan aritmetik-geometrik seriyi kapalı forma dönüştürmektir.
\(T\), sonsuz bir adil para dizisinde \(RL\) deseninin ilk kez bittiği konum olsun. Uygulamaların kullandığı standart yeniden yazımda şampiyonu belirleyen an tam olarak bu ilk \(RL\) anıdır ve kazanan oyuncunun etiketi yalnızca tur numarasının \(n\)'ye göre kalanına bağlıdır.
Bu yüzden \(k\). oyuncu ancak ve ancak
$$T=k+jn$$
şeklinde bir değer için kazanır; burada \(j\ge 0\). Böylece bütün problem \(T\)'nin dağılımını bulup bunu \(n\)'ye göre tek bir kongruans sınıfı üzerinde toplamaya dönüşür.
\(t\ge 2\) sabit olsun. İlk \(RL\)'nin tam \(t\). turda bitmesi için, ilk \(t-1\) sembolde daha erken bir \(RL\) olmamalı, \(t-1\). konumdaki sembol \(R\) olmalı ve \(t\). konumdaki sembol \(L\) olmalıdır.
İçinde \(RL\) geçmeyen bir ikili kelime önce yalnızca \(L\)'lerden, sonra yalnızca \(R\)'lerden oluşabilir. Bu yüzden uzunluğu \(t-1\) olan her uygun önek
$$L^aR^{\,t-1-a}\qquad (0\le a\le t-2)$$
biçimindedir.
Böyle tam \(t-1\) tane önek vardır. Uzunluğu \(t\) olan her para dizisinin olasılığı \(2^{-t}\) olduğundan
$$\Pr(T=t)=\frac{t-1}{2^t}\qquad (t\ge 2)$$
elde edilir.
Oyuncu etiketleri her \(n\) turda bir tekrar ettiği için, \(k\). oyuncu tam olarak \(t\equiv k\pmod n\) olan terimleri toplar. Dolayısıyla
$$P_n(k)=\sum_{j\ge 0}\Pr(T=k+jn)=\sum_{j\ge 0}\frac{k+jn-1}{2^{k+jn}}$$
olur. Üç uygulamanın da çıkış noktası bu seridir.
Şunu tanımlayalım:
$$q=2^{-n}.$$
O zaman \(2^{-k}\) ortak çarpan olarak dışarı alınabilir:
$$P_n(k)=2^{-k}\sum_{j\ge 0}(k-1+jn)q^j.$$
Şimdi standart özdeşlikleri kullanalım:
$$\sum_{j\ge 0}q^j=\frac{1}{1-q},\qquad \sum_{j\ge 0}jq^j=\frac{q}{(1-q)^2}.$$
Bunlar yerine yazılınca
$$P_n(k)=2^{-k}\left(\frac{k-1}{1-q}+\frac{nq}{(1-q)^2}\right)$$
elde edilir.
Şunu yazalım:
$$X=2^n-1.$$
\(q=2^{-n}\) olduğu için
$$\frac{1}{1-q}=\frac{2^n}{X},\qquad \frac{q}{(1-q)^2}=\frac{2^n}{X^2}$$
olur. Böylece
$$P_n(k)=2^{-k}\left(\frac{(k-1)2^n}{X}+\frac{n2^n}{X^2}\right)=\frac{2^{n-k}\big((k-1)X+n\big)}{X^2}.$$
\(X=2^n-1\) yerine konursa kompakt form şudur:
$$P_n(k)=\frac{2^{n-k}\big((k-1)2^n+(n-k+1)\big)}{(2^n-1)^2}.$$
Şöyle tanımlayalım:
$$Y=(k-1)2^n+(n-k+1).$$
İndirgenmemiş kesir
$$P_n(k)=\frac{2^{n-k}Y}{X^2},\qquad X=2^n-1$$
şeklindedir. \(X\) tek sayı olduğu için \(2^{n-k}\) çarpanı paydadan asla sadeleşmez. Olası sadeleşme yalnızca \(\gcd(Y,X^2)\) üzerinden gelir. Mod \(X\) altında
$$Y\equiv (k-1)+(n-k+1)\equiv n\pmod X$$
olduğundan
$$\gcd(Y,X)=\gcd(n,X)$$
sonucuna ulaşılır.
Hedefteki \(n=10^8+7\) asal sayıdır. Fermat'nın küçük teoremine göre \(2^n\equiv 2\pmod n\), dolayısıyla
$$2^n-1\equiv 1\pmod n.$$
Buradan \(\gcd(n,2^n-1)=1\) çıkar; yani hedef örnekte ek sadeleştirme yoktur. O halde
$$M_n(k)\equiv 2^{n-k}\big((k-1)2^n+(n-k+1)\big)(2^n-1)^2\pmod{10^8}.$$
Bu örnek, hedef girişte ek sadeleştirme gerekmese bile genel durumda sadeleştirmenin neden önemli olduğunu gösterir.
Kapalı formdan
$$P_6(2)=\frac{2^{6-2}\big((2-1)2^6+(6-2+1)\big)}{(2^6-1)^2}=\frac{16\cdot 69}{63^2}=\frac{1104}{3969}$$
bulunur. Şimdi pay ve paydayı \(3\)'e böleriz:
$$P_6(2)=\frac{368}{1323}.$$
Dolayısıyla
$$M_6(2)=368\cdot 1323=486864,$$
ve bu değer küçük doğrulama noktasıyla aynıdır.
C++, Python ve Java uygulamaları oyunu simüle etmez. Yalnızca son sekiz basamak istendiği için kapalı formu doğrudan \(10^8\) modunda hesaplarlar.
Önce ikili üs alma ile \(2^n\bmod 10^8\) ve \(2^{n-k}\bmod 10^8\) bulunur. Sonra \(2^n-1\) ile \((k-1)2^n+(n-k+1)\) ifadeleri \(10^8\) modunda oluşturulur. Ardından
$$2^{n-k}\cdot \big((k-1)2^n+(n-k+1)\big)\cdot (2^n-1)\cdot (2^n-1)\pmod{10^8}$$
çarpımı alınır.
Uygulamalardan biri ayrıca küçük tam doğrulamaları ve hedef girişte sadeleştirmenin atlanmasını haklı çıkaran aralarında asallık koşulunu denetler; daha kısa uygulamalar ise hedef parametrelerin sabit olmasına güvenir. Sonuç, gerekirse başına sıfır eklenmiş sekiz basamaklı bir metin olarak yazdırılır.
Baskın maliyet modüler üs almadır ve bunun süresi \(O(\log n)\)'dir. Geri kalan işlemler sabit sayıda modüler toplama ve çarpma olduğundan toplam bellek kullanımı \(O(1)\) olur.
En este juego cíclico por parejas, los jugadores se recorren en un orden fijo, cada ronda se decide con una moneda justa y un jugador se convierte en campeón en cuanto ese mismo jugador gana dos rondas consecutivas en las que participa. Sea \(P_n(k)\) la probabilidad de que el jugador \(k\) gane cuando hay \(n\) jugadores, y sea \(M_n(k)\) el producto del numerador y el denominador después de reducir \(P_n(k)\) a su forma irreducible. Se pide obtener las últimas ocho cifras de
$$M_{10^8+7}(10^4+7).$$
Las implementaciones no siguen el juego ronda a ronda. En su lugar usan una reformulación estándar en términos de la primera aparición de un patrón en una secuencia de monedas justas. A partir de ahí solo queda contar esa primera aparición y simplificar una serie aritmético-geométrica.
Sea \(T\) la posición en la que el patrón \(RL\) termina por primera vez en una secuencia infinita de monedas justas. En la reformulación utilizada, ese primer \(RL\) es exactamente el instante decisivo del juego, y la identidad del ganador depende solo del número de ronda módulo \(n\).
Por tanto, el jugador \(k\) gana exactamente cuando
$$T=k+jn$$
para algún entero \(j\ge 0\). Así, todo el problema se reduce a hallar la distribución de \(T\) y sumar las probabilidades sobre una clase residual fija módulo \(n\).
Fijemos \(t\ge 2\). Para que el primer \(RL\) termine exactamente en la ronda \(t\), los primeros \(t-1\) símbolos no pueden contener un \(RL\) anterior, el símbolo en la posición \(t-1\) debe ser \(R\) y el símbolo en la posición \(t\) debe ser \(L\).
Una palabra binaria sin \(RL\) tiene necesariamente todos los \(L\) al principio y todos los \(R\) al final, así que cada prefijo admisible de longitud \(t-1\) tiene la forma
$$L^aR^{\,t-1-a}\qquad (0\le a\le t-2).$$
Hay exactamente \(t-1\) prefijos de ese tipo. Como cada cadena de longitud \(t\) tiene probabilidad \(2^{-t}\), obtenemos
$$\Pr(T=t)=\frac{t-1}{2^t}\qquad (t\ge 2).$$
Como las etiquetas de los jugadores se repiten cada \(n\) rondas, el jugador \(k\) recoge exactamente los términos con \(t\equiv k\pmod n\). Por eso
$$P_n(k)=\sum_{j\ge 0}\Pr(T=k+jn)=\sum_{j\ge 0}\frac{k+jn-1}{2^{k+jn}}.$$
Esta es la serie central utilizada por las tres implementaciones.
Definamos
$$q=2^{-n}.$$
Entonces se puede factorizar \(2^{-k}\):
$$P_n(k)=2^{-k}\sum_{j\ge 0}(k-1+jn)q^j.$$
Ahora usamos las identidades estándar
$$\sum_{j\ge 0}q^j=\frac{1}{1-q},\qquad \sum_{j\ge 0}jq^j=\frac{q}{(1-q)^2}.$$
Sustituyendo, resulta
$$P_n(k)=2^{-k}\left(\frac{k-1}{1-q}+\frac{nq}{(1-q)^2}\right).$$
Sea
$$X=2^n-1.$$
Como \(q=2^{-n}\), se cumple que
$$\frac{1}{1-q}=\frac{2^n}{X},\qquad \frac{q}{(1-q)^2}=\frac{2^n}{X^2}.$$
Por tanto,
$$P_n(k)=2^{-k}\left(\frac{(k-1)2^n}{X}+\frac{n2^n}{X^2}\right)=\frac{2^{n-k}\big((k-1)X+n\big)}{X^2}.$$
Al reemplazar \(X\) por \(2^n-1\), queda
$$P_n(k)=\frac{2^{n-k}\big((k-1)2^n+(n-k+1)\big)}{(2^n-1)^2}.$$
Escribamos
$$Y=(k-1)2^n+(n-k+1).$$
La fracción antes de reducir es
$$P_n(k)=\frac{2^{n-k}Y}{X^2},\qquad X=2^n-1.$$
Como \(X\) es impar, el factor \(2^{n-k}\) nunca se cancela con el denominador. La única posible reducción proviene de \(\gcd(Y,X^2)\). Módulo \(X\),
$$Y\equiv (k-1)+(n-k+1)\equiv n\pmod X,$$
de modo que
$$\gcd(Y,X)=\gcd(n,X).$$
Para el valor objetivo \(n=10^8+7\), el número \(n\) es primo, y el pequeño teorema de Fermat da \(2^n\equiv 2\pmod n\). Entonces
$$2^n-1\equiv 1\pmod n,$$
así que \(\gcd(n,2^n-1)=1\). En la instancia objetivo no hace falta reducir más, y por ello
$$M_n(k)\equiv 2^{n-k}\big((k-1)2^n+(n-k+1)\big)(2^n-1)^2\pmod{10^8}.$$
Este ejemplo muestra por qué la reducción importa en general, aunque en la instancia final no sea necesaria.
A partir de la fórmula cerrada,
$$P_6(2)=\frac{2^{6-2}\big((2-1)2^6+(6-2+1)\big)}{(2^6-1)^2}=\frac{16\cdot 69}{63^2}=\frac{1104}{3969}.$$
Ahora reducimos por \(3\):
$$P_6(2)=\frac{368}{1323}.$$
Por lo tanto,
$$M_6(2)=368\cdot 1323=486864,$$
que coincide con la comprobación pequeña usada por la validación exacta.
Las implementaciones en C++, Python y Java no simulan el juego. Evalúan directamente la fórmula cerrada módulo \(10^8\), porque solo interesan las últimas ocho cifras.
Primero calculan \(2^n\bmod 10^8\) y \(2^{n-k}\bmod 10^8\) mediante exponenciación modular binaria. Después forman los factores \(2^n-1\) y \((k-1)2^n+(n-k+1)\) también módulo \(10^8\). Luego multiplican
$$2^{n-k}\cdot \big((k-1)2^n+(n-k+1)\big)\cdot (2^n-1)\cdot (2^n-1)\pmod{10^8}.$$
Una de las implementaciones además comprueba ejemplos pequeños exactos y verifica la coprimalidad que permite omitir la reducción en la instancia objetivo; las versiones más compactas aprovechan directamente que los parámetros finales son fijos. El resultado final se imprime como una cadena de ocho dígitos, con ceros a la izquierda si hace falta.
El coste dominante es la exponenciación modular, que requiere \(O(\log n)\) tiempo. El resto son solo unas pocas sumas y multiplicaciones modulares sobre enteros de tamaño de máquina, de modo que el uso de memoria es \(O(1)\).
在这个循环进行的两两抛硬币游戏中，玩家按照固定顺序轮转，每一轮由一次公平抛硬币决定胜负，而某位玩家一旦在自己参与的两场相邻轮次中都获胜，就会成为最终冠军。记 \(P_n(k)\) 为共有 \(n\) 名玩家时第 \(k\) 位玩家夺冠的概率；把这个概率约成最简分数后，记分子与分母的乘积为 \(M_n(k)\)。题目要求的是
$$M_{10^8+7}(10^4+7)$$
的最后八位数字。
实现并不直接逐轮模拟游戏，而是先把它改写成“在公平硬币序列中等待某个模式第一次出现”的问题。这样一来，核心工作就变成两件事：先数出这个首次出现的概率，再把得到的级数化简成闭式。
设 \(T\) 表示在一条无限长的公平硬币序列中，模式 \(RL\) 第一次结束的位置。实现所采用的标准重述表明，游戏中真正决定冠军的时刻，正好对应于这个第一次出现的 \(RL\)，而获胜玩家的编号只取决于该轮编号对 \(n\) 的余数。
因此，第 \(k\) 位玩家获胜当且仅当
$$T=k+jn$$
对某个整数 \(j\ge 0\) 成立。于是原问题就变成：先求出 \(T\) 的分布，再把属于同一个模 \(n\) 同余类的那些概率加起来。
固定 \(t\ge 2\)。若第一次 \(RL\) 恰好在第 \(t\) 轮结束，那么前 \(t-1\) 个符号中不能提前出现 \(RL\)，第 \(t-1\) 个符号必须是 \(R\)，而第 \(t\) 个符号必须是 \(L\)。
一个不含 \(RL\) 的二元串，必然是前面全是 \(L\)，后面全是 \(R\)。因此，长度为 \(t-1\) 的每个合法前缀都只能写成
$$L^aR^{\,t-1-a}\qquad (0\le a\le t-2).$$
这样的前缀一共有恰好 \(t-1\) 个。由于任意长度为 \(t\) 的硬币序列概率都是 \(2^{-t}\)，于是得到
$$\Pr(T=t)=\frac{t-1}{2^t}\qquad (t\ge 2).$$
玩家编号每经过 \(n\) 轮就循环一次，所以第 \(k\) 位玩家对应的正是所有满足 \(t\equiv k\pmod n\) 的那些结束时刻。因此
$$P_n(k)=\sum_{j\ge 0}\Pr(T=k+jn)=\sum_{j\ge 0}\frac{k+jn-1}{2^{k+jn}}.$$
这就是三种实现共同使用的关键级数。
令
$$q=2^{-n}.$$
那么可以先提取出 \(2^{-k}\)：
$$P_n(k)=2^{-k}\sum_{j\ge 0}(k-1+jn)q^j.$$
接着使用两个标准求和公式
$$\sum_{j\ge 0}q^j=\frac{1}{1-q},\qquad \sum_{j\ge 0}jq^j=\frac{q}{(1-q)^2}.$$
代入后可得
$$P_n(k)=2^{-k}\left(\frac{k-1}{1-q}+\frac{nq}{(1-q)^2}\right).$$
记
$$X=2^n-1.$$
因为 \(q=2^{-n}\)，所以
$$\frac{1}{1-q}=\frac{2^n}{X},\qquad \frac{q}{(1-q)^2}=\frac{2^n}{X^2}.$$
于是
$$P_n(k)=2^{-k}\left(\frac{(k-1)2^n}{X}+\frac{n2^n}{X^2}\right)=\frac{2^{n-k}\big((k-1)X+n\big)}{X^2}.$$
再把 \(X=2^n-1\) 展开，就得到紧凑的闭式
$$P_n(k)=\frac{2^{n-k}\big((k-1)2^n+(n-k+1)\big)}{(2^n-1)^2}.$$
再记
$$Y=(k-1)2^n+(n-k+1).$$
那么未约分的分数就是
$$P_n(k)=\frac{2^{n-k}Y}{X^2},\qquad X=2^n-1.$$
由于 \(X\) 是奇数，因子 \(2^{n-k}\) 不会和分母约掉。真正可能发生的约分，只来自 \(\gcd(Y,X^2)\)。在模 \(X\) 的意义下，
$$Y\equiv (k-1)+(n-k+1)\equiv n\pmod X,$$
因此
$$\gcd(Y,X)=\gcd(n,X).$$
对于目标参数 \(n=10^8+7\)，\(n\) 是素数，而费马小定理给出 \(2^n\equiv 2\pmod n\)。于是
$$2^n-1\equiv 1\pmod n,$$
从而 \(\gcd(n,2^n-1)=1\)。这说明目标实例中不需要额外约分，因此
$$M_n(k)\equiv 2^{n-k}\big((k-1)2^n+(n-k+1)\big)(2^n-1)^2\pmod{10^8}.$$
这个例子说明，一般情况下约分步骤确实重要，只是目标实例恰好不需要而已。
由闭式直接得到
$$P_6(2)=\frac{2^{6-2}\big((2-1)2^6+(6-2+1)\big)}{(2^6-1)^2}=\frac{16\cdot 69}{63^2}=\frac{1104}{3969}.$$
再把分子分母同时除以 \(3\)，得到
$$P_6(2)=\frac{368}{1323}.$$
因此
$$M_6(2)=368\cdot 1323=486864,$$
这与精确校验中使用的小样例结果一致。
C++、Python 和 Java 三种实现都不会去模拟具体比赛过程，而是直接在模 \(10^8\) 下计算闭式，因为题目只要求最后八位。
首先，它们用二进制快速幂求出 \(2^n\bmod 10^8\) 和 \(2^{n-k}\bmod 10^8\)。接着，在同一个模数下构造两个闭式因子 \(2^n-1\) 与 \((k-1)2^n+(n-k+1)\)。然后计算
$$2^{n-k}\cdot \big((k-1)2^n+(n-k+1)\big)\cdot (2^n-1)\cdot (2^n-1)\pmod{10^8}.$$
其中一个实现还会额外检查小规模精确样例，并验证目标参数满足上面说明的互素条件，从而可以安全地跳过约分；更精简的实现则直接利用目标输入已经固定这一事实。最后再把结果格式化为 8 位字符串，必要时在左侧补零。
主要成本来自模幂运算，时间复杂度为 \(O(\log n)\)。其余部分只是常数次的模加法与模乘法，因此空间复杂度为 \(O(1)\)。
В этой циклической парной игре игроки проходят по фиксированному кругу, каждый раунд определяется честным броском монеты, и игрок становится чемпионом, как только выигрывает две подряд идущие партии, в которых участвует. Обозначим через \(P_n(k)\) вероятность победы игрока \(k\) при \(n\) игроках, а через \(M_n(k)\) произведение числителя и знаменателя после сокращения \(P_n(k)\) до несократимой дроби. Нужно найти последние восемь цифр числа
$$M_{10^8+7}(10^4+7).$$
Реализации не моделируют игру напрямую. Вместо этого используется стандартное сведение к задаче о первом появлении определённого шаблона в последовательности честных бросков монеты. После такого сведения остаётся посчитать вероятность первого появления и упростить возникающий арифметико-геометрический ряд.
Пусть \(T\) — позиция, на которой шаблон \(RL\) впервые заканчивается в бесконечной последовательности честных бросков. В используемой переформулировке игры именно это первое \(RL\) соответствует решающему моменту, а номер победителя зависит только от номера раунда по модулю \(n\).
Поэтому игрок \(k\) выигрывает тогда и только тогда, когда
$$T=k+jn$$
для некоторого целого \(j\ge 0\). Значит, задача сводится к нахождению распределения \(T\) и суммированию вероятностей по одному фиксированному классу вычетов modulo \(n\).
Зафиксируем \(t\ge 2\). Чтобы первое \(RL\) закончилось ровно на раунде \(t\), среди первых \(t-1\) символов не должно быть более раннего \(RL\), символ в позиции \(t-1\) должен быть равен \(R\), а символ в позиции \(t\) должен быть равен \(L\).
Двоичное слово без \(RL\) обязательно имеет сначала только \(L\), а затем только \(R\). Поэтому каждый допустимый префикс длины \(t-1\) имеет вид
$$L^aR^{\,t-1-a}\qquad (0\le a\le t-2).$$
Таких префиксов ровно \(t-1\). Поскольку любая строка длины \(t\) имеет вероятность \(2^{-t}\), получаем
$$\Pr(T=t)=\frac{t-1}{2^t}\qquad (t\ge 2).$$
Так как номера игроков повторяются через каждые \(n\) раундов, игроку \(k\) соответствуют все времена завершения с условием \(t\equiv k\pmod n\). Следовательно,
$$P_n(k)=\sum_{j\ge 0}\Pr(T=k+jn)=\sum_{j\ge 0}\frac{k+jn-1}{2^{k+jn}}.$$
Именно этот ряд лежит в основе всех трёх реализаций.
Положим
$$q=2^{-n}.$$
Тогда можно вынести множитель \(2^{-k}\):
$$P_n(k)=2^{-k}\sum_{j\ge 0}(k-1+jn)q^j.$$
Используем стандартные тождества
$$\sum_{j\ge 0}q^j=\frac{1}{1-q},\qquad \sum_{j\ge 0}jq^j=\frac{q}{(1-q)^2}.$$
После подстановки имеем
$$P_n(k)=2^{-k}\left(\frac{k-1}{1-q}+\frac{nq}{(1-q)^2}\right).$$
Обозначим
$$X=2^n-1.$$
Так как \(q=2^{-n}\), верно
$$\frac{1}{1-q}=\frac{2^n}{X},\qquad \frac{q}{(1-q)^2}=\frac{2^n}{X^2}.$$
Отсюда
$$P_n(k)=2^{-k}\left(\frac{(k-1)2^n}{X}+\frac{n2^n}{X^2}\right)=\frac{2^{n-k}\big((k-1)X+n\big)}{X^2}.$$
Подставляя \(X=2^n-1\), получаем компактный вид
$$P_n(k)=\frac{2^{n-k}\big((k-1)2^n+(n-k+1)\big)}{(2^n-1)^2}.$$
Обозначим также
$$Y=(k-1)2^n+(n-k+1).$$
Тогда несокращённая дробь имеет вид
$$P_n(k)=\frac{2^{n-k}Y}{X^2},\qquad X=2^n-1.$$
Поскольку \(X\) нечётно, множитель \(2^{n-k}\) никогда не сокращается со знаменателем. Возможное сокращение может идти только через \(\gcd(Y,X^2)\). По модулю \(X\) имеем
$$Y\equiv (k-1)+(n-k+1)\equiv n\pmod X,$$
следовательно,
$$\gcd(Y,X)=\gcd(n,X).$$
Для целевого значения \(n=10^8+7\) число \(n\) простое, а малая теорема Ферма даёт \(2^n\equiv 2\pmod n\). Значит,
$$2^n-1\equiv 1\pmod n,$$
и потому \(\gcd(n,2^n-1)=1\). Для целевого случая дополнительного сокращения нет, так что
$$M_n(k)\equiv 2^{n-k}\big((k-1)2^n+(n-k+1)\big)(2^n-1)^2\pmod{10^8}.$$
Этот пример показывает, почему шаг сокращения важен в общем случае, хотя для целевого набора параметров он не нужен.
Из замкнутой формулы получаем
$$P_6(2)=\frac{2^{6-2}\big((2-1)2^6+(6-2+1)\big)}{(2^6-1)^2}=\frac{16\cdot 69}{63^2}=\frac{1104}{3969}.$$
Теперь сокращаем на \(3\):
$$P_6(2)=\frac{368}{1323}.$$
Следовательно,
$$M_6(2)=368\cdot 1323=486864,$$
что совпадает с малой контрольной проверкой точного вычисления.
Реализации на C++, Python и Java не моделируют игру. Они напрямую вычисляют замкнутую формулу по модулю \(10^8\), потому что нужны только последние восемь цифр.
Сначала при помощи бинарного модульного возведения в степень вычисляются \(2^n\bmod 10^8\) и \(2^{n-k}\bmod 10^8\). Затем по модулю \(10^8\) строятся два множителя \(2^n-1\) и \((k-1)2^n+(n-k+1)\). После этого вычисляется произведение
$$2^{n-k}\cdot \big((k-1)2^n+(n-k+1)\big)\cdot (2^n-1)\cdot (2^n-1)\pmod{10^8}.$$
Одна из реализаций дополнительно проверяет малые точные примеры и подтверждает условие взаимной простоты, позволяющее пропустить сокращение для целевого ввода; более компактные реализации используют тот факт, что целевые параметры фиксированы заранее. В конце результат форматируется как восьмизначная строка с ведущими нулями при необходимости.
Основная стоимость приходится на модульное возведение в степень, что даёт \(O(\log n)\) по времени. Все остальные действия — это лишь константное число модульных сложений и умножений над машинными целыми, поэтому память равна \(O(1)\).
في هذه اللعبة الزوجية الدورية يمر اللاعبون وفق ترتيب ثابت، وتُحسم كل جولة برمية عملة عادلة، ويصبح اللاعب بطلاً عندما يفوز هو نفسه بجولتين متتاليتين يشارك فيهما. نرمز باحتمال فوز اللاعب \(k\) عند وجود \(n\) لاعبين إلى \(P_n(k)\)، ونرمز بحاصل ضرب البسط والمقام بعد اختزال هذا الاحتمال إلى أبسط صورة إلى \(M_n(k)\). المطلوب هو آخر ثمانية أرقام من
$$M_{10^8+7}(10^4+7).$$
لا تعتمد التطبيقات على محاكاة اللعبة جولة بجولة، بل تستخدم صياغة قياسية تحول المسألة إلى انتظار أول ظهور لنمط معيّن في متتالية من رميات العملة العادلة. بعد ذلك يصبح العمل كله هو حساب احتمال هذا الظهور الأول ثم تبسيط متسلسلة حسابية-هندسية.
لنرمز بـ \(T\) إلى الموضع الذي ينتهي عنده النمط \(RL\) لأول مرة في متتالية لا نهائية من رميات عملة عادلة. في الصياغة المستخدمة في الحل، تمثل هذه المرة الأولى التي يظهر فيها \(RL\) اللحظة الحاسمة التي تحدد البطل، كما أن هوية الفائز تعتمد فقط على رقم الجولة بترديد \(n\).
لذلك فإن اللاعب \(k\) يفوز إذا وفقط إذا كان
$$T=k+jn$$
لبعض عدد صحيح \(j\ge 0\). وهكذا تتحول المسألة كلها إلى إيجاد توزيع \(T\) ثم جمع الاحتمالات الواقعة في فئة توافق واحدة modulo \(n\).
ثبّت \(t\ge 2\). لكي ينتهي أول \(RL\) تماماً عند الجولة \(t\)، يجب ألا تحتوي الرموز \(t-1\) الأولى على \(RL\) أسبق، ويجب أن يكون الرمز في الموضع \(t-1\) هو \(R\)، والرمز في الموضع \(t\) هو \(L\).
أي كلمة ثنائية لا تحتوي على \(RL\) لا بد أن تكون جميع حروف \(L\) فيها أولاً ثم جميع حروف \(R\) بعد ذلك. لذلك فإن كل بادئة صحيحة طولها \(t-1\) تأخذ الشكل
$$L^aR^{\,t-1-a}\qquad (0\le a\le t-2).$$
وهناك بالضبط \(t-1\) بادئة من هذا النوع. وبما أن احتمال كل سلسلة بطول \(t\) هو \(2^{-t}\)، نحصل على
$$\Pr(T=t)=\frac{t-1}{2^t}\qquad (t\ge 2).$$
بما أن أرقام اللاعبين تتكرر كل \(n\) جولات، فإن اللاعب \(k\) يجمع تماماً الأزمنة التي تحقق \(t\equiv k\pmod n\). ومن ثم
$$P_n(k)=\sum_{j\ge 0}\Pr(T=k+jn)=\sum_{j\ge 0}\frac{k+jn-1}{2^{k+jn}}.$$
وهذه هي المتسلسلة الأساسية المستخدمة في جميع التطبيقات الثلاثة.
لنضع
$$q=2^{-n}.$$
عندئذ يمكن إخراج العامل \(2^{-k}\):
$$P_n(k)=2^{-k}\sum_{j\ge 0}(k-1+jn)q^j.$$
ثم نستخدم المتطابقتين القياسيتين
$$\sum_{j\ge 0}q^j=\frac{1}{1-q},\qquad \sum_{j\ge 0}jq^j=\frac{q}{(1-q)^2}.$$
وبالتعويض نحصل على
$$P_n(k)=2^{-k}\left(\frac{k-1}{1-q}+\frac{nq}{(1-q)^2}\right).$$
لنعرف
$$X=2^n-1.$$
وبما أن \(q=2^{-n}\)، فإن
$$\frac{1}{1-q}=\frac{2^n}{X},\qquad \frac{q}{(1-q)^2}=\frac{2^n}{X^2}.$$
ومن ثم
$$P_n(k)=2^{-k}\left(\frac{(k-1)2^n}{X}+\frac{n2^n}{X^2}\right)=\frac{2^{n-k}\big((k-1)X+n\big)}{X^2}.$$
وبتعويض \(X=2^n-1\) نحصل على الصيغة المدمجة
$$P_n(k)=\frac{2^{n-k}\big((k-1)2^n+(n-k+1)\big)}{(2^n-1)^2}.$$
لنعرف أيضاً
$$Y=(k-1)2^n+(n-k+1).$$
عندها يكون الكسر قبل الاختزال هو
$$P_n(k)=\frac{2^{n-k}Y}{X^2},\qquad X=2^n-1.$$
ولأن \(X\) عدد فردي، فإن العامل \(2^{n-k}\) لا يختزل أبداً مع المقام. وأي اختزال محتمل لا بد أن يأتي من \(\gcd(Y,X^2)\) فقط. وبالأخذ modulo \(X\) نجد أن
$$Y\equiv (k-1)+(n-k+1)\equiv n\pmod X,$$
ومن ثم
$$\gcd(Y,X)=\gcd(n,X).$$
في الحالة المطلوبة \(n=10^8+7\)، العدد \(n\) أولي، وتعطي مبرهنة فيرما الصغرى \(2^n\equiv 2\pmod n\). لذلك
$$2^n-1\equiv 1\pmod n,$$
وبالتالي \(\gcd(n,2^n-1)=1\). وهذا يعني أنه لا توجد حاجة إلى اختزال إضافي في المثال الهدف، ومن ثم
$$M_n(k)\equiv 2^{n-k}\big((k-1)2^n+(n-k+1)\big)(2^n-1)^2\pmod{10^8}.$$
يوضح هذا المثال لماذا تظل خطوة الاختزال مهمة في الحالة العامة، حتى لو لم نحتج إليها في المثال النهائي المطلوب.
من الصيغة المغلقة نحصل على
$$P_6(2)=\frac{2^{6-2}\big((2-1)2^6+(6-2+1)\big)}{(2^6-1)^2}=\frac{16\cdot 69}{63^2}=\frac{1104}{3969}.$$
ثم نختزل بالقاسم \(3\):
$$P_6(2)=\frac{368}{1323}.$$
وعليه
$$M_6(2)=368\cdot 1323=486864,$$
وهو نفس مقدار التحقق الصغير المستخدم في الفحص الدقيق.
تنفيذات C++ وPython وJava لا تحاكي اللعبة. إنها تحسب الصيغة المغلقة مباشرةً بترديد \(10^8\)، لأن المطلوب هو آخر ثمانية أرقام فقط.
أولاً تُحسب القيمتان \(2^n\bmod 10^8\) و\(2^{n-k}\bmod 10^8\) باستخدام الرفع الثنائي المعياري. بعد ذلك تُبنى العوامل \(2^n-1\) و\((k-1)2^n+(n-k+1)\) أيضاً بترديد \(10^8\). ثم يُحسب حاصل الضرب
$$2^{n-k}\cdot \big((k-1)2^n+(n-k+1)\big)\cdot (2^n-1)\cdot (2^n-1)\pmod{10^8}.$$
أحد التنفيذات يضيف كذلك فحوصات دقيقة لأمثلة صغيرة ويتأكد من شرط التوافق الأولي الذي يبرر تجاوز الاختزال في الإدخال الهدف، بينما تعتمد التنفيذات المختصرة على أن القيم النهائية ثابتة سلفاً. وفي النهاية تُنسق النتيجة كسلسلة من ثمانية أرقام مع أصفار بادئة عند الحاجة.
الكلفة المسيطرة هي الرفع المعياري للأس، وزمنه \(O(\log n)\). أما بقية العمل فهو عدد ثابت من عمليات الجمع والضرب المعياريين على أعداد بحجم كلمة الآلة، لذلك يكون استهلاك الذاكرة \(O(1)\).