There are \(m=c+1\) coins on a strip of \(n\) squares, and exactly one of them is the silver dollar. A legal move is either a regular left move of one coin or the special move of pocketing the leftmost coin. The first player wins iff they eventually pocket the silver dollar.
So we must count all configurations from which the first player can force that outcome. If we first choose the occupied squares and then choose which of the \(m\) coins is silver, the total number of raw configurations is
$$T=m\binom{n}{m}.$$
Write the coin positions as
$$0\le x_0 \lt x_1 \lt \cdots \lt x_{m-1}\le n-1.$$
Instead of working with positions directly, the code switches to gaps:
$$g_0=x_0,\qquad g_i=x_i-x_{i-1}-1\ (1\le i\le m-1),\qquad g_m=n-1-x_{m-1}.$$
These are the empty squares before the first coin, between consecutive coins, and after the last coin. Every legal placement corresponds to exactly one nonnegative gap vector \((g_0,\dots,g_m)\), and the total number of empty squares is
$$g_0+g_1+\cdots+g_m=n-m=:N.$$
This is why the implementation begins with the parameter reduction
$$m=c+1,\qquad N=n-m.$$
The crucial combinatorial fact is that the ordinary silver dollar game can be described by alternating gaps. Let
$$k=\left\lceil\frac{m}{2}\right\rceil,\qquad r=m-k+1.$$
The active gaps are the ones that contribute to the Nim-style xor condition:
If \(m\) is even, the active gaps are
$$g_1,g_3,\dots,g_{m-1}.$$
If \(m\) is odd, the active gaps are
$$g_0,g_2,\dots,g_{m-1}.$$
All remaining gaps are passive: they affect the total length, but not the xor criterion.
For the ordinary silver dollar game, a position is losing precisely when the xor of the active gaps is zero:
$$a_1\oplus a_2\oplus\cdots\oplus a_k=0,$$
where \(\oplus\) denotes bitwise xor, i.e. the Nim-sum. This reduces the geometric game on coin positions to a counting problem on nonnegative integers with a fixed total sum and an xor constraint.
Now restore the fact that one coin is distinguished as the silver dollar, and let \(j\in\{0,\dots,m-1\}\) be its rank from the left.
1) The leftmost silver dollar is never losing. If \(j=0\), the current player pockets it immediately and wins.
2) Even number of coins. If \(m\) is even and \(j\ge1\), the losing configurations are exactly the ordinary xor-zero gap configurations. The silver dollar may be any of the \(m-1\) non-leftmost coins, so
$$L=(m-1)L_0,\qquad L_0=\text{Count}(N;\text{ways}_k).$$
3) Odd number of coins. If \(m\) is odd, two different families appear:
When the silver dollar is the second coin (\(j=1\)), we again obtain the ordinary xor-zero count
$$L_0=\text{Count}(N;\text{ways}_k).$$
When the silver dollar is any coin from the third onward (\(j\ge2\)), the pocket move shifts the effective left boundary by one square. In gap language this becomes the same xor-zero counting problem, but with total sum \(N+1\) and the extra requirement \(g_0>0\). The code denotes this count by \(L_1\):
$$L_1=\text{Count}(N+1;\text{ways}_k)-\text{Count}(N+1;\text{ways}_{k-1}).$$
The subtraction removes the cases with \(g_0=0\): if the first active gap is zero, it contributes nothing to the xor and the problem collapses to the same count with only \(k-1\) active gaps.
Therefore, for odd \(m\),
$$L=L_0+(m-2)L_1.$$
Finally the number of winning configurations is always
$$W=T-L.$$
The function \(\text{Count}(S;\text{ways})\) counts nonnegative gap tuples whose total sum is \(S\) and whose active gaps xor to zero. Direct enumeration is impossible for \(n=10^6\), so the code counts them bit by bit.
Fix one binary column. Suppose exactly \(x\) of the \(k\) active gaps have bit 1. To keep xor zero in that column, \(x\) must be even. If exactly \(y\) of the \(r\) passive gaps also have bit 1, then the total number of ones in that column is \(s=x+y\), and the number of assignments for that column is
$$\binom{k}{x}\binom{r}{y}.$$
Summing over all even \(x\) gives the coefficient array used by the DP:
$$\text{ways}(s)=\sum_{\substack{0\le x\le k\\x\text{ even}}}\binom{k}{x}\binom{r}{s-x},\qquad 0\le s\le k+r.$$
This explains the code in build_ways_even_*: it is not an arbitrary precomputation, but the exact count of all valid bit-column patterns.
After the bit-column counts are known, the remaining task is to ensure that the total arithmetic sum of all gaps is exactly \(S\). That is what count_with_ways does.
Process the binary expansion of \(S\) from least significant bit to most significant bit. Let \(c\) be the incoming carry at bit \(b\), and let \(\beta_b\in\{0,1\}\) be the \(b\)-th bit of \(S\). If a chosen column has \(s\) ones in total, then it is valid exactly when
$$s+c\equiv \beta_b\pmod2.$$
The outgoing carry is then
$$c'=\frac{s+c-\beta_b}{2}.$$
Hence the transition is
$$dp_{b+1}(c')\mathrel{+}=dp_b(c)\cdot \text{ways}(s).$$
This is a standard digit-DP with carries, but here the column multiplicities already encode the xor-zero condition on the active gaps.
Here \(m=c+1=3\) and \(N=n-m=7\). The total number of configurations is
$$T=3\binom{10}{3}=3\cdot120=360.$$
Because \(m\) is odd, the losing count splits into two parts. The silver dollar on the second coin contributes
$$L_0=\text{Count}(7;\text{ways}_2)=20.$$
The silver dollar on the third coin contributes
$$L_1=\text{Count}(8;\text{ways}_2)-\text{Count}(8;\text{ways}_1)=16.$$
Therefore
$$L=20+(3-2)\cdot16=36,$$
and
$$W=360-36=324,$$
which matches the published checkpoint.
The C++, Python, and Java implementations follow the same pipeline. First, they build small binomial tables for the gap-layer coefficients. Next, build_ways_even_* constructs the array \(\text{ways}(s)\). Then count_with_ways_* performs the carry DP for an exact target sum. Finally, compute_W_* applies the even/odd formulas for the losing count and subtracts it from \(T\).
For the final Euler input, the modulus is composite:
$$M=1000036000099=1000003\cdot1000033.$$
So the code computes binomial coefficients modulo each prime via factorial and inverse-factorial tables, then merges the two residues with the Chinese Remainder Theorem. The C++ version additionally computes the small checkpoints exactly before switching to modular arithmetic for \(W(1\,000\,000,100)\).
For fixed \(m\), a single Count call scans \(O(\log N)\) bit levels. Each level considers \(O(m)\) carry states and \(O(m)\) possible column sums, so the DP cost is
$$O(m^2\log N)$$
time and \(O(m)\) memory. The factorial / inverse-factorial preprocessing for modular binomial coefficients is \(O(n)\) for each prime modulus.
Auf einem Streifen mit \(n\) Feldern liegen \(m=c+1\) Münzen, davon genau eine als Silberdollar. Ein Zug ist entweder ein gewöhnlicher Zug nach links oder der Sonderzug, die linkeste Münze einzustecken. Der erste Spieler gewinnt genau dann, wenn er schließlich den Silberdollar einsteckt.
Wir müssen also alle Konfigurationen zählen, aus denen der Startspieler diesen Ausgang erzwingen kann. Wählt man zunächst die belegten Felder und danach, welche der \(m\) Münzen der Silberdollar ist, erhält man insgesamt
$$T=m\binom{n}{m}$$
Rohkonfigurationen.
Bezeichne die Münzpositionen mit
$$0\le x_0 \lt x_1 \lt \cdots \lt x_{m-1}\le n-1.$$
Statt direkt mit den Positionen zu arbeiten, verwendet der Code die Lücken
$$g_0=x_0,\qquad g_i=x_i-x_{i-1}-1\ (1\le i\le m-1),\qquad g_m=n-1-x_{m-1}.$$
Das sind die freien Felder vor der ersten Münze, zwischen benachbarten Münzen und nach der letzten Münze. Jede Platzierung entspricht genau einem nichtnegativen Vektor \((g_0,\dots,g_m)\), und die Gesamtzahl leerer Felder ist
$$g_0+g_1+\cdots+g_m=n-m=:N.$$
Darum reduziert die Implementierung zuerst auf
$$m=c+1,\qquad N=n-m.$$
Der entscheidende kombinatorische Satz besagt, dass das gewöhnliche Silver-Dollar-Spiel durch alternierende Lücken beschrieben werden kann. Setze
$$k=\left\lceil\frac{m}{2}\right\rceil,\qquad r=m-k+1.$$
Die aktiven Lücken sind genau die, die in die Nim-Summe eingehen:
Ist \(m\) gerade, so sind die aktiven Lücken
$$g_1,g_3,\dots,g_{m-1}.$$
Ist \(m\) ungerade, so sind die aktiven Lücken
$$g_0,g_2,\dots,g_{m-1}.$$
Alle übrigen Lücken sind passiv: Sie beeinflussen die Gesamtlänge, aber nicht die xor-Bedingung.
Für das gewöhnliche Silver-Dollar-Spiel ist eine Stellung genau dann verlierend, wenn die xor-Summe der aktiven Lücken Null ist:
$$a_1\oplus a_2\oplus\cdots\oplus a_k=0,$$
wobei \(\oplus\) die bitweise XOR-Verknüpfung, also die Nim-Summe, bezeichnet. Damit wird das geometrische Spiel auf Münzpositionen zu einem Zählproblem über nichtnegative ganze Zahlen mit fester Gesamtsumme und xor-Nebenbedingung.
Nun berücksichtigen wir wieder, dass eine Münze als Silberdollar ausgezeichnet ist, und nennen ihren Rang von links \(j\in\{0,\dots,m-1\}\).
1) Linkester Silberdollar. Für \(j=0\) gewinnt der aktuelle Spieler sofort, indem er ihn einsteckt. Solche Stellungen sind also nie verlierend.
2) Gerade Münzanzahl. Ist \(m\) gerade und \(j\ge1\), dann sind die verlierenden Konfigurationen genau die gewöhnlichen xor-Null-Stellungen. Der Silberdollar kann dann auf jeder der \(m-1\) nichtlinken Münzen liegen, also
$$L=(m-1)L_0,\qquad L_0=\text{Count}(N;\text{ways}_k).$$
3) Ungerade Münzanzahl. Ist \(m\) ungerade, entstehen zwei Familien:
Liegt der Silberdollar auf der zweiten Münze (\(j=1\)), erhält man wieder einfach die gewöhnliche xor-Null-Zahl
$$L_0=\text{Count}(N;\text{ways}_k).$$
Liegt der Silberdollar weiter rechts (\(j\ge2\)), verschiebt der Sonderzug die effektive linke Randbedingung um ein Feld. In der Lückensprache ist das dasselbe xor-Zählproblem, aber mit Gesamtsumme \(N+1\) und Zusatzbedingung \(g_0>0\). Dieser Anteil heißt im Code \(L_1\):
$$L_1=\text{Count}(N+1;\text{ways}_k)-\text{Count}(N+1;\text{ways}_{k-1}).$$
Die Subtraktion entfernt genau die Fälle mit \(g_0=0\): Dann trägt die erste aktive Lücke nichts zur xor-Summe bei und das Problem reduziert sich auf dieselbe Zählung mit nur \(k-1\) aktiven Lücken.
Also gilt für ungerades \(m\)
$$L=L_0+(m-2)L_1.$$
Die Anzahl der Gewinnstellungen ist schließlich immer
$$W=T-L.$$
Die Funktion \(\text{Count}(S;\text{ways})\) zählt nichtnegative Lückenvektoren mit Gesamtsumme \(S\), deren aktive Lücken xor zu Null ergeben. Direkte Enumeration ist bei \(n=10^6\) unmöglich, daher zählt der Code bitweise.
Fixiere eine Binärstelle. Haben genau \(x\) der \(k\) aktiven Lücken an dieser Stelle eine 1, so muss \(x\) gerade sein, damit die xor-Summe dort Null bleibt. Haben zusätzlich genau \(y\) der \(r\) passiven Lücken eine 1, dann ist die Gesamtzahl der Einsen in dieser Spalte \(s=x+y\), und die Anzahl solcher Muster ist
$$\binom{k}{x}\binom{r}{y}.$$
Summiert man über alle geraden \(x\), erhält man das im DP verwendete Koeffizientenarray:
$$\text{ways}(s)=\sum_{\substack{0\le x\le k\\x\text{ gerade}}}\binom{k}{x}\binom{r}{s-x},\qquad 0\le s\le k+r.$$
Genau dies berechnet build_ways_even_*.
Sind die Spaltenkoeffizienten bekannt, muss nur noch sichergestellt werden, dass die gesamte arithmetische Summe aller Lücken genau \(S\) ergibt. Das leistet count_with_ways.
Man verarbeitet die Bits von \(S\) von rechts nach links. Sei \(c\) der eingehende Carry an Position \(b\), und \(\beta_b\in\{0,1\}\) das \(b\)-te Bit von \(S\). Eine Spaltensumme \(s\) ist genau dann zulässig, wenn
$$s+c\equiv \beta_b\pmod2.$$
Der ausgehende Carry lautet dann
$$c'=\frac{s+c-\beta_b}{2}.$$
Damit ergibt sich der Übergang
$$dp_{b+1}(c')\mathrel{+}=dp_b(c)\cdot \text{ways}(s).$$
Das ist ein klassisches Stellen-DP mit Überträgen, wobei die Spaltenmultiplikitäten bereits die xor-Null-Bedingung der aktiven Lücken kodieren.
Hier ist \(m=c+1=3\) und \(N=n-m=7\). Die Gesamtzahl aller Konfigurationen ist
$$T=3\binom{10}{3}=3\cdot120=360.$$
Da \(m\) ungerade ist, zerfällt die Verlustzahl in zwei Teile. Für den Silberdollar auf der zweiten Münze erhält man
$$L_0=\text{Count}(7;\text{ways}_2)=20.$$
Für den Silberdollar auf der dritten Münze erhält man
$$L_1=\text{Count}(8;\text{ways}_2)-\text{Count}(8;\text{ways}_1)=16.$$
Also
$$L=20+(3-2)\cdot16=36,$$
und damit
$$W=360-36=324,$$
genau wie in der Aufgabenstellung angegeben.
Die C++-, Python- und Java-Versionen folgen derselben Pipeline. Zuerst werden kleine Binomialtabellen für die Lückenschicht aufgebaut. Dann konstruiert build_ways_even_* das Array \(\text{ways}(s)\). Anschließend führt count_with_ways_* das Carry-DP für eine exakte Zielsumme aus. Schließlich setzt compute_W_* die Gerade/Ungerade-Formeln für die Verluststellungen ein und subtrahiert sie von \(T\).
Für die endgültige Euler-Eingabe ist der Modulus zusammengesetzt:
$$M=1000036000099=1000003\cdot1000033.$$
Daher berechnet der Code die Binomialkoeffizienten modulo beider Primzahlen mit Fakultäts- und Inversfakultätstabellen und kombiniert die Reste anschließend per Chinesischem Restsatz. Die C++-Version prüft zusätzlich die kleinen Kontrollwerte exakt, bevor sie für \(W(1\,000\,000,100)\) auf Modularechnung umschaltet.
Für festes \(m\) durchläuft ein einzelner Count-Aufruf \(O(\log N)\) Bitpositionen. Pro Ebene werden \(O(m)\) Carry-Zustände und \(O(m)\) mögliche Spaltensummen betrachtet. Damit kostet das DP
$$O(m^2\log N)$$
Zeit und \(O(m)\) Speicher. Die Vorberechnung von Fakultäten und Inversfakultäten für modulare Binomialkoeffizienten benötigt \(O(n)\) pro Primmodul.
\(n\) karelik bir şerit üzerinde \(m=c+1\) adet madeni para vardır ve bunlardan yalnızca biri gümüş dolardır. Geçerli hamle ya bir parayı sola kaydırmak ya da en soldaki parayı cebe atmaktır. İlk oyuncu, sonunda gümüş doları cebine atabiliyorsa kazanır.
Dolayısıyla ilk oyuncunun bunu zorlayabildiği tüm başlangıç dizilimlerini saymamız gerekir. Önce dolu kareleri, sonra da bu \(m\) para arasından hangisinin gümüş dolar olduğunu seçersek toplam ham konfigürasyon sayısı
$$T=m\binom{n}{m}$$
olur.
Para konumlarını
$$0\le x_0 \lt x_1 \lt \cdots \lt x_{m-1}\le n-1$$
olarak yazalım. Kod, doğrudan bu konumlarla değil, aralardaki boşluklarla çalışır:
$$g_0=x_0,\qquad g_i=x_i-x_{i-1}-1\ (1\le i\le m-1),\qquad g_m=n-1-x_{m-1}.$$
Bunlar ilk paradan önceki, komşu paralar arasındaki ve son paradan sonraki boş kare sayılarıdır. Her yerleşim tam olarak bir \((g_0,\dots,g_m)\) boşluk vektörüne karşılık gelir ve toplam boş kare sayısı
$$g_0+g_1+\cdots+g_m=n-m=:N$$
olur. Bu yüzden çözüm önce
$$m=c+1,\qquad N=n-m$$
dönüşümünü yapar.
Temel kombinatorik gerçek şudur: klasik silver dollar oyunu, dönüşümlü boşluklar üzerinden Nim'e indirgenebilir. Tanımlayalım:
$$k=\left\lceil\frac{m}{2}\right\rceil,\qquad r=m-k+1.$$
Aktif boşluklar xor koşuluna giren boşluklardır:
\(m\) çiftse aktif boşluklar
$$g_1,g_3,\dots,g_{m-1}$$
olur.
\(m\) tekse aktif boşluklar
$$g_0,g_2,\dots,g_{m-1}$$
olur.
Kalan boşluklar pasiftir: toplam uzunluğu etkilerler ama xor koşuluna girmezler.
Klasik silver dollar oyunu için bir konum tam olarak aktif boşlukların xor'u sıfırsa kaybedendir:
$$a_1\oplus a_2\oplus\cdots\oplus a_k=0,$$
burada \(\oplus\) bit düzeyinde xor, yani Nim toplamıdır. Böylece geometrik para dizilimi problemi, toplamı sabit olan ve xor kısıtı taşıyan negatif olmayan tamsayıların sayımına dönüşür.
Şimdi bir paranın gümüş dolar olduğunu tekrar devreye alalım ve soldan indeksini \(j\in\{0,\dots,m-1\}\) ile gösterelim.
1) Gümüş dolar soldaki ilk paraysa: \(j=0\) durumunda sıradaki oyuncu onu hemen cebe atıp kazanır. Bu yüzden böyle konumlar asla kaybeden değildir.
2) Para sayısı çiftse: \(m\) çift ve \(j\ge1\) ise kaybeden konfigürasyonlar tam olarak klasik xor-sıfır konfigürasyonlarıdır. Gümüş dolar soldaki ilk para dışında kalan \(m-1\) paradan herhangi birinde olabilir; dolayısıyla
$$L=(m-1)L_0,\qquad L_0=\text{Count}(N;\text{ways}_k).$$
3) Para sayısı tekse: \(m\) tek olduğunda iki farklı aile oluşur.
Gümüş dolar ikinci paradaysa (\(j=1\)), yine klasik xor-sıfır sayımı gelir:
$$L_0=\text{Count}(N;\text{ways}_k).$$
Gümüş dolar üçüncü veya daha sağdaki bir paradaysa (\(j\ge2\)), özel cebine atma hamlesi etkin sol sınırı bir kare kaydırır. Boşluk diliyle bu, toplamı \(N+1\) olan ve ayrıca \(g_0>0\) koşulu taşıyan aynı xor-sıfır sayımına eşdeğerdir. Kod bu sayıya \(L_1\) der:
$$L_1=\text{Count}(N+1;\text{ways}_k)-\text{Count}(N+1;\text{ways}_{k-1}).$$
Çıkarma işlemi \(g_0=0\) olan durumları atar: ilk aktif boşluk sıfırsa xor'a katkı yapmaz ve problem \(k-1\) aktif boşluklu daha küçük aynı sayma problemine indirgenir.
Bu nedenle tek \(m\) için
$$L=L_0+(m-2)L_1$$
ve son olarak
$$W=T-L$$
olur.
\(\text{Count}(S;\text{ways})\) fonksiyonu toplamı \(S\) olan ve aktif boşlukları xor ile sıfır veren negatif olmayan boşluk vektörlerini sayar. \(n=10^6\) için bunu doğrudan denemek mümkün değildir; bu yüzden kod bit bit sayım yapar.
Tek bir ikili bit sütununa bakalım. \(k\) aktif boşluktan tam \(x\) tanesinin bu bitte 1 olduğunu varsayalım. O sütunda xor'un sıfır kalması için \(x\) sayısı çift olmalıdır. \(r\) pasif boşluktan tam \(y\) tanesi de 1 ise sütundaki toplam 1 sayısı \(s=x+y\) olur ve bu desenlerin sayısı
$$\binom{k}{x}\binom{r}{y}$$
şeklindedir. Çift tüm \(x\) değerleri üzerinden toplarsak DP'de kullanılan katsayı dizisini elde ederiz:
$$\text{ways}(s)=\sum_{\substack{0\le x\le k\\x\text{ çift}}}\binom{k}{x}\binom{r}{s-x},\qquad 0\le s\le k+r.$$
build_ways_even_* fonksiyonları tam olarak bu katsayıları kurar.
Sütun katsayıları bilindikten sonra geriye sadece tüm boşlukların aritmetik toplamının tam olarak \(S\) olmasını zorlamak kalır. Bunu yapan parça count_with_ways'dir.
\(S\)'nin bitlerini en düşük bitten en yüksek bite doğru işleyelim. \(b\). bitte içeri gelen taşıma \(c\), \(S\)'nin ilgili biti de \(\beta_b\in\{0,1\}\) olsun. Toplam sütun 1 sayısı \(s\) ise bu seçim ancak
$$s+c\equiv \beta_b\pmod2$$
olduğunda geçerlidir. Yeni taşıma da
$$c'=\frac{s+c-\beta_b}{2}$$
olur. Böylece geçiş formülü
$$dp_{b+1}(c')\mathrel{+}=dp_b(c)\cdot \text{ways}(s)$$
haline gelir. Bu, standart bir basamak-DP'dir; farkı, sütun çokluklarının aktif boşluklardaki xor-sıfır koşulunu zaten içine gömmüş olmasıdır.
Burada \(m=c+1=3\) ve \(N=n-m=7\) olur. Toplam konfigürasyon sayısı
$$T=3\binom{10}{3}=3\cdot120=360$$
çıkar. \(m\) tek olduğu için kaybeden sayısı iki parçaya ayrılır. Gümüş dolar ikinci paradaysa
$$L_0=\text{Count}(7;\text{ways}_2)=20,$$
üçüncü paradaysa
$$L_1=\text{Count}(8;\text{ways}_2)-\text{Count}(8;\text{ways}_1)=16.$$
Dolayısıyla
$$L=20+(3-2)\cdot16=36,$$
ve
$$W=360-36=324$$
elde edilir; bu da problemde verilen kontrol değeridir.
C++, Python ve Java çözümleri aynı hattı izler. Önce boşluk-katmanı katsayıları için küçük binom tabloları kurulur. Sonra build_ways_even_* ile \(\text{ways}(s)\) dizisi oluşturulur. Ardından count_with_ways_* taşımalı DP'yi çalıştırarak belirli bir toplamı tam olarak sayar. Son aşamada compute_W_*, çift/tek \(m\) formülleriyle kaybedenleri hesaplar ve bunları \(T\)'den çıkarır.
Nihai Euler girdisinde modül bileşiktir:
$$M=1000036000099=1000003\cdot1000033.$$
Bu nedenle kod binom katsayılarını iki asal mod altında faktöriyel ve ters faktöriyel tablolarıyla hesaplar, sonra Çin Kalan Teoremi ile birleştirir. C++ sürümü ayrıca \(W(10,2)\) ve \(W(100,10)\) kontrol noktalarını önce tam aritmetikle doğrular, ardından \(W(1\,000\,000,100)\) için modüler hesaba geçer.
Sabit \(m\) için tek bir Count çağrısı \(O(\log N)\) bit seviyesi dolaşır. Her seviyede \(O(m)\) taşıma durumu ve \(O(m)\) olası sütun toplamı denenir. Bu yüzden DP maliyeti
$$O(m^2\log N)$$
zaman ve \(O(m)\) bellek olur. Modüler binom katsayıları için faktöriyel / ters faktöriyel hazırlığı her asal mod için \(O(n)\) zaman alır.
Hay \(m=c+1\) monedas en una tira de \(n\) casillas y exactamente una de ellas es el dólar de plata. Un movimiento legal consiste en desplazar una moneda hacia la izquierda o en realizar el movimiento especial de embolsarse la moneda más a la izquierda. El primer jugador gana si y solo si termina embolsándose el dólar de plata.
Por tanto, debemos contar todas las configuraciones desde las que el primer jugador puede forzar ese resultado. Si primero elegimos las casillas ocupadas y después cuál de las \(m\) monedas es la especial, el número total de configuraciones brutas es
$$T=m\binom{n}{m}.$$
Escribamos las posiciones de las monedas como
$$0\le x_0 \lt x_1 \lt \cdots \lt x_{m-1}\le n-1.$$
En lugar de trabajar directamente con esas posiciones, el código usa los huecos:
$$g_0=x_0,\qquad g_i=x_i-x_{i-1}-1\ (1\le i\le m-1),\qquad g_m=n-1-x_{m-1}.$$
Son las casillas vacías antes de la primera moneda, entre monedas consecutivas y después de la última. Cada disposición corresponde de forma única a un vector no negativo \((g_0,\dots,g_m)\), y el número total de casillas vacías es
$$g_0+g_1+\cdots+g_m=n-m=:N.$$
De ahí que la implementación empiece con la reducción
$$m=c+1,\qquad N=n-m.$$
El hecho combinatorio clave es que el juego ordinario del silver dollar se describe mediante huecos alternos. Definimos
$$k=\left\lceil\frac{m}{2}\right\rceil,\qquad r=m-k+1.$$
Los huecos activos son los que entran en la condición xor:
Si \(m\) es par, los huecos activos son
$$g_1,g_3,\dots,g_{m-1}.$$
Si \(m\) es impar, los huecos activos son
$$g_0,g_2,\dots,g_{m-1}.$$
Los huecos restantes son pasivos: afectan a la longitud total, pero no a la condición xor.
En el juego ordinario, una posición es perdedora exactamente cuando el xor de los huecos activos es cero:
$$a_1\oplus a_2\oplus\cdots\oplus a_k=0,$$
donde \(\oplus\) es el xor bit a bit, es decir, la suma Nim. Así el problema geométrico sobre posiciones de monedas pasa a ser un problema de conteo de enteros no negativos con suma total fija y una restricción xor.
Ahora recuperamos el hecho de que una moneda es el dólar de plata y llamamos \(j\in\{0,\dots,m-1\}\) a su índice desde la izquierda.
1) Dólar de plata a la izquierda del todo. Si \(j=0\), el jugador actual lo embolsa inmediatamente y gana. Por tanto, esas posiciones nunca son perdedoras.
2) Número par de monedas. Si \(m\) es par y \(j\ge1\), las configuraciones perdedoras son exactamente las configuraciones ordinarias con xor cero. El dólar de plata puede estar en cualquiera de las \(m-1\) monedas no izquierdas, así que
$$L=(m-1)L_0,\qquad L_0=\text{Count}(N;\text{ways}_k).$$
3) Número impar de monedas. Si \(m\) es impar, aparecen dos familias:
Cuando el dólar de plata está en la segunda moneda (\(j=1\)), vuelve a aparecer el conteo ordinario xor-cero
$$L_0=\text{Count}(N;\text{ways}_k).$$
Cuando el dólar de plata está en la tercera moneda o más a la derecha (\(j\ge2\)), el movimiento especial desplaza en una casilla la frontera efectiva de la izquierda. En términos de huecos, esto se convierte en el mismo problema xor-cero, pero con suma total \(N+1\) y con la condición extra \(g_0>0\). El código llama a ese conteo \(L_1\):
$$L_1=\text{Count}(N+1;\text{ways}_k)-\text{Count}(N+1;\text{ways}_{k-1}).$$
La resta elimina exactamente los casos con \(g_0=0\): si el primer hueco activo vale cero, no aporta nada al xor y el problema se reduce al mismo conteo con solo \(k-1\) huecos activos.
Por tanto, para \(m\) impar,
$$L=L_0+(m-2)L_1,$$
y siempre
$$W=T-L.$$
La función \(\text{Count}(S;\text{ways})\) cuenta vectores de huecos no negativos cuya suma es \(S\) y cuyos huecos activos tienen xor cero. Enumerarlos de manera directa es imposible para \(n=10^6\), así que el código cuenta bit a bit.
Fijemos una columna binaria. Supongamos que exactamente \(x\) de los \(k\) huecos activos tienen un 1 en ese bit. Para que el xor de esa columna sea cero, \(x\) debe ser par. Si además exactamente \(y\) de los \(r\) huecos pasivos tienen un 1, entonces el número total de unos en esa columna es \(s=x+y\), y el número de asignaciones posibles es
$$\binom{k}{x}\binom{r}{y}.$$
Sumando sobre todos los \(x\) pares obtenemos el arreglo de coeficientes usado por la DP:
$$\text{ways}(s)=\sum_{\substack{0\le x\le k\\x\text{ par}}}\binom{k}{x}\binom{r}{s-x},\qquad 0\le s\le k+r.$$
Eso es exactamente lo que construye build_ways_even_*.
Una vez conocidos los coeficientes de columna, solo falta imponer que la suma aritmética total de todos los huecos sea exactamente \(S\). De eso se encarga count_with_ways.
Se procesan los bits de \(S\) de menor a mayor peso. Sea \(c\) el acarreo entrante en el bit \(b\), y sea \(\beta_b\in\{0,1\}\) el bit correspondiente de \(S\). Una elección de suma de columna \(s\) es válida exactamente cuando
$$s+c\equiv \beta_b\pmod2.$$
El nuevo acarreo es
$$c'=\frac{s+c-\beta_b}{2}.$$
Por tanto, la transición es
$$dp_{b+1}(c')\mathrel{+}=dp_b(c)\cdot \text{ways}(s).$$
Es una DP clásica por dígitos con acarreos, pero aquí las multiplicidades de columna ya incorporan la condición xor-cero de los huecos activos.
Aquí \(m=c+1=3\) y \(N=n-m=7\). El número total de configuraciones es
$$T=3\binom{10}{3}=3\cdot120=360.$$
Como \(m\) es impar, el número de posiciones perdedoras se divide en dos partes. Con el dólar de plata en la segunda moneda se obtiene
$$L_0=\text{Count}(7;\text{ways}_2)=20.$$
Con el dólar de plata en la tercera moneda se obtiene
$$L_1=\text{Count}(8;\text{ways}_2)-\text{Count}(8;\text{ways}_1)=16.$$
Luego
$$L=20+(3-2)\cdot16=36,$$
y
$$W=360-36=324,$$
en perfecto acuerdo con el valor publicado.
Las implementaciones en C++, Python y Java siguen exactamente el mismo esquema. Primero construyen tablas pequeñas de binomiales para la capa combinatoria de huecos. Después, build_ways_even_* arma el arreglo \(\text{ways}(s)\). A continuación, count_with_ways_* ejecuta la DP con acarreos para una suma objetivo exacta. Por último, compute_W_* aplica las fórmulas de \(m\) par / impar para el conteo de posiciones perdedoras y las resta de \(T\).
Para la entrada final de Euler, el módulo es compuesto:
$$M=1000036000099=1000003\cdot1000033.$$
Por ello, el código calcula los binomiales módulo cada primo usando tablas de factoriales e inversos factoriales y luego une ambos residuos mediante el Teorema Chino del Resto. La versión en C++ además valida exactamente los puntos de control pequeños antes de pasar a la aritmética modular para \(W(1\,000\,000,100)\).
Para \(m\) fijo, una llamada a Count recorre \(O(\log N)\) niveles de bits. Cada nivel considera \(O(m)\) estados de acarreo y \(O(m)\) posibles sumas de columna, así que el coste de la DP es
$$O(m^2\log N)$$
en tiempo y \(O(m)\) en memoria. La precomputación de factoriales e inversos factoriales para binomiales modulares cuesta \(O(n)\) por cada módulo primo.
在一条有 \(n\) 个格子的纸带上放着 \(m=c+1\) 枚硬币，其中恰好一枚是银元。一次合法操作要么把某一枚硬币向左移动若干格，要么执行特殊操作：把最左边的硬币装入口袋。谁最终把银元装入口袋，谁就获胜。
因此我们要求的是：有多少初始布局能让先手必胜。先选出被占据的格子，再决定这 \(m\) 枚硬币中哪一枚是银元，则原始配置总数为
$$T=m\binom{n}{m}.$$
把硬币位置写成
$$0\le x_0 \lt x_1 \lt \cdots \lt x_{m-1}\le n-1.$$
代码并不直接处理这些坐标，而是改用空隙变量：
$$g_0=x_0,\qquad g_i=x_i-x_{i-1}-1\ (1\le i\le m-1),\qquad g_m=n-1-x_{m-1}.$$
它们分别表示第一枚硬币左边的空格、相邻两枚硬币之间的空格、以及最后一枚硬币右边的空格。每一种摆法都唯一对应一个非负向量 \((g_0,\dots,g_m)\)，并且空格总数满足
$$g_0+g_1+\cdots+g_m=n-m=:N.$$
这就是实现一开始先做
$$m=c+1,\qquad N=n-m$$
这个参数变换的原因。
关键的组合事实是：普通 silver dollar 游戏可以转化为“交替空隙”的 Nim 结构。定义
$$k=\left\lceil\frac{m}{2}\right\rceil,\qquad r=m-k+1.$$
活跃空隙是进入异或条件的那些空隙：
若 \(m\) 为偶数，则活跃空隙是
$$g_1,g_3,\dots,g_{m-1}.$$
若 \(m\) 为奇数，则活跃空隙是
$$g_0,g_2,\dots,g_{m-1}.$$
其余空隙是被动空隙：它们会影响总长度，但不进入异或判据。
对普通 silver dollar 游戏来说，一个局面恰好在活跃空隙的异或为零时是必败局：
$$a_1\oplus a_2\oplus\cdots\oplus a_k=0,$$
其中 \(\oplus\) 表示按位 xor，也就是 Nim-sum。于是，原本关于几何位置的博弈问题，被转化成“总和固定且活跃分量异或为零”的非负整数计数问题。
现在重新考虑“哪一枚硬币是银元”这一信息，并设它从左往右的编号为 \(j\in\{0,\dots,m-1\}\)。
1) 银元若已在最左边，则一定不是必败局。 因为 \(j=0\) 时，当前玩家可以立刻把它装入口袋并获胜。
2) 当硬币数 \(m\) 为偶数时。 若 \(m\) 为偶数且 \(j\ge1\)，必败布局恰好就是普通 xor 为零的那些底层布局。银元可以是除最左边外任意一枚硬币，所以
$$L=(m-1)L_0,\qquad L_0=\text{Count}(N;\text{ways}_k).$$
3) 当硬币数 \(m\) 为奇数时。 这时会分成两类：
若银元在第二枚硬币上（\(j=1\)），仍然对应普通 xor 为零的计数
$$L_0=\text{Count}(N;\text{ways}_k).$$
若银元在第三枚或更右边（\(j\ge2\)），则特殊“装袋”操作会把有效左边界向右平移一格。用空隙语言表达，这等价于：总空隙和变成 \(N+1\)，同时要求 \(g_0>0\)，其余仍满足同样的 xor 为零条件。代码把这部分记为 \(L_1\)：
$$L_1=\text{Count}(N+1;\text{ways}_k)-\text{Count}(N+1;\text{ways}_{k-1}).$$
减去的那一项正是 \(g_0=0\) 的情况：当第一个活跃空隙为零时，它对异或没有贡献，问题就退化成只有 \(k-1\) 个活跃空隙的同类计数。
因此，当 \(m\) 为奇数时，
$$L=L_0+(m-2)L_1,$$
最终总胜局数为
$$W=T-L.$$
\(\text{Count}(S;\text{ways})\) 用来统计总和为 \(S\)、且活跃空隙异或为零的非负空隙向量。对于 \(n=10^6\)，显然不能暴力枚举，因此代码按二进制位逐列统计。
固定某一二进制位。假设 \(k\) 个活跃空隙中恰好有 \(x\) 个在这一位上是 1。要保证这一列的 xor 为零，\(x\) 必须是偶数。再设 \(r\) 个被动空隙中有 \(y\) 个在这一位上是 1，那么这一列总共有 \(s=x+y\) 个 1，而这种列模式的数量就是
$$\binom{k}{x}\binom{r}{y}.$$
对所有偶数 \(x\) 求和，就得到 DP 使用的系数数组：
$$\text{ways}(s)=\sum_{\substack{0\le x\le k\\x\text{ 为偶数}}}\binom{k}{x}\binom{r}{s-x},\qquad 0\le s\le k+r.$$
这正是 build_ways_even_* 在做的事。
当每一列的组合数已经知道后，还必须保证所有空隙的算术总和恰好等于 \(S\)。这就是 count_with_ways 的工作。
从低位到高位处理 \(S\) 的二进制展开。设第 \(b\) 位的输入进位为 \(c\)，而 \(S\) 的该位为 \(\beta_b\in\{0,1\}\)。若某次选择使这一列总共有 \(s\) 个 1，那么它合法当且仅当
$$s+c\equiv \beta_b\pmod2.$$
对应的输出进位为
$$c'=\frac{s+c-\beta_b}{2}.$$
于是转移公式就是
$$dp_{b+1}(c')\mathrel{+}=dp_b(c)\cdot \text{ways}(s).$$
这本质上是标准的数位 DP / 进位 DP，只不过列计数已经把“活跃空隙 xor 为零”的约束编码进去了。
此时 \(m=c+1=3\)，\(N=n-m=7\)。原始配置总数为
$$T=3\binom{10}{3}=3\cdot120=360.$$
由于 \(m\) 为奇数，必败局分成两部分。银元在第二枚硬币上时，有
$$L_0=\text{Count}(7;\text{ways}_2)=20.$$
银元在第三枚硬币上时，有
$$L_1=\text{Count}(8;\text{ways}_2)-\text{Count}(8;\text{ways}_1)=16.$$
因此
$$L=20+(3-2)\cdot16=36,$$
从而
$$W=360-36=324,$$
与题目给出的校验值一致。
C++、Python 和 Java 三份实现遵循完全相同的流程。先构造小范围二项式表，用于空隙层组合数。再由 build_ways_even_* 生成 \(\text{ways}(s)\) 数组。接着 count_with_ways_* 运行进位 DP 来统计精确目标和。最后 compute_W_* 根据 \(m\) 的奇偶套用不同的必败局公式，并从 \(T\) 中减去。
对最终 Euler 输入，模数是合数：
$$M=1000036000099=1000003\cdot1000033.$$
所以代码先在两个素数模下分别计算二项式系数（使用阶乘表和逆阶乘表），再用中国剩余定理把两个余数合并。C++ 版本还会先用精确整数验证 \(W(10,2)\) 与 \(W(100,10)\)，然后才转到 \(W(1\,000\,000,100)\) 的模运算。
对固定的 \(m\)，一次 Count 调用需要扫描 \(O(\log N)\) 个二进制位。每一层会遍历 \(O(m)\) 个进位状态以及 \(O(m)\) 个可能的列和，因此 DP 代价为
$$O(m^2\log N)$$
时间和 \(O(m)\) 空间。模二项式所需的阶乘 / 逆阶乘预处理，对每个素数模都是 \(O(n)\)。
На полосе из \(n\) клеток расположены \(m=c+1\) монет, и ровно одна из них является серебряным долларом. Разрешённый ход либо сдвигает одну монету влево, либо выполняет специальный ход: игрок забирает самую левую монету. Выигрывает тот, кто в итоге забирает серебряный доллар.
Следовательно, нужно посчитать все конфигурации, из которых первый игрок может это гарантировать. Если сначала выбрать занятые клетки, а затем указать, какая из \(m\) монет является серебряной, общее число исходных конфигураций равно
$$T=m\binom{n}{m}.$$
Пусть позиции монет имеют вид
$$0\le x_0 \lt x_1 \lt \cdots \lt x_{m-1}\le n-1.$$
Вместо самих координат код работает с зазорами:
$$g_0=x_0,\qquad g_i=x_i-x_{i-1}-1\ (1\le i\le m-1),\qquad g_m=n-1-x_{m-1}.$$
Это числа пустых клеток перед первой монетой, между соседними монетами и после последней монеты. Каждой расстановке соответствует единственный неотрицательный вектор \((g_0,\dots,g_m)\), причём суммарное число пустых клеток равно
$$g_0+g_1+\cdots+g_m=n-m=:N.$$
Именно поэтому реализация начинает с замены параметров
$$m=c+1,\qquad N=n-m.$$
Ключевой комбинаторный факт состоит в том, что обычная игра silver dollar описывается через чередующиеся зазоры. Обозначим
$$k=\left\lceil\frac{m}{2}\right\rceil,\qquad r=m-k+1.$$
Активные зазоры участвуют в xor-условии:
если \(m\) чётно, активны
$$g_1,g_3,\dots,g_{m-1}.$$
если \(m\) нечётно, активны
$$g_0,g_2,\dots,g_{m-1}.$$
Остальные зазоры пассивны: они влияют на общую длину, но не на xor-критерий.
Для обычной игры позиция проигрышна тогда и только тогда, когда xor активных зазоров равен нулю:
$$a_1\oplus a_2\oplus\cdots\oplus a_k=0,$$
где \(\oplus\) обозначает побитовое xor, то есть Nim-сумму. Тем самым задача о геометрическом расположении монет превращается в задачу подсчёта неотрицательных целых чисел с фиксированной суммой и xor-ограничением.
Теперь снова выделим серебряный доллар среди монет и обозначим его номер слева через \(j\in\{0,\dots,m-1\}\).
1) Серебряный доллар слева. Если \(j=0\), текущий игрок немедленно забирает его и выигрывает. Такие позиции никогда не являются проигрышными.
2) Чётное число монет. Если \(m\) чётно и \(j\ge1\), проигрышные конфигурации совпадают с обычными xor-нулевыми конфигурациями. Серебряный доллар может стоять на любой из \(m-1\) не самых левых монет, поэтому
$$L=(m-1)L_0,\qquad L_0=\text{Count}(N;\text{ways}_k).$$
3) Нечётное число монет. Если \(m\) нечётно, возникают две семьи:
когда серебряный доллар стоит на второй монете (\(j=1\)), снова получаем обычный xor-нулевой подсчёт
$$L_0=\text{Count}(N;\text{ways}_k).$$
когда серебряный доллар стоит на третьей или более правой монете (\(j\ge2\)), специальный ход сдвигает эффективную левую границу на одну клетку. В терминах зазоров это превращается в тот же xor-нулевой подсчёт, но для суммы \(N+1\) и с дополнительным условием \(g_0>0\). В коде эта величина обозначена как \(L_1\):
$$L_1=\text{Count}(N+1;\text{ways}_k)-\text{Count}(N+1;\text{ways}_{k-1}).$$
Вычитание убирает случаи \(g_0=0\): тогда первый активный зазор не влияет на xor и задача сводится к тому же подсчёту с \(k-1\) активными зазорами.
Итак, для нечётного \(m\)
$$L=L_0+(m-2)L_1,$$
а число выигрышных конфигураций равно
$$W=T-L.$$
Функция \(\text{Count}(S;\text{ways})\) считает неотрицательные векторы зазоров с суммой \(S\), у которых xor активных зазоров равен нулю. Прямой перебор невозможен уже для \(n=10^6\), поэтому код считает по битам.
Зафиксируем один двоичный разряд. Пусть ровно \(x\) из \(k\) активных зазоров имеют в этом разряде единицу. Чтобы xor в этом столбце был равен нулю, число \(x\) должно быть чётным. Если ещё ровно \(y\) из \(r\) пассивных зазоров имеют единицу, то всего единиц в столбце \(s=x+y\), а число таких выборов равно
$$\binom{k}{x}\binom{r}{y}.$$
Суммируя по всем чётным \(x\), получаем коэффициенты, используемые в DP:
$$\text{ways}(s)=\sum_{\substack{0\le x\le k\\x\text{ чётно}}}\binom{k}{x}\binom{r}{s-x},\qquad 0\le s\le k+r.$$
Именно это строит функция build_ways_even_*.
После того как известны коэффициенты по столбцам, остаётся навязать точную арифметическую сумму \(S\). Этим занимается count_with_ways.
Биты числа \(S\) обрабатываются от младшего к старшему. Пусть \(c\) — входящий перенос на бите \(b\), а \(\beta_b\in\{0,1\}\) — \(b\)-й бит числа \(S\). Если выбран столбец с суммой единиц \(s\), то он допустим тогда и только тогда, когда
$$s+c\equiv \beta_b\pmod2.$$
Новый перенос равен
$$c'=\frac{s+c-\beta_b}{2}.$$
Поэтому переход имеет вид
$$dp_{b+1}(c')\mathrel{+}=dp_b(c)\cdot \text{ways}(s).$$
Это стандартное цифровое DP с переносами, но здесь столбцовые кратности уже кодируют условие xor = 0 на активных зазорах.
Здесь \(m=c+1=3\) и \(N=n-m=7\). Общее число конфигураций равно
$$T=3\binom{10}{3}=3\cdot120=360.$$
Поскольку \(m\) нечётно, число проигрышных позиций делится на две части. Для серебряного доллара на второй монете получаем
$$L_0=\text{Count}(7;\text{ways}_2)=20.$$
Для серебряного доллара на третьей монете получаем
$$L_1=\text{Count}(8;\text{ways}_2)-\text{Count}(8;\text{ways}_1)=16.$$
Следовательно,
$$L=20+(3-2)\cdot16=36,$$
и потому
$$W=360-36=324,$$
что совпадает с опубликованной контрольной точкой.
Реализации на C++, Python и Java следуют одной и той же схеме. Сначала строятся малые биномиальные таблицы для коэффициентов слоя зазоров. Затем build_ways_even_* формирует массив \(\text{ways}(s)\). После этого count_with_ways_* запускает DP с переносами для точной целевой суммы. Наконец, compute_W_* применяет формулы для чётного / нечётного \(m\) и вычитает число проигрышных конфигураций из \(T\).
Для финального входа Euler модуль составной:
$$M=1000036000099=1000003\cdot1000033.$$
Поэтому биномиальные коэффициенты считаются по каждому простому модулю с помощью таблиц факториалов и обратных факториалов, а затем остатки объединяются китайской теоремой об остатках. Версия на C++ дополнительно точно проверяет малые контрольные значения, прежде чем перейти к модульной арифметике для \(W(1\,000\,000,100)\).
Для фиксированного \(m\) один вызов Count проходит по \(O(\log N)\) битовым уровням. На каждом уровне рассматриваются \(O(m)\) состояний переноса и \(O(m)\) возможных сумм столбца, так что стоимость DP равна
$$O(m^2\log N)$$
по времени и \(O(m)\) по памяти. Предварительное вычисление факториалов и обратных факториалов для модульных биномиальных коэффициентов требует \(O(n)\) для каждого простого модуля.
على شريط طوله \(n\) خانات توجد \(m=c+1\) عملات، وإحدى هذه العملات فقط هي الدولار الفضي. الحركة القانونية إمّا نقل عملة واحدة إلى اليسار، أو القيام بالحركة الخاصة وهي وضع العملة اليسرى الأبعد في الجيب. يفوز اللاعب الذي ينجح في وضع الدولار الفضي في جيبه في النهاية.
إذًا علينا أن نعدّ كل الترتيبات التي يستطيع منها اللاعب الأول فرض هذه النتيجة. إذا اخترنا أولًا الخانات المشغولة ثم اخترنا أيّ عملة من العملات \(m\) هي الدولار الفضي، فإن العدد الكلي للحالات الخام يساوي
$$T=m\binom{n}{m}.$$
لنكتب مواضع العملات بالشكل
$$0\le x_0 \lt x_1 \lt \cdots \lt x_{m-1}\le n-1.$$
بدلًا من التعامل مع الإحداثيات مباشرة، يستخدم الكود الفجوات:
$$g_0=x_0,\qquad g_i=x_i-x_{i-1}-1\ (1\le i\le m-1),\qquad g_m=n-1-x_{m-1}.$$
وهذه تمثل عدد الخانات الفارغة قبل أول عملة، وبين كل عملتين متتاليتين، وبعد آخر عملة. كل توزيع للعملات يقابله متجه وحيد غير سالب \((g_0,\dots,g_m)\)، ويكون مجموع الخانات الفارغة
$$g_0+g_1+\cdots+g_m=n-m=:N.$$
ولهذا يبدأ الحل بالتحويل
$$m=c+1,\qquad N=n-m.$$
الحقيقة التوافقية الأساسية هي أن لعبة silver dollar العادية يمكن وصفها بواسطة فجوات متناوبة. نعرّف
$$k=\left\lceil\frac{m}{2}\right\rceil,\qquad r=m-k+1.$$
الفجوات الفعالة هي التي تدخل في شرط xor:
إذا كان \(m\) زوجيًا فالفجوات الفعالة هي
$$g_1,g_3,\dots,g_{m-1}.$$
وإذا كان \(m\) فرديًا فالفجوات الفعالة هي
$$g_0,g_2,\dots,g_{m-1}.$$
أما الفجوات الأخرى فهي فجوات غير فعالة: تؤثر في الطول الكلي لكنها لا تدخل في شرط xor.
في لعبة silver dollar العادية تكون الوضعية خاسرة بالضبط عندما يكون xor للفجوات الفعالة مساويًا للصفر:
$$a_1\oplus a_2\oplus\cdots\oplus a_k=0,$$
حيث ترمز \(\oplus\) إلى xor الثنائي، أي مجموع Nim. وهكذا تتحول مسألة ترتيب العملات على الشريط إلى مسألة عدّ أعداد غير سالبة مجموعها ثابت وتخضع لقيد xor.
الآن نعيد إدخال حقيقة أن إحدى العملات مميزة بوصفها الدولار الفضي، ولْنرمز إلى ترتيبها من اليسار بـ \(j\in\{0,\dots,m-1\}\).
1) الدولار الفضي في أقصى اليسار. إذا كان \(j=0\)، فإن اللاعب الحالي يضعه مباشرة في الجيب ويفوز. لذلك لا تكون هذه المواضع خاسرة أبدًا.
2) عندما يكون عدد العملات زوجيًا. إذا كان \(m\) زوجيًا و\(j\ge1\)، فإن المواضع الخاسرة هي بالضبط المواضع العادية التي تحقق xor = 0. وبما أن الدولار الفضي يمكن أن يكون في أي واحدة من العملات \(m-1\) غير اليسرى، نحصل على
$$L=(m-1)L_0,\qquad L_0=\text{Count}(N;\text{ways}_k).$$
3) عندما يكون عدد العملات فرديًا. في هذه الحالة تظهر عائلتان:
إذا كان الدولار الفضي في العملة الثانية (\(j=1\)) فإننا نحصل من جديد على العدّ العادي الموافق لشرط xor = 0:
$$L_0=\text{Count}(N;\text{ways}_k).$$
أما إذا كان الدولار الفضي في العملة الثالثة أو أبعد إلى اليمين (\(j\ge2\))، فإن الحركة الخاصة تغيّر الحد الأيسر الفعّال بمقدار خانة واحدة. وبلغة الفجوات يصبح هذا هو نفس عدّ xor = 0 ولكن مع مجموع كلي \(N+1\) ومع الشرط الإضافي \(g_0>0\). ويسمّي الكود هذه الكمية \(L_1\):
$$L_1=\text{Count}(N+1;\text{ways}_k)-\text{Count}(N+1;\text{ways}_{k-1}).$$
الطرح يزيل تمامًا الحالات التي فيها \(g_0=0\): فعندما تكون أول فجوة فعالة صفرًا فإنها لا تسهم في xor، وتنهار المسألة إلى العدّ نفسه لكن مع \(k-1\) فجوات فعالة فقط.
وعليه، عندما يكون \(m\) فرديًا،
$$L=L_0+(m-2)L_1,$$
ثم يكون عدد الوضعيات الرابحة دائمًا
$$W=T-L.$$
الدالة \(\text{Count}(S;\text{ways})\) تعدّ متجهات الفجوات غير السالبة التي مجموعها \(S\) ويكون xor للفجوات الفعالة فيها مساويًا للصفر. التعداد المباشر مستحيل عندما \(n=10^6\)، لذلك يعتمد الكود على العدّ خانةً ثنائيةً بخانة.
لنثبت خانة ثنائية واحدة. إذا كان عدد الفجوات الفعالة التي تحتوي على 1 في هذه الخانة هو \(x\)، فيجب أن يكون \(x\) زوجيًا حتى يبقى xor في هذه الخانة صفرًا. وإذا كان عدد الفجوات غير الفعالة التي تحتوي على 1 في الخانة نفسها هو \(y\)، فإن العدد الكلي للواحدات في هذا العمود هو \(s=x+y\)، وعدد التعيينات الممكنة يساوي
$$\binom{k}{x}\binom{r}{y}.$$
وبالجمع على كل القيم الزوجية لـ \(x\) نحصل على مصفوفة المعاملات التي تستخدمها البرمجة الديناميكية:
$$\text{ways}(s)=\sum_{\substack{0\le x\le k\\x\text{ زوجي}}}\binom{k}{x}\binom{r}{s-x},\qquad 0\le s\le k+r.$$
وهذا بالضبط ما تبنيه الدالة build_ways_even_*.
بعد معرفة معاملات الأعمدة، يتبقى فرض أن المجموع الحسابي الكامل لكل الفجوات يساوي \(S\) تمامًا. هذا هو دور count_with_ways.
نعالج البتات في التمثيل الثنائي للعدد \(S\) من الأقل أهمية إلى الأعلى. إذا كان الحمل الداخل عند البت \(b\) هو \(c\)، وكان البت الموافق في \(S\) هو \(\beta_b\in\{0,1\}\)، فإن اختيار عمود مجموع واحداته \(s\) يكون صالحًا إذا وفقط إذا
$$s+c\equiv \beta_b\pmod2.$$
ويكون الحمل الخارج
$$c'=\frac{s+c-\beta_b}{2}.$$
وبالتالي يكون الانتقال
$$dp_{b+1}(c')\mathrel{+}=dp_b(c)\cdot \text{ways}(s).$$
هذه برمجة ديناميكية معيارية على الأرقام والحمل، لكن معاملات الأعمدة هنا تحمل أصلًا شرط xor الصفري للفجوات الفعالة.
هنا \(m=c+1=3\) و\(N=n-m=7\). العدد الكلي للحالات هو
$$T=3\binom{10}{3}=3\cdot120=360.$$
وبما أن \(m\) فردي، ينقسم عدد الحالات الخاسرة إلى جزأين. عندما يكون الدولار الفضي في العملة الثانية نحصل على
$$L_0=\text{Count}(7;\text{ways}_2)=20.$$
وعندما يكون في العملة الثالثة نحصل على
$$L_1=\text{Count}(8;\text{ways}_2)-\text{Count}(8;\text{ways}_1)=16.$$
إذن
$$L=20+(3-2)\cdot16=36,$$
ومن ثم
$$W=360-36=324,$$
وهو تمامًا مقدار التحقق المذكور في نص المسألة.
إصدارات C++ وPython وJava تتبع جميعها المسار نفسه. أولًا تُبنى جداول ثنائية صغيرة لمعاملات طبقة الفجوات. بعد ذلك تُنشئ build_ways_even_* المصفوفة \(\text{ways}(s)\). ثم تُشغّل count_with_ways_* البرمجة الديناميكية ذات الحمل من أجل مجموع هدف دقيق. وأخيرًا تطبّق compute_W_* صيغتي الحالة الزوجية / الفردية لعدد الحالات الخاسرة وتطرحها من \(T\).
في إدخال Euler النهائي يكون المودولو مركبًا:
$$M=1000036000099=1000003\cdot1000033.$$
ولهذا يحسب الكود معاملات ثنائية الحد modulo كل عدد أولي على حدة باستخدام جداول المضروب ومعكوس المضروب، ثم يدمج الباقيين بواسطة نظرية البواقي الصينية. كما أن نسخة C++ تتحقق أولًا من القيم الصغيرة بدقة كاملة قبل أن تنتقل إلى الحساب المعياري من أجل \(W(1\,000\,000,100)\).
لـ \(m\) ثابت، فإن استدعاءً واحدًا للدالة Count يمر عبر \(O(\log N)\) من مستويات البتات. وفي كل مستوى توجد \(O(m)\) حالات حمل و\(O(m)\) مجاميع أعمدة ممكنة، لذا تكون كلفة البرمجة الديناميكية
$$O(m^2\log N)$$
زمنًا و\(O(m)\) ذاكرةً. أما التهيئة المسبقة لجداول المضروب ومعكوسه لحساب معاملات ثنائية الحد modulo الأعداد الأولية فتتكلف \(O(n)\) لكل مود أولي.