We consider three distinct heap sizes \(a\lt b\lt c\). A legal move decreases exactly one heap to a smaller nonnegative size, after which the three heap sizes are reordered and must still be distinct. Let \(\mathcal{P}\) denote the set of losing positions for this game.
Define \(\mathcal{P}_N=\{(a,b,c)\in\mathcal{P}: 0\lt a\lt b\lt c\lt N\}\).
The quantity to compute is
$$F(N)=\sum_{(a,b,c)\in\mathcal{P}_N}(a+b+c)\pmod{10^9}.$$
A direct search over all triples below \(N\) is only feasible for tiny bounds. The implementation avoids that cubic search space by using a structural parametrization of all losing positions and then summing each block in closed form.
The main game-specific fact used by the implementation is that every losing position belongs to a unique dyadic block indexed by
$$p=2^k-1,\qquad k\ge 1,$$
and inside that block the losing triples are exactly
$$c=p+n,\qquad b=p+t,\qquad a=(n\oplus t)-1,$$
with
$$1\le n\le p,\qquad 0\le t\lt n.$$
Here \(\oplus\) is bitwise XOR. Because \(c=p+n\) lies in the interval \(p+1\le c\le 2p\), the largest heap chooses the block uniquely, so different values of \(k\) never overlap.
To contribute to \(F(N)\), the largest heap must satisfy \(c\lt N\). Since \(c=p+n\), this becomes
$$p+n\lt N\iff n\le N-1-p.$$
Therefore the relevant range of \(n\) is
$$1\le n\le m,\qquad m=\min\{p,\ N-1-p\}.$$
For each such \(n\), the parameter \(t\) runs through \(0,1,\dots,n-1\), which automatically ensures \(b\lt c\).
Fix a block parameter \(p\). For a fixed \(n\), summing over all allowed \(t\) gives
$$a+b+c=(n\oplus t)-1+(p+t)+(p+n).$$
Define the XOR row sum
$$X(n)=\sum_{t=0}^{n-1}(n\oplus t).$$
Then
$$\sum_{t=0}^{n-1}(a+b+c)=X(n)+\sum_{t=0}^{n-1}t+n^2+n(2p-1).$$
Because \(\sum_{t=0}^{n-1}t=\frac{n(n-1)}{2}\), the raw contribution of the block is
$$\sum_{n=1}^{m}\left(X(n)+\frac{n(n-1)}{2}+n^2+(2p-1)n\right).$$
So the whole problem reduces to four standard sums:
$$\sum_{n=1}^{m}X(n),\qquad \sum_{n=1}^{m}n,\qquad \sum_{n=1}^{m}n^2,\qquad \sum_{n=1}^{m}\frac{n(n-1)}{2}.$$
The ordinary arithmetic sums are classical:
$$\sum_{n=1}^{m}n=\frac{m(m+1)}{2},$$
$$\sum_{n=1}^{m}n^2=\frac{m(m+1)(2m+1)}{6},$$
$$\sum_{n=1}^{m}\frac{n(n-1)}{2}=\frac{m(m+1)(m-1)}{6}.$$
The implementation evaluates these formulas exactly by dividing by \(2\) and \(3\) before modular multiplication, so everything remains valid modulo \(10^9\).
Set \(X(0)=0\) and define
$$S(n)=\sum_{i=0}^{n-1}X(i).$$
Then the needed XOR contribution is simply \(\sum_{n=1}^{m}X(n)=S(m+1)\).
To evaluate \(S\) quickly, write
$$n=2^m+r,\qquad 0\le r\lt 2^m,$$
and let \(p=2^m\). For \(0\le r\lt p\), split the definition of \(X(p+r)\) into two ranges:
$$X(p+r)=\sum_{t=0}^{p-1}((p+r)\oplus t)+\sum_{u=0}^{r-1}((p+r)\oplus(p+u)).$$
In the first sum the top bit stays set, so \((p+r)\oplus t=p+(r\oplus t)\). As \(t\) runs through \(0,\dots,p-1\), the values \(r\oplus t\) are a permutation of \(0,\dots,p-1\). Hence
$$\sum_{t=0}^{p-1}((p+r)\oplus t)=p^2+\sum_{v=0}^{p-1}v=p^2+\frac{p(p-1)}{2}=\frac{p(3p-1)}{2}.$$
In the second sum the top bit cancels, so \((p+r)\oplus(p+u)=r\oplus u\). Therefore
$$X(p+r)=C_m+X(r),\qquad C_m=\frac{2^m(3\cdot 2^m-1)}{2}.$$
Summing this identity over \(r\) gives the key recursion
$$\boxed{S(2^m+r)=S(2^m)+r\,C_m+S(r).}$$
For powers of two we get
$$S(2^{m+1})=2S(2^m)+2^mC_m,$$
so the implementation precomputes \(S(2^m)\) and \(C_m\) once and then evaluates any \(S(n)\) in \(O(\log n)\) recursive steps.
The parametrization above also produces states whose smallest heap is \(a=0\). These states appear naturally in the game graph, but they are not part of \(F(N)\), which only sums \(0\lt a\lt b\lt c\).
We have \(a=0\) exactly when
$$n\oplus t=1,$$
so the candidate is \(t=n\oplus 1\). This is inside the legal range \(0\le t\lt n\) if and only if \(n\) is odd, in which case \(t=n-1\). Thus each odd \(n\) contributes exactly one invalid triple.
For odd \(n\), the excluded sum equals
$$0+(p+n-1)+(p+n)=2p+2n-1.$$
If
$$q=\left\lfloor\frac{m+1}{2}\right\rfloor,$$
then the odd integers in \([1,m]\) are \(1,3,\dots,2q-1\), so
$$\sum_{\substack{1\le n\le m\\ 2\nmid n}}1=q,\qquad \sum_{\substack{1\le n\le m\\ 2\nmid n}}n=q^2.$$
Therefore the correction term for one block is
$$\boxed{(2p-1)q+2q^2.}$$
Combining the raw block sum with the odd-\(n\) correction, the contribution of block \(p=2^k-1\) is
$$\begin{aligned} B(p,m)=&\ S(m+1)+\frac{m(m+1)(m-1)}{6}+\frac{m(m+1)(2m+1)}{6}\\ &+(2p-1)\frac{m(m+1)}{2}-\left((2p-1)q+2q^2\right), \end{aligned}$$
where
$$m=\min\{p,\ N-1-p\},\qquad q=\left\lfloor\frac{m+1}{2}\right\rfloor.$$
Hence the whole answer is
$$\boxed{F(N)=\sum_{\substack{k\ge 1\\ 2^k\lt N}} B(2^k-1,\ \min\{2^k-1,\ N-2^k\})\pmod{10^9}.}$$
After the structural theorem about losing positions, everything else is pure arithmetic.
For \(N=8\), the only possible blocks are \(p=1\) and \(p=3\).
For \(p=1\), we have \(m=1\). The unique parametrized triple is \((0,1,2)\), so the entire block disappears after the \(a=0\) correction.
For \(p=3\), we have \(m=3\). First compute
$$X(1)=1,\qquad X(2)=2+3=5,\qquad X(3)=3+2+1=6,$$
hence
$$\sum_{n=1}^{3}X(n)=12,\qquad \sum_{n=1}^{3}n=6,\qquad \sum_{n=1}^{3}n^2=14,\qquad \sum_{n=1}^{3}\frac{n(n-1)}{2}=4.$$
The raw block total is
$$12+14+4+(2\cdot 3-1)\cdot 6=12+14+4+30=60.$$
Now \(q=\left\lfloor\frac{3+1}{2}\right\rfloor=2\), so the correction is
$$(2\cdot 3-1)\cdot 2+2\cdot 2^2=10+8=18.$$
Therefore
$$F(8)=60-18=42,$$
which matches the checkpoint used by the implementation. A second checkpoint is \(F(128)=496062\).
The C++, Python, and Java implementations all follow the same plan. They enumerate the dyadic blocks \(p=2^k-1\) with \(p+1\lt N\), compute the cutoff \(m=\min\{p,N-1-p\}\), and add the closed-form block contribution modulo \(10^9\).
The only nontrivial subroutine is the evaluator for \(S(n)\). It uses the recursion above together with precomputed values at powers of two, so no block ever loops over all \(t\) or all \(n\). Because different blocks are independent, the outer accumulation can also be split across worker threads or processes.
There are \(O(\log N)\) dyadic blocks because \(p=2^k-1\). Each block requires only a constant number of modular polynomial sums plus one evaluation of \(S(m+1)\), and the recursion for \(S\) has depth \(O(\log N)\). Therefore the total running time is
$$O((\log N)^2),$$
and the memory usage is \(O(\log N)\) for the precomputed tables of powers of two. This is exponentially smaller than any direct exploration of all triples below \(N\).
Wir betrachten drei verschiedene Haufengrößen \(a\lt b\lt c\). Ein Zug verkleinert genau einen Haufen auf eine kleinere nichtnegative Größe; anschließend wird neu sortiert, und die drei Werte müssen weiterhin verschieden sein. Sei \(\mathcal{P}\) die Menge aller Verlustpositionen dieses Spiels.
Definiere \(\mathcal{P}_N=\{(a,b,c)\in\mathcal{P}: 0\lt a\lt b\lt c\lt N\}\).
Gesucht ist
$$F(N)=\sum_{(a,b,c)\in\mathcal{P}_N}(a+b+c)\pmod{10^9}.$$
Ein direktes Durchprobieren aller Tripel unterhalb von \(N\) funktioniert nur für sehr kleine Schranken. Die Implementierung vermeidet diesen kubischen Zustandsraum durch eine strukturelle Beschreibung aller Verlustpositionen und summiert dann jeden Block in geschlossener Form.
Die zentrale spieltheoretische Tatsache, auf der die Implementierung beruht, lautet: Jede Verlustposition liegt in genau einem dyadischen Block mit
$$p=2^k-1,\qquad k\ge 1,$$
und innerhalb dieses Blocks haben die Verlusttripel die Form
$$c=p+n,\qquad b=p+t,\qquad a=(n\oplus t)-1,$$
mit
$$1\le n\le p,\qquad 0\le t\lt n.$$
Dabei bezeichnet \(\oplus\) das bitweise XOR. Weil \(c=p+n\) stets im Intervall \(p+1\le c\le 2p\) liegt, bestimmt der größte Haufen den Block eindeutig; verschiedene \(k\)-Werte überlappen also nicht.
Für einen Beitrag zu \(F(N)\) muss der größte Haufen \(c\lt N\) erfüllen. Aus \(c=p+n\) folgt
$$p+n\lt N\iff n\le N-1-p.$$
Also bleibt nur der Bereich
$$1\le n\le m,\qquad m=\min\{p,\ N-1-p\}.$$
Für jedes solche \(n\) läuft \(t\) durch \(0,1,\dots,n-1\); damit ist automatisch \(b\lt c\) gesichert.
Fixiere \(p\). Für festes \(n\) ergibt das Summieren über alle zulässigen \(t\)
$$a+b+c=(n\oplus t)-1+(p+t)+(p+n).$$
Definiere die XOR-Zeilensumme
$$X(n)=\sum_{t=0}^{n-1}(n\oplus t).$$
Dann gilt
$$\sum_{t=0}^{n-1}(a+b+c)=X(n)+\sum_{t=0}^{n-1}t+n^2+n(2p-1).$$
Mit \(\sum_{t=0}^{n-1}t=\frac{n(n-1)}{2}\) erhält man als rohen Blockbeitrag
$$\sum_{n=1}^{m}\left(X(n)+\frac{n(n-1)}{2}+n^2+(2p-1)n\right).$$
Damit reduziert sich das Problem auf vier Standardsummen:
$$\sum_{n=1}^{m}X(n),\qquad \sum_{n=1}^{m}n,\qquad \sum_{n=1}^{m}n^2,\qquad \sum_{n=1}^{m}\frac{n(n-1)}{2}.$$
Die gewöhnlichen Summen lauten
$$\sum_{n=1}^{m}n=\frac{m(m+1)}{2},$$
$$\sum_{n=1}^{m}n^2=\frac{m(m+1)(2m+1)}{6},$$
$$\sum_{n=1}^{m}\frac{n(n-1)}{2}=\frac{m(m+1)(m-1)}{6}.$$
Die Implementierung wertet diese Ausdrücke exakt aus, indem sie vor der modularen Multiplikation durch \(2\) und \(3\) teilt. So bleibt alles korrekt modulo \(10^9\).
Setze \(X(0)=0\) und definiere
$$S(n)=\sum_{i=0}^{n-1}X(i).$$
Dann ist die benötigte XOR-Summe gleich \(\sum_{n=1}^{m}X(n)=S(m+1)\).
Für eine schnelle Auswertung schreibe
$$n=2^m+r,\qquad 0\le r\lt 2^m,$$
und setze \(p=2^m\). Für \(0\le r\lt p\) zerlegt man \(X(p+r)\) in zwei Teile:
$$X(p+r)=\sum_{t=0}^{p-1}((p+r)\oplus t)+\sum_{u=0}^{r-1}((p+r)\oplus(p+u)).$$
Im ersten Teil bleibt das höchste Bit gesetzt, also \((p+r)\oplus t=p+(r\oplus t)\). Wenn \(t\) durch \(0,\dots,p-1\) läuft, ist \(r\oplus t\) lediglich eine Permutation von \(0,\dots,p-1\). Deshalb
$$\sum_{t=0}^{p-1}((p+r)\oplus t)=p^2+\sum_{v=0}^{p-1}v=p^2+\frac{p(p-1)}{2}=\frac{p(3p-1)}{2}.$$
Im zweiten Teil hebt sich das höchste Bit weg, daher \((p+r)\oplus(p+u)=r\oplus u\). Somit
$$X(p+r)=C_m+X(r),\qquad C_m=\frac{2^m(3\cdot 2^m-1)}{2}.$$
Durch Summation über \(r\) folgt die Rekursion
$$\boxed{S(2^m+r)=S(2^m)+r\,C_m+S(r).}$$
Für Zweierpotenzen vereinfacht sich das zu
$$S(2^{m+1})=2S(2^m)+2^mC_m,$$
weshalb die Implementierung \(S(2^m)\) und \(C_m\) vorab speichert und dann jedes \(S(n)\) in \(O(\log n)\) Schritten berechnet.
Die Parametrisierung erzeugt auch Zustände mit kleinstem Haufen \(a=0\). Solche Zustände gehören zwar zur Spielstruktur, werden aber in \(F(N)\) nicht mitgezählt, weil dort \(0\lt a\lt b\lt c\) gefordert ist.
Es gilt \(a=0\) genau dann, wenn
$$n\oplus t=1,$$
also wäre der Kandidat \(t=n\oplus 1\). Dieser liegt genau dann im erlaubten Bereich \(0\le t\lt n\), wenn \(n\) ungerade ist; dann ist \(t=n-1\). Für jedes ungerade \(n\) gibt es also genau ein ungültiges Tripel.
Für ungerades \(n\) lautet die auszuschließende Summe
$$0+(p+n-1)+(p+n)=2p+2n-1.$$
Mit
$$q=\left\lfloor\frac{m+1}{2}\right\rfloor$$
sind die ungeraden Zahlen in \([1,m]\) gleich \(1,3,\dots,2q-1\), also
$$\sum_{\substack{1\le n\le m\\ 2\nmid n}}1=q,\qquad \sum_{\substack{1\le n\le m\\ 2\nmid n}}n=q^2.$$
Damit ist der Korrekturterm eines Blocks
$$\boxed{(2p-1)q+2q^2.}$$
Setzt man alles zusammen, so ist der Beitrag des Blocks \(p=2^k-1\)
$$\begin{aligned} B(p,m)=&\ S(m+1)+\frac{m(m+1)(m-1)}{6}+\frac{m(m+1)(2m+1)}{6}\\ &+(2p-1)\frac{m(m+1)}{2}-\left((2p-1)q+2q^2\right), \end{aligned}$$
wobei
$$m=\min\{p,\ N-1-p\},\qquad q=\left\lfloor\frac{m+1}{2}\right\rfloor.$$
Daraus folgt insgesamt
$$\boxed{F(N)=\sum_{\substack{k\ge 1\\ 2^k\lt N}} B(2^k-1,\ \min\{2^k-1,\ N-2^k\})\pmod{10^9}.}$$
Nach dem strukturellen Satz über die Verlustpositionen bleibt also nur noch arithmetische Auswertung.
Für \(N=8\) kommen nur die Blöcke \(p=1\) und \(p=3\) vor.
Bei \(p=1\) ist \(m=1\). Das einzige parametrisierte Tripel ist \((0,1,2)\); nach der \(a=0\)-Korrektur trägt dieser Block also \(0\) bei.
Für \(p=3\) ist \(m=3\). Zunächst
$$X(1)=1,\qquad X(2)=2+3=5,\qquad X(3)=3+2+1=6,$$
also
$$\sum_{n=1}^{3}X(n)=12,\qquad \sum_{n=1}^{3}n=6,\qquad \sum_{n=1}^{3}n^2=14,\qquad \sum_{n=1}^{3}\frac{n(n-1)}{2}=4.$$
Der rohe Blockwert ist damit
$$12+14+4+(2\cdot 3-1)\cdot 6=60.$$
Nun ist \(q=\left\lfloor\frac{3+1}{2}\right\rfloor=2\), also beträgt die Korrektur
$$(2\cdot 3-1)\cdot 2+2\cdot 2^2=18.$$
Folglich
$$F(8)=60-18=42,$$
genau der Kontrollwert der Implementierung. Ein weiterer Prüfwert ist \(F(128)=496062\).
Die C++-, Python- und Java-Implementierungen verfolgen dieselbe Strategie. Sie zählen alle Blöcke \(p=2^k-1\) mit \(p+1\lt N\) auf, berechnen den abgeschnittenen Parameter \(m=\min\{p,N-1-p\}\) und addieren den geschlossenen Blockbeitrag modulo \(10^9\).
Die einzige nichttriviale Unterroutine ist die Auswertung von \(S(n)\). Dank der obigen Rekursion und der vorab berechneten Werte an Zweierpotenzen ist in keinem Block eine Schleife über alle \(t\) oder alle \(n\) nötig. Weil die Blöcke unabhängig sind, kann die äußere Summe außerdem auf mehrere Worker verteilt werden.
Es gibt nur \(O(\log N)\) dyadische Blöcke, da \(p=2^k-1\). Jeder Block benötigt lediglich eine konstante Anzahl modularer Polynomsummen und eine Auswertung von \(S(m+1)\); die Rekursion für \(S\) hat Tiefe \(O(\log N)\). Insgesamt ergibt das
$$O((\log N)^2),$$
während der Speicherverbrauch \(O(\log N)\) für die vorab gespeicherten Zweierpotenzen beträgt. Das ist exponentiell kleiner als jede direkte Untersuchung aller Tripel unterhalb von \(N\).
Üç farklı yığın büyüklüğü \(a\lt b\lt c\) düşünülür. Yasal bir hamle, tam olarak bir yığını daha küçük bir negatif olmayan değere indirir; ardından üç değer yeniden sıralanır ve yine birbirinden farklı kalmalıdır. \(\mathcal{P}\) ile bu oyunun kaybeden durumlar kümesini gösterelim.
\(\mathcal{P}_N=\{(a,b,c)\in\mathcal{P}: 0\lt a\lt b\lt c\lt N\}\) tanımını yapalım.
Hesaplanmak istenen büyüklük
$$F(N)=\sum_{(a,b,c)\in\mathcal{P}_N}(a+b+c)\pmod{10^9}.$$
\(N\)'den küçük tüm üçlüleri doğrudan taramak ancak çok küçük sınırlar için mümkündür. Uygulama bunu yapmak yerine, kaybeden durumların yapısal bir parametrelemesini kullanır ve her bloğun katkısını kapalı formda toplar.
Uygulamanın dayandığı temel oyun kuramı gerçeği şudur: Her kaybeden durum,
$$p=2^k-1,\qquad k\ge 1,$$
şeklindeki tek bir ikili bloğa aittir ve bu blok içinde kaybeden üçlüler
$$c=p+n,\qquad b=p+t,\qquad a=(n\oplus t)-1,$$
biçiminde yazılır; burada
$$1\le n\le p,\qquad 0\le t\lt n.$$
Buradaki \(\oplus\), bit düzeyinde XOR işlemidir. \(c=p+n\) her zaman \(p+1\le c\le 2p\) aralığında olduğundan, en büyük yığın bloğu tek başına belirler ve farklı \(k\) değerleri çakışmaz.
\(F(N)\)'ye katkı verebilmesi için en büyük yığın \(c\lt N\) olmalıdır. \(c=p+n\) olduğundan
$$p+n\lt N\iff n\le N-1-p.$$
Bu yüzden geçerli aralık
$$1\le n\le m,\qquad m=\min\{p,\ N-1-p\}$$
olur. Her böyle \(n\) için \(t\), \(0,1,\dots,n-1\) değerlerini alır; bu da otomatik olarak \(b\lt c\) koşulunu sağlar.
Sabit bir \(p\) bloğunda ve sabit bir \(n\) için
$$a+b+c=(n\oplus t)-1+(p+t)+(p+n).$$
XOR satır toplamını
$$X(n)=\sum_{t=0}^{n-1}(n\oplus t)$$
şeklinde tanımlayalım. O zaman
$$\sum_{t=0}^{n-1}(a+b+c)=X(n)+\sum_{t=0}^{n-1}t+n^2+n(2p-1).$$
\(\sum_{t=0}^{n-1}t=\frac{n(n-1)}{2}\) olduğundan, düzeltme yapılmadan önce bloğun toplamı
$$\sum_{n=1}^{m}\left(X(n)+\frac{n(n-1)}{2}+n^2+(2p-1)n\right)$$
olur. Böylece problem dört standart toplamın hesaplanmasına iner:
$$\sum_{n=1}^{m}X(n),\qquad \sum_{n=1}^{m}n,\qquad \sum_{n=1}^{m}n^2,\qquad \sum_{n=1}^{m}\frac{n(n-1)}{2}.$$
Bilinen toplamlar şunlardır:
$$\sum_{n=1}^{m}n=\frac{m(m+1)}{2},$$
$$\sum_{n=1}^{m}n^2=\frac{m(m+1)(2m+1)}{6},$$
$$\sum_{n=1}^{m}\frac{n(n-1)}{2}=\frac{m(m+1)(m-1)}{6}.$$
Uygulama bu ifadeleri modulo \(10^9\) altında doğru biçimde hesaplamak için, önce \(2\) ve \(3\) ile tam bölmeleri yapar, sonra modüler çarpma uygular.
\(X(0)=0\) olsun ve
$$S(n)=\sum_{i=0}^{n-1}X(i)$$
tanımını yapalım. Böylece ihtiyaç duyulan XOR katkısı \(\sum_{n=1}^{m}X(n)=S(m+1)\) olur.
Şimdi
$$n=2^m+r,\qquad 0\le r\lt 2^m$$
yazalım ve \(p=2^m\) alalım. \(0\le r\lt p\) için
$$X(p+r)=\sum_{t=0}^{p-1}((p+r)\oplus t)+\sum_{u=0}^{r-1}((p+r)\oplus(p+u)).$$
İlk toplamda en yüksek bit korunur; dolayısıyla \((p+r)\oplus t=p+(r\oplus t)\). \(t\), \(0,\dots,p-1\) aralığında gezerken \(r\oplus t\) de aynı aralığın bir permütasyonu olur. Bu yüzden
$$\sum_{t=0}^{p-1}((p+r)\oplus t)=p^2+\sum_{v=0}^{p-1}v=p^2+\frac{p(p-1)}{2}=\frac{p(3p-1)}{2}.$$
İkinci toplamda ise en yüksek bit yok olur ve \((p+r)\oplus(p+u)=r\oplus u\) elde edilir. Demek ki
$$X(p+r)=C_m+X(r),\qquad C_m=\frac{2^m(3\cdot 2^m-1)}{2}.$$
Bunu \(r\) üzerinde toplayınca temel özyineleme gelir:
$$\boxed{S(2^m+r)=S(2^m)+r\,C_m+S(r).}$$
Özellikle iki kuvvet için
$$S(2^{m+1})=2S(2^m)+2^mC_m$$
olur. Uygulama \(S(2^m)\) ve \(C_m\) değerlerini bir kez önceden hesaplar; böylece herhangi bir \(S(n)\) değeri \(O(\log n)\) derinlikte bulunur.
Bu parametreleme, en küçük yığının \(a=0\) olduğu durumları da üretir. Bunlar oyun grafiğinin doğal parçasıdır, fakat \(F(N)\) yalnızca \(0\lt a\lt b\lt c\) koşulunu sağlayan üçlüleri topladığı için sonuçtan çıkarılmalıdır.
\(a=0\) olması tam olarak
$$n\oplus t=1$$
anlamına gelir; dolayısıyla aday \(t=n\oplus 1\)'dir. Bu değer ancak \(n\) tek ise \(0\le t\lt n\) aralığına düşer ve o durumda \(t=n-1\) olur. Yani her tek \(n\) için tam bir geçersiz üçlü vardır.
Tek \(n\) için dışlanacak toplam
$$0+(p+n-1)+(p+n)=2p+2n-1$$
şeklindedir. Eğer
$$q=\left\lfloor\frac{m+1}{2}\right\rfloor$$
ise, \([1,m]\) aralığındaki tek sayılar \(1,3,\dots,2q-1\) olur ve
$$\sum_{\substack{1\le n\le m\\ n\text{ tek}}}1=q,\qquad \sum_{\substack{1\le n\le m\\ n\text{ tek}}}n=q^2.$$
Dolayısıyla blok düzeltmesi
$$\boxed{(2p-1)q+2q^2}$$
olur.
Tüm parçalar birleştirilince \(p=2^k-1\) bloğunun katkısı
$$\begin{aligned} B(p,m)=&\ S(m+1)+\frac{m(m+1)(m-1)}{6}+\frac{m(m+1)(2m+1)}{6}\\ &+(2p-1)\frac{m(m+1)}{2}-\left((2p-1)q+2q^2\right), \end{aligned}$$
burada
$$m=\min\{p,\ N-1-p\},\qquad q=\left\lfloor\frac{m+1}{2}\right\rfloor$$
olmak üzere elde edilir. Sonuç olarak
$$\boxed{F(N)=\sum_{\substack{k\ge 1\\ 2^k\lt N}} B(2^k-1,\ \min\{2^k-1,\ N-2^k\})\pmod{10^9}.}$$
Kaybeden durumların yapısal karakterizasyonu verildikten sonra geriye sadece aritmetik hesap kalır.
\(N=8\) için yalnızca \(p=1\) ve \(p=3\) blokları mümkündür.
\(p=1\) için \(m=1\) olur. Tek parametrelenmiş üçlü \((0,1,2)\) olduğundan, \(a=0\) düzeltmesi sonrası bu blok \(0\) katkı verir.
\(p=3\) için \(m=3\). Önce
$$X(1)=1,\qquad X(2)=2+3=5,\qquad X(3)=3+2+1=6,$$
dolayısıyla
$$\sum_{n=1}^{3}X(n)=12,\qquad \sum_{n=1}^{3}n=6,\qquad \sum_{n=1}^{3}n^2=14,\qquad \sum_{n=1}^{3}\frac{n(n-1)}{2}=4.$$
Ham blok toplamı
$$12+14+4+(2\cdot 3-1)\cdot 6=60$$
çıkar. Ayrıca \(q=\left\lfloor\frac{3+1}{2}\right\rfloor=2\) olduğu için düzeltme
$$(2\cdot 3-1)\cdot 2+2\cdot 2^2=18$$
olur. Böylece
$$F(8)=60-18=42,$$
ki bu, uygulamanın kullandığı kontrol değeriyle aynıdır. İkinci bir kontrol noktası da \(F(128)=496062\)'dir.
C++, Python ve Java uygulamaları aynı planı izler. \(p=2^k-1\) ve \(p+1\lt N\) koşulunu sağlayan tüm bloklar üretilir, her biri için \(m=\min\{p,N-1-p\}\) hesaplanır ve kapalı formdaki blok katkısı modulo \(10^9\) olarak toplanır.
Tek zor alt adım \(S(n)\) hesabıdır. Bu hesap yukarıdaki özyinelemeyi ve iki kuvvet noktalarındaki önhesapları kullandığı için, hiçbir blokta tüm \(t\) ya da tüm \(n\) değerleri tek tek dolaşılmaz. Bloklar birbirinden bağımsız olduğundan, dış toplam uygun olduğunda iş parçacıklarına veya süreçlere de bölünebilir.
\(p=2^k-1\) olduğundan blok sayısı \(O(\log N)\)'dir. Her blok yalnızca sabit sayıda modüler polinom toplamı ve bir adet \(S(m+1)\) hesabı gerektirir; \(S\) özyinelemesinin derinliği de \(O(\log N)\) olur. Böylece toplam çalışma süresi
$$O((\log N)^2)$$
seviyesindedir. Bellek kullanımı ise iki kuvvet tabloları için \(O(\log N)\)'dir. Bu, \(N\)'den küçük tüm üçlüleri doğrudan incelemeye göre astronomik biçimde daha küçüktür.
Consideramos tres montones distintos \(a\lt b\lt c\). Un movimiento legal reduce exactamente uno de ellos a un valor no negativo más pequeño; después se reordena la terna y los tres tamaños deben seguir siendo distintos. Denotemos por \(\mathcal{P}\) el conjunto de posiciones perdedoras del juego.
Definimos \(\mathcal{P}_N=\{(a,b,c)\in\mathcal{P}: 0\lt a\lt b\lt c\lt N\}\).
La cantidad pedida es
$$F(N)=\sum_{(a,b,c)\in\mathcal{P}_N}(a+b+c)\pmod{10^9}.$$
Explorar directamente todas las ternas menores que \(N\) solo sirve para valores muy pequeños. La implementación evita ese espacio cúbico usando una parametrización estructural de todas las posiciones perdedoras y luego suma cada bloque mediante fórmulas cerradas.
El hecho específico del juego que usa la implementación es que toda posición perdedora pertenece a un único bloque diádico dado por
$$p=2^k-1,\qquad k\ge 1,$$
y dentro de ese bloque las ternas perdedoras son exactamente
$$c=p+n,\qquad b=p+t,\qquad a=(n\oplus t)-1,$$
con
$$1\le n\le p,\qquad 0\le t\lt n.$$
Aquí \(\oplus\) representa XOR bit a bit. Como \(c=p+n\) siempre cae en el intervalo \(p+1\le c\le 2p\), el mayor montón determina el bloque de manera única y no hay solapamiento entre distintos valores de \(k\).
Para contribuir a \(F(N)\), el montón mayor debe cumplir \(c\lt N\). Como \(c=p+n\), obtenemos
$$p+n\lt N\iff n\le N-1-p.$$
Por tanto, el rango útil de \(n\) es
$$1\le n\le m,\qquad m=\min\{p,\ N-1-p\}.$$
Para cada uno de esos \(n\), el parámetro \(t\) recorre \(0,1,\dots,n-1\), lo que asegura automáticamente \(b\lt c\).
Fijado \(p\), y para un \(n\) fijo, al sumar todos los \(t\) permitidos aparece
$$a+b+c=(n\oplus t)-1+(p+t)+(p+n).$$
Definimos la suma XOR de fila
$$X(n)=\sum_{t=0}^{n-1}(n\oplus t).$$
Entonces
$$\sum_{t=0}^{n-1}(a+b+c)=X(n)+\sum_{t=0}^{n-1}t+n^2+n(2p-1).$$
Como \(\sum_{t=0}^{n-1}t=\frac{n(n-1)}{2}\), la contribución bruta del bloque es
$$\sum_{n=1}^{m}\left(X(n)+\frac{n(n-1)}{2}+n^2+(2p-1)n\right).$$
Así, todo se reduce a cuatro sumas estándar:
$$\sum_{n=1}^{m}X(n),\qquad \sum_{n=1}^{m}n,\qquad \sum_{n=1}^{m}n^2,\qquad \sum_{n=1}^{m}\frac{n(n-1)}{2}.$$
Las sumas ordinarias son
$$\sum_{n=1}^{m}n=\frac{m(m+1)}{2},$$
$$\sum_{n=1}^{m}n^2=\frac{m(m+1)(2m+1)}{6},$$
$$\sum_{n=1}^{m}\frac{n(n-1)}{2}=\frac{m(m+1)(m-1)}{6}.$$
La implementación las evalúa de forma exacta dividiendo por \(2\) y \(3\) antes de reducir módulo \(10^9\), de modo que no aparece ningún problema con fracciones.
Tomamos \(X(0)=0\) y definimos
$$S(n)=\sum_{i=0}^{n-1}X(i).$$
Entonces la contribución XOR que necesitamos es \(\sum_{n=1}^{m}X(n)=S(m+1)\).
Escribamos
$$n=2^m+r,\qquad 0\le r\lt 2^m,$$
y sea \(p=2^m\). Para \(0\le r\lt p\), separamos
$$X(p+r)=\sum_{t=0}^{p-1}((p+r)\oplus t)+\sum_{u=0}^{r-1}((p+r)\oplus(p+u)).$$
En la primera suma el bit más alto permanece activo, así que \((p+r)\oplus t=p+(r\oplus t)\). Cuando \(t\) recorre \(0,\dots,p-1\), los valores \(r\oplus t\) forman simplemente una permutación de \(0,\dots,p-1\). Por tanto
$$\sum_{t=0}^{p-1}((p+r)\oplus t)=p^2+\sum_{v=0}^{p-1}v=p^2+\frac{p(p-1)}{2}=\frac{p(3p-1)}{2}.$$
En la segunda suma el bit alto se cancela, y queda \((p+r)\oplus(p+u)=r\oplus u\). Así obtenemos
$$X(p+r)=C_m+X(r),\qquad C_m=\frac{2^m(3\cdot 2^m-1)}{2}.$$
Al sumar sobre \(r\), aparece la recurrencia clave
$$\boxed{S(2^m+r)=S(2^m)+r\,C_m+S(r).}$$
Para potencias de dos, esto implica
$$S(2^{m+1})=2S(2^m)+2^mC_m,$$
de modo que la implementación precalcula \(S(2^m)\) y \(C_m\), y luego evalúa cualquier \(S(n)\) en \(O(\log n)\) pasos recursivos.
La parametrización anterior también genera estados cuyo montón más pequeño es \(a=0\). Esos estados forman parte natural del grafo del juego, pero no pertenecen a \(F(N)\), porque en la suma final exigimos \(0\lt a\lt b\lt c\).
Se tiene \(a=0\) exactamente cuando
$$n\oplus t=1,$$
de modo que el candidato es \(t=n\oplus 1\). Este valor cae en el intervalo permitido \(0\le t\lt n\) si y solo si \(n\) es impar; en ese caso \(t=n-1\). Por lo tanto, cada \(n\) impar aporta exactamente una terna inválida.
Para \(n\) impar, la suma excluida es
$$0+(p+n-1)+(p+n)=2p+2n-1.$$
Si
$$q=\left\lfloor\frac{m+1}{2}\right\rfloor,$$
entonces los impares de \([1,m]\) son \(1,3,\dots,2q-1\), y se cumple
$$\sum_{\substack{1\le n\le m\\ 2\nmid n}}1=q,\qquad \sum_{\substack{1\le n\le m\\ 2\nmid n}}n=q^2.$$
Así, la corrección total del bloque es
$$\boxed{(2p-1)q+2q^2.}$$
Al juntar la suma bruta con la corrección para los \(n\) impares, la contribución del bloque \(p=2^k-1\) vale
$$\begin{aligned} B(p,m)=&\ S(m+1)+\frac{m(m+1)(m-1)}{6}+\frac{m(m+1)(2m+1)}{6}\\ &+(2p-1)\frac{m(m+1)}{2}-\left((2p-1)q+2q^2\right), \end{aligned}$$
donde
$$m=\min\{p,\ N-1-p\},\qquad q=\left\lfloor\frac{m+1}{2}\right\rfloor.$$
Por consiguiente,
$$\boxed{F(N)=\sum_{\substack{k\ge 1\\ 2^k\lt N}} B(2^k-1,\ \min\{2^k-1,\ N-2^k\})\pmod{10^9}.}$$
Una vez aceptada la descripción estructural de las posiciones perdedoras, el resto del trabajo es puramente aritmético.
Para \(N=8\), solo aparecen los bloques \(p=1\) y \(p=3\).
En el bloque \(p=1\), tenemos \(m=1\). La única terna parametrizada es \((0,1,2)\), así que tras la corrección por \(a=0\) la contribución de ese bloque es \(0\).
En el bloque \(p=3\), \(m=3\). Primero calculamos
$$X(1)=1,\qquad X(2)=2+3=5,\qquad X(3)=3+2+1=6,$$
y por tanto
$$\sum_{n=1}^{3}X(n)=12,\qquad \sum_{n=1}^{3}n=6,\qquad \sum_{n=1}^{3}n^2=14,\qquad \sum_{n=1}^{3}\frac{n(n-1)}{2}=4.$$
La suma bruta del bloque es
$$12+14+4+(2\cdot 3-1)\cdot 6=60.$$
Ahora \(q=\left\lfloor\frac{3+1}{2}\right\rfloor=2\), de modo que la corrección vale
$$(2\cdot 3-1)\cdot 2+2\cdot 2^2=18.$$
Entonces
$$F(8)=60-18=42,$$
que coincide con el valor de control usado por la implementación. Otro punto de verificación es \(F(128)=496062\).
Las implementaciones en C++, Python y Java siguen exactamente el mismo esquema. Enumeran todos los bloques \(p=2^k-1\) con \(p+1\lt N\), calculan \(m=\min\{p,N-1-p\}\) y suman la fórmula cerrada del bloque módulo \(10^9\).
La única pieza delicada es la evaluación de \(S(n)\). Gracias a la recurrencia anterior y a los valores precalculados en potencias de dos, ningún bloque necesita iterar por todos los \(t\) ni por todos los \(n\). Además, como los bloques son independientes, la suma exterior se puede repartir entre varios hilos o procesos.
Hay \(O(\log N)\) bloques diádicos porque \(p=2^k-1\). Cada bloque requiere un número constante de sumas polinomiales modulares y una evaluación de \(S(m+1)\); la recurrencia de \(S\) tiene profundidad \(O(\log N)\). En consecuencia, el tiempo total es
$$O((\log N)^2),$$
mientras que la memoria es \(O(\log N)\) para las tablas precalculadas en potencias de dos. Esto es muchísimo menor que explorar explícitamente todas las ternas inferiores a \(N\).
我们考虑三个互不相同的堆大小 \(a\lt b\lt c\)。一次合法操作会把其中恰好一个堆减少到更小的非负值，然后重新排序，并且三个数仍然必须互不相同。记 \(\mathcal{P}\) 为这个游戏的必败态集合。
记 \(\mathcal{P}_N=\{(a,b,c)\in\mathcal{P}: 0\lt a\lt b\lt c\lt N\}\)。
要求计算
$$F(N)=\sum_{(a,b,c)\in\mathcal{P}_N}(a+b+c)\pmod{10^9}.$$
如果直接枚举所有小于 \(N\) 的三元组，状态空间是立方级的，只能处理很小的 \(N\)。实现采用了必败态的结构化参数表示，把每个块的贡献化成闭式求和。
实现所依赖的核心结构事实是：每个必败态都属于唯一的一个二进制块
$$p=2^k-1,\qquad k\ge 1,$$
并且在该块内，所有必败三元组都可以写成
$$c=p+n,\qquad b=p+t,\qquad a=(n\oplus t)-1,$$
其中
$$1\le n\le p,\qquad 0\le t\lt n.$$
这里的 \(\oplus\) 表示按位 XOR。由于 \(c=p+n\) 总落在区间 \(p+1\le c\le 2p\) 内，所以最大堆会唯一确定所属块，不同的 \(k\) 不会重叠。
要让一个位置计入 \(F(N)\)，必须有 \(c\lt N\)。由 \(c=p+n\) 可得
$$p+n\lt N\iff n\le N-1-p.$$
因此真正需要的范围是
$$1\le n\le m,\qquad m=\min\{p,\ N-1-p\}.$$
对每个这样的 \(n\)，参数 \(t\) 取遍 \(0,1,\dots,n-1\)，这会自动保证 \(b\lt c\)。
固定 \(p\) 后，对某个固定的 \(n\)，有
$$a+b+c=(n\oplus t)-1+(p+t)+(p+n).$$
定义 XOR 行和
$$X(n)=\sum_{t=0}^{n-1}(n\oplus t).$$
那么
$$\sum_{t=0}^{n-1}(a+b+c)=X(n)+\sum_{t=0}^{n-1}t+n^2+n(2p-1).$$
又因为 \(\sum_{t=0}^{n-1}t=\frac{n(n-1)}{2}\)，所以块的原始贡献为
$$\sum_{n=1}^{m}\left(X(n)+\frac{n(n-1)}{2}+n^2+(2p-1)n\right).$$
因此问题被压缩成四个基本求和：
$$\sum_{n=1}^{m}X(n),\qquad \sum_{n=1}^{m}n,\qquad \sum_{n=1}^{m}n^2,\qquad \sum_{n=1}^{m}\frac{n(n-1)}{2}.$$
普通算术和分别是
$$\sum_{n=1}^{m}n=\frac{m(m+1)}{2},$$
$$\sum_{n=1}^{m}n^2=\frac{m(m+1)(2m+1)}{6},$$
$$\sum_{n=1}^{m}\frac{n(n-1)}{2}=\frac{m(m+1)(m-1)}{6}.$$
实现会先做对 \(2\) 和 \(3\) 的整除，再做模 \(10^9\) 下的乘法，因此整个计算始终保持精确。
令 \(X(0)=0\)，并定义
$$S(n)=\sum_{i=0}^{n-1}X(i).$$
于是所需的 XOR 贡献就是 \(\sum_{n=1}^{m}X(n)=S(m+1)\)。
把 \(n\) 写成
$$n=2^m+r,\qquad 0\le r\lt 2^m,$$
并记 \(p=2^m\)。对 \(0\le r\lt p\)，将 \(X(p+r)\) 分成两段：
$$X(p+r)=\sum_{t=0}^{p-1}((p+r)\oplus t)+\sum_{u=0}^{r-1}((p+r)\oplus(p+u)).$$
在第一段中，最高位始终保留，所以 \((p+r)\oplus t=p+(r\oplus t)\)。当 \(t\) 取遍 \(0,\dots,p-1\) 时，\(r\oplus t\) 只是 \(0,\dots,p-1\) 的一个排列，因此
$$\sum_{t=0}^{p-1}((p+r)\oplus t)=p^2+\sum_{v=0}^{p-1}v=p^2+\frac{p(p-1)}{2}=\frac{p(3p-1)}{2}.$$
在第二段中，最高位抵消，所以 \((p+r)\oplus(p+u)=r\oplus u\)。于是得到
$$X(p+r)=C_m+X(r),\qquad C_m=\frac{2^m(3\cdot 2^m-1)}{2}.$$
对 \(r\) 求和就得到关键递推：
$$\boxed{S(2^m+r)=S(2^m)+r\,C_m+S(r).}$$
特别地，对二次幂有
$$S(2^{m+1})=2S(2^m)+2^mC_m,$$
因此实现会先预处理所有 \(S(2^m)\) 和 \(C_m\)，随后就能在 \(O(\log n)\) 的递归深度内求出任意 \(S(n)\)。
上面的参数化还会生成最小堆为 \(a=0\) 的状态。这些状态在游戏图中是自然存在的，但它们不应计入 \(F(N)\)，因为最终求和只覆盖 \(0\lt a\lt b\lt c\)。
条件 \(a=0\) 等价于
$$n\oplus t=1,$$
所以候选值是 \(t=n\oplus 1\)。只有当 \(n\) 为奇数时，这个值才落在合法范围 \(0\le t\lt n\) 内，此时恰有 \(t=n-1\)。因此每个奇数 \(n\) 都对应一个需要删除的无效三元组。
对奇数 \(n\)，被排除的和为
$$0+(p+n-1)+(p+n)=2p+2n-1.$$
若记
$$q=\left\lfloor\frac{m+1}{2}\right\rfloor,$$
那么区间 \([1,m]\) 内的奇数就是 \(1,3,\dots,2q-1\)，从而
$$\sum_{\substack{1\le n\le m\\ 2\nmid n}}1=q,\qquad \sum_{\substack{1\le n\le m\\ 2\nmid n}}n=q^2.$$
所以单个块的修正项为
$$\boxed{(2p-1)q+2q^2.}$$
把原始求和与奇数修正合并，块 \(p=2^k-1\) 的贡献为
$$\begin{aligned} B(p,m)=&\ S(m+1)+\frac{m(m+1)(m-1)}{6}+\frac{m(m+1)(2m+1)}{6}\\ &+(2p-1)\frac{m(m+1)}{2}-\left((2p-1)q+2q^2\right), \end{aligned}$$
其中
$$m=\min\{p,\ N-1-p\},\qquad q=\left\lfloor\frac{m+1}{2}\right\rfloor.$$
因此整体答案就是
$$\boxed{F(N)=\sum_{\substack{k\ge 1\\ 2^k\lt N}} B(2^k-1,\ \min\{2^k-1,\ N-2^k\})\pmod{10^9}.}$$
也就是说，一旦接受必败态的块结构，剩下的部分完全是算术化简。
当 \(N=8\) 时，只会出现 \(p=1\) 和 \(p=3\) 两个块。
对 \(p=1\)，有 \(m=1\)。唯一被参数化出的三元组是 \((0,1,2)\)，因此经 \(a=0\) 修正后该块贡献为 \(0\)。
对 \(p=3\)，有 \(m=3\)。先算
$$X(1)=1,\qquad X(2)=2+3=5,\qquad X(3)=3+2+1=6,$$
所以
$$\sum_{n=1}^{3}X(n)=12,\qquad \sum_{n=1}^{3}n=6,\qquad \sum_{n=1}^{3}n^2=14,\qquad \sum_{n=1}^{3}\frac{n(n-1)}{2}=4.$$
原始块和为
$$12+14+4+(2\cdot 3-1)\cdot 6=60.$$
又因为 \(q=\left\lfloor\frac{3+1}{2}\right\rfloor=2\)，修正项是
$$(2\cdot 3-1)\cdot 2+2\cdot 2^2=18.$$
于是
$$F(8)=60-18=42,$$
与实现使用的校验值一致。另一个校验点是 \(F(128)=496062\)。
C++、Python 和 Java 三个实现遵循完全相同的结构。它们枚举所有满足 \(p=2^k-1\) 且 \(p+1\lt N\) 的块，计算截断参数 \(m=\min\{p,N-1-p\}\)，然后把块公式按模 \(10^9\) 累加起来。
唯一真正复杂的部分是 \(S(n)\) 的求值。由于使用了上面的递推和二次幂处的预处理值，任何块都不需要遍历所有 \(t\) 或所有 \(n\)。同时，各个块互相独立，所以外层求和也可以分配到多个线程或进程上。
因为 \(p=2^k-1\)，所以块数只有 \(O(\log N)\)。每个块只需要常数个模多项式求和，再加一次 \(S(m+1)\) 的计算，而 \(S\) 的递归深度是 \(O(\log N)\)。于是总时间复杂度为
$$O((\log N)^2),$$
额外空间复杂度为 \(O(\log N)\)，对应于二次幂预处理表。与直接枚举所有小于 \(N\) 的三元组相比，这个量级要小得多。
Рассматриваются три различных размера куч \(a\lt b\lt c\). Допустимый ход уменьшает ровно одну кучу до меньшего неотрицательного значения; затем тройка переупорядочивается, и все три значения должны оставаться различными. Обозначим через \(\mathcal{P}\) множество проигрышных позиций игры.
Обозначим \(\mathcal{P}_N=\{(a,b,c)\in\mathcal{P}: 0\lt a\lt b\lt c\lt N\}\).
Нужно вычислить
$$F(N)=\sum_{(a,b,c)\in\mathcal{P}_N}(a+b+c)\pmod{10^9}.$$
Полный перебор всех троек меньше \(N\) возможен только для очень маленьких значений. Реализация уходит от этого кубического пространства состояний, используя структурную параметризацию всех проигрышных позиций и затем суммируя каждый блок в замкнутом виде.
Ключевой факт о самой игре, на котором основана реализация, состоит в том, что каждая проигрышная позиция принадлежит ровно одному двоичному блоку
$$p=2^k-1,\qquad k\ge 1,$$
а внутри такого блока проигрышные тройки имеют вид
$$c=p+n,\qquad b=p+t,\qquad a=(n\oplus t)-1,$$
где
$$1\le n\le p,\qquad 0\le t\lt n.$$
Здесь \(\oplus\) означает побитовое XOR. Поскольку \(c=p+n\) всегда лежит в интервале \(p+1\le c\le 2p\), наибольшая куча однозначно определяет блок, и разные значения \(k\) не пересекаются.
Чтобы позиция учитывалась в \(F(N)\), необходимо \(c\lt N\). Из соотношения \(c=p+n\) получаем
$$p+n\lt N\iff n\le N-1-p.$$
Следовательно, рабочий диапазон равен
$$1\le n\le m,\qquad m=\min\{p,\ N-1-p\}.$$
Для каждого такого \(n\) параметр \(t\) пробегает \(0,1,\dots,n-1\), что автоматически гарантирует \(b\lt c\).
Зафиксируем \(p\). Для фиксированного \(n\) имеем
$$a+b+c=(n\oplus t)-1+(p+t)+(p+n).$$
Введем строковую XOR-сумму
$$X(n)=\sum_{t=0}^{n-1}(n\oplus t).$$
Тогда
$$\sum_{t=0}^{n-1}(a+b+c)=X(n)+\sum_{t=0}^{n-1}t+n^2+n(2p-1).$$
Так как \(\sum_{t=0}^{n-1}t=\frac{n(n-1)}{2}\), сырая сумма блока равна
$$\sum_{n=1}^{m}\left(X(n)+\frac{n(n-1)}{2}+n^2+(2p-1)n\right).$$
Итак, задача сводится к четырем стандартным суммам:
$$\sum_{n=1}^{m}X(n),\qquad \sum_{n=1}^{m}n,\qquad \sum_{n=1}^{m}n^2,\qquad \sum_{n=1}^{m}\frac{n(n-1)}{2}.$$
Обычные суммы имеют вид
$$\sum_{n=1}^{m}n=\frac{m(m+1)}{2},$$
$$\sum_{n=1}^{m}n^2=\frac{m(m+1)(2m+1)}{6},$$
$$\sum_{n=1}^{m}\frac{n(n-1)}{2}=\frac{m(m+1)(m-1)}{6}.$$
Реализация вычисляет эти выражения точно: деление на \(2\) и \(3\) выполняется до взятия модуля, а затем применяется умножение по модулю \(10^9\).
Положим \(X(0)=0\) и введем функцию
$$S(n)=\sum_{i=0}^{n-1}X(i).$$
Тогда нужная XOR-часть равна \(\sum_{n=1}^{m}X(n)=S(m+1)\).
Запишем
$$n=2^m+r,\qquad 0\le r\lt 2^m,$$
и обозначим \(p=2^m\). Для \(0\le r\lt p\) разбиваем
$$X(p+r)=\sum_{t=0}^{p-1}((p+r)\oplus t)+\sum_{u=0}^{r-1}((p+r)\oplus(p+u)).$$
В первой сумме старший бит сохраняется, поэтому \((p+r)\oplus t=p+(r\oplus t)\). Когда \(t\) пробегает \(0,\dots,p-1\), значения \(r\oplus t\) просто переставляют числа \(0,\dots,p-1\). Значит,
$$\sum_{t=0}^{p-1}((p+r)\oplus t)=p^2+\sum_{v=0}^{p-1}v=p^2+\frac{p(p-1)}{2}=\frac{p(3p-1)}{2}.$$
Во второй сумме старший бит сокращается, так что \((p+r)\oplus(p+u)=r\oplus u\). Отсюда
$$X(p+r)=C_m+X(r),\qquad C_m=\frac{2^m(3\cdot 2^m-1)}{2}.$$
Суммируя по \(r\), получаем ключевую рекурсию
$$\boxed{S(2^m+r)=S(2^m)+r\,C_m+S(r).}$$
Для степеней двойки это дает
$$S(2^{m+1})=2S(2^m)+2^mC_m,$$
поэтому реализация заранее считает \(S(2^m)\) и \(C_m\), а любое значение \(S(n)\) затем получается за \(O(\log n)\) рекурсивных шагов.
Параметризация порождает также состояния, где минимальная куча равна нулю. Они естественно возникают в графе игры, но в сумму \(F(N)\) не входят, поскольку там учитываются только тройки с \(0\lt a\lt b\lt c\).
Условие \(a=0\) эквивалентно
$$n\oplus t=1,$$
то есть кандидат равен \(t=n\oplus 1\). Он попадает в допустимый диапазон \(0\le t\lt n\) тогда и только тогда, когда \(n\) нечетно; в этом случае \(t=n-1\). Следовательно, каждому нечетному \(n\) соответствует ровно одна недопустимая тройка.
Для нечетного \(n\) исключаемая сумма равна
$$0+(p+n-1)+(p+n)=2p+2n-1.$$
Если
$$q=\left\lfloor\frac{m+1}{2}\right\rfloor,$$
то нечетные числа в \([1,m]\) равны \(1,3,\dots,2q-1\), и потому
$$\sum_{\substack{1\le n\le m\\ 2\nmid n}}1=q,\qquad \sum_{\substack{1\le n\le m\\ 2\nmid n}}n=q^2.$$
Итак, поправка для блока имеет вид
$$\boxed{(2p-1)q+2q^2.}$$
Объединяя сырую сумму и поправку по нечетным \(n\), получаем вклад блока \(p=2^k-1\):
$$\begin{aligned} B(p,m)=&\ S(m+1)+\frac{m(m+1)(m-1)}{6}+\frac{m(m+1)(2m+1)}{6}\\ &+(2p-1)\frac{m(m+1)}{2}-\left((2p-1)q+2q^2\right), \end{aligned}$$
где
$$m=\min\{p,\ N-1-p\},\qquad q=\left\lfloor\frac{m+1}{2}\right\rfloor.$$
Следовательно, весь ответ равен
$$\boxed{F(N)=\sum_{\substack{k\ge 1\\ 2^k\lt N}} B(2^k-1,\ \min\{2^k-1,\ N-2^k\})\pmod{10^9}.}$$
После структурного описания проигрышных позиций дальнейшая часть решения становится чисто арифметической.
При \(N=8\) возможны только блоки \(p=1\) и \(p=3\).
Для \(p=1\) имеем \(m=1\). Единственная параметризованная тройка равна \((0,1,2)\), поэтому после поправки на \(a=0\) вклад блока равен нулю.
Для \(p=3\) имеем \(m=3\). Сначала вычисляем
$$X(1)=1,\qquad X(2)=2+3=5,\qquad X(3)=3+2+1=6,$$
а значит
$$\sum_{n=1}^{3}X(n)=12,\qquad \sum_{n=1}^{3}n=6,\qquad \sum_{n=1}^{3}n^2=14,\qquad \sum_{n=1}^{3}\frac{n(n-1)}{2}=4.$$
Сырая сумма блока равна
$$12+14+4+(2\cdot 3-1)\cdot 6=60.$$
Теперь \(q=\left\lfloor\frac{3+1}{2}\right\rfloor=2\), поэтому поправка равна
$$(2\cdot 3-1)\cdot 2+2\cdot 2^2=18.$$
Итак,
$$F(8)=60-18=42,$$
что совпадает с контрольным значением реализации. Еще один контрольный пункт: \(F(128)=496062\).
Реализации на C++, Python и Java следуют одной и той же схеме. Они перечисляют все блоки \(p=2^k-1\) с условием \(p+1\lt N\), вычисляют усеченный параметр \(m=\min\{p,N-1-p\}\) и прибавляют замкнутую формулу блока по модулю \(10^9\).
Единственная по-настоящему нетривиальная часть - вычисление \(S(n)\). Благодаря приведенной выше рекурсии и предварительно посчитанным значениям на степенях двойки ни в одном блоке не требуется проходить все \(t\) или все \(n\). Внешняя сумма по блокам также независима и потому может распределяться между несколькими потоками или процессами.
Так как \(p=2^k-1\), число двоичных блоков равно \(O(\log N)\). Каждый блок требует лишь постоянного числа модульных полиномиальных сумм и одного вычисления \(S(m+1)\), а глубина рекурсии для \(S\) равна \(O(\log N)\). Следовательно, суммарное время работы составляет
$$O((\log N)^2),$$
а память - \(O(\log N)\) для таблиц, связанных со степенями двойки. Это на порядки меньше, чем прямое исследование всех троек ниже \(N\).
لدينا ثلاث كومات مختلفة الأحجام \(a\lt b\lt c\). الحركة القانونية تُنقص كومة واحدة فقط إلى قيمة غير سالبة أصغر، ثم تُرتَّب القيم من جديد ويجب أن تبقى الأحجام الثلاثة مختلفة. نرمز بـ \(\mathcal{P}\) إلى مجموعة الحالات الخاسرة في هذه اللعبة.
لنعرّف \(\mathcal{P}_N=\{(a,b,c)\in\mathcal{P}: 0\lt a\lt b\lt c\lt N\}\).
الكمية المطلوبة هي
$$F(N)=\sum_{(a,b,c)\in\mathcal{P}_N}(a+b+c)\pmod{10^9}.$$
الفحص المباشر لكل الثلاثيات الأصغر من \(N\) لا يصلح إلا لحدود صغيرة جدًا. لذلك تعتمد الخوارزمية على وصف بنيوي لجميع الحالات الخاسرة، ثم تجمع مساهمة كل كتلة بصيغة مغلقة.
الحقيقة الأساسية الخاصة باللعبة التي يستخدمها التنفيذ هي أن كل حالة خاسرة تنتمي إلى كتلة ثنائية وحيدة من الشكل
$$p=2^k-1,\qquad k\ge 1,$$
وداخل هذه الكتلة تكون الثلاثيات الخاسرة بالضبط على الصورة
$$c=p+n,\qquad b=p+t,\qquad a=(n\oplus t)-1,$$
حيث
$$1\le n\le p,\qquad 0\le t\lt n.$$
والرمز \(\oplus\) هو XOR على مستوى البتات. وبما أن \(c=p+n\) يقع دائمًا في المجال \(p+1\le c\le 2p\)، فإن الكومة الأكبر تحدد الكتلة بشكل وحيد، ولا يوجد تداخل بين قيم \(k\) المختلفة.
حتى تدخل الحالة في \(F(N)\) يجب أن تحقق \(c\lt N\). ومن العلاقة \(c=p+n\) نحصل على
$$p+n\lt N\iff n\le N-1-p.$$
إذن المجال الفعلي هو
$$1\le n\le m,\qquad m=\min\{p,\ N-1-p\}.$$
ولكل قيمة من هذه القيم، يأخذ \(t\) القيم \(0,1,\dots,n-1\)، وهذا يضمن تلقائيًا الشرط \(b\lt c\).
بعد تثبيت \(p\)، ولـ \(n\) ثابت، نجد أن
$$a+b+c=(n\oplus t)-1+(p+t)+(p+n).$$
لنعرّف مجموع XOR الصفّي
$$X(n)=\sum_{t=0}^{n-1}(n\oplus t).$$
إذن
$$\sum_{t=0}^{n-1}(a+b+c)=X(n)+\sum_{t=0}^{n-1}t+n^2+n(2p-1).$$
وبما أن \(\sum_{t=0}^{n-1}t=\frac{n(n-1)}{2}\)، فإن المساهمة الخام للكتلة هي
$$\sum_{n=1}^{m}\left(X(n)+\frac{n(n-1)}{2}+n^2+(2p-1)n\right).$$
وهكذا تنخفض المسألة إلى أربعة مجاميع قياسية:
$$\sum_{n=1}^{m}X(n),\qquad \sum_{n=1}^{m}n,\qquad \sum_{n=1}^{m}n^2,\qquad \sum_{n=1}^{m}\frac{n(n-1)}{2}.$$
المجاميع العادية هي
$$\sum_{n=1}^{m}n=\frac{m(m+1)}{2},$$
$$\sum_{n=1}^{m}n^2=\frac{m(m+1)(2m+1)}{6},$$
$$\sum_{n=1}^{m}\frac{n(n-1)}{2}=\frac{m(m+1)(m-1)}{6}.$$
ويحسب التنفيذ هذه الصيغ بدقة تامة، إذ يقسم على \(2\) و\(3\) قبل الضرب المعياري، وبذلك تبقى الصيغة صحيحة تحت الترديد \(10^9\).
نضع \(X(0)=0\) ونعرّف
$$S(n)=\sum_{i=0}^{n-1}X(i).$$
وعندئذٍ تصبح مساهمة XOR المطلوبة مساوية لـ \(\sum_{n=1}^{m}X(n)=S(m+1)\).
اكتب
$$n=2^m+r,\qquad 0\le r\lt 2^m,$$
ولنرمز إلى \(p=2^m\). عندما \(0\le r\lt p\)، نقسم \(X(p+r)\) إلى جزأين:
$$X(p+r)=\sum_{t=0}^{p-1}((p+r)\oplus t)+\sum_{u=0}^{r-1}((p+r)\oplus(p+u)).$$
في المجموع الأول تبقى البتة العليا موجودة، ومن ثم \((p+r)\oplus t=p+(r\oplus t)\). وعندما يمر \(t\) على \(0,\dots,p-1\)، فإن \(r\oplus t\) لا يفعل أكثر من إعادة ترتيب الأعداد \(0,\dots,p-1\). لذا
$$\sum_{t=0}^{p-1}((p+r)\oplus t)=p^2+\sum_{v=0}^{p-1}v=p^2+\frac{p(p-1)}{2}=\frac{p(3p-1)}{2}.$$
أما في المجموع الثاني فإن البتة العليا تُلغى، فينتج \((p+r)\oplus(p+u)=r\oplus u\). وبالتالي
$$X(p+r)=C_m+X(r),\qquad C_m=\frac{2^m(3\cdot 2^m-1)}{2}.$$
وبجمع هذه العلاقة على \(r\) نحصل على التكرار الأساسي
$$\boxed{S(2^m+r)=S(2^m)+r\,C_m+S(r).}$$
وبوجه خاص، لقوى العدد \(2\) نحصل على
$$S(2^{m+1})=2S(2^m)+2^mC_m,$$
ومن ثم يسبق التنفيذ حساب \(S(2^m)\) و\(C_m\)، وبعد ذلك يمكن إيجاد أي \(S(n)\) في \(O(\log n)\) خطوة تراجعية.
هذا التمثيل البنيوي يولد أيضًا حالات تكون فيها أصغر كومة مساوية للصفر. هذه الحالات مفيدة داخل بنية اللعبة، لكنها لا تدخل في \(F(N)\) لأن المجموع النهائي يشترط \(0\lt a\lt b\lt c\).
يتحقق الشرط \(a=0\) بالضبط عندما
$$n\oplus t=1,$$
ومن ثم يكون المرشح هو \(t=n\oplus 1\). وهذه القيمة تقع داخل المجال القانوني \(0\le t\lt n\) إذا وفقط إذا كان \(n\) فرديًا، وعندها تكون \(t=n-1\). لذلك يسهم كل \(n\) فردي بثلاثية غير صالحة واحدة فقط.
وبالنسبة لـ \(n\) الفردي، فإن المجموع المستبعد يساوي
$$0+(p+n-1)+(p+n)=2p+2n-1.$$
إذا وضعنا
$$q=\left\lfloor\frac{m+1}{2}\right\rfloor,$$
فإن الأعداد الفردية في \([1,m]\) هي \(1,3,\dots,2q-1\)، ولذلك
$$\sum_{\substack{1\le n\le m\\ 2\nmid n}}1=q,\qquad \sum_{\substack{1\le n\le m\\ 2\nmid n}}n=q^2.$$
ومن ثم تكون صيغة التصحيح للكتلة الواحدة هي
$$\boxed{(2p-1)q+2q^2.}$$
عند جمع المساهمة الخام مع تصحيح القيم الفردية، تصبح مساهمة الكتلة \(p=2^k-1\) مساوية لـ
$$\begin{aligned} B(p,m)=&\ S(m+1)+\frac{m(m+1)(m-1)}{6}+\frac{m(m+1)(2m+1)}{6}\\ &+(2p-1)\frac{m(m+1)}{2}-\left((2p-1)q+2q^2\right), \end{aligned}$$
حيث
$$m=\min\{p,\ N-1-p\},\qquad q=\left\lfloor\frac{m+1}{2}\right\rfloor.$$
وبالتالي فإن الجواب الكلي هو
$$\boxed{F(N)=\sum_{\substack{k\ge 1\\ 2^k\lt N}} B(2^k-1,\ \min\{2^k-1,\ N-2^k\})\pmod{10^9}.}$$
أي أن العمل كله بعد الوصف البنيوي للحالات الخاسرة يتحول إلى حسابات عددية صريحة.
عندما \(N=8\)، تكون الكتل الممكنة فقط هي \(p=1\) و\(p=3\).
في الكتلة \(p=1\) لدينا \(m=1\)، والثلاثية الوحيدة التي ينتجها التمثيل هي \((0,1,2)\)، ولذلك تختفي مساهمة هذه الكتلة كلها بعد تصحيح \(a=0\).
أما في الكتلة \(p=3\) فلدينا \(m=3\). نحسب أولًا
$$X(1)=1,\qquad X(2)=2+3=5,\qquad X(3)=3+2+1=6,$$
ومن ثم
$$\sum_{n=1}^{3}X(n)=12,\qquad \sum_{n=1}^{3}n=6,\qquad \sum_{n=1}^{3}n^2=14,\qquad \sum_{n=1}^{3}\frac{n(n-1)}{2}=4.$$
إذن المجموع الخام للكتلة هو
$$12+14+4+(2\cdot 3-1)\cdot 6=60.$$
وبما أن \(q=\left\lfloor\frac{3+1}{2}\right\rfloor=2\)، فإن التصحيح يساوي
$$(2\cdot 3-1)\cdot 2+2\cdot 2^2=18.$$
إذًا
$$F(8)=60-18=42,$$
وهو نفس مقدار التحقق المستخدم في التنفيذ. كما أن نقطة تحقق ثانية هي \(F(128)=496062\).
التنفيذات في C++ وPython وJava تتبع البنية نفسها. فهي تعدد جميع الكتل \(p=2^k-1\) التي تحقق \(p+1\lt N\)، ثم تحسب \(m=\min\{p,N-1-p\}\)، ثم تجمع صيغة الكتلة بترديد \(10^9\).
الجزء الوحيد غير المباشر هو حساب \(S(n)\). وبفضل العلاقة التراجعية السابقة والقيم المحسوبة مسبقًا عند قوى العدد \(2\)، لا تحتاج أي كتلة إلى الدوران على جميع قيم \(t\) أو جميع قيم \(n\). ولأن الكتل مستقلة عن بعضها، يمكن توزيع المجموع الخارجي على عدة خيوط أو عمليات أيضًا.
بما أن \(p=2^k-1\)، فإن عدد الكتل هو \(O(\log N)\). وكل كتلة تحتاج إلى عدد ثابت من المجاميع كثيرة الحدود المعيارية وإلى تقييم واحد لـ \(S(m+1)\)، أما عمق التراجع في \(S\) فهو \(O(\log N)\). لذلك فإن زمن التنفيذ الكلي يساوي
$$O((\log N)^2),$$
بينما يساوي استهلاك الذاكرة \(O(\log N)\) من أجل الجداول المحسوبة مسبقًا عند قوى العدد \(2\). وهذا أصغر بكثير من أي محاولة مباشرة لفحص كل الثلاثيات الأصغر من \(N\).