A position is an integer partition \(\lambda=(s_1,\dots,s_t)\) of \(n\), where each part is a heap size. For a fixed parameter \(k\), one move chooses one heap and replaces it by any partition of that heap into between \(2\) and \(k\) nonempty heaps. Let \(F_k(n)\) denote the number of winning partitions of \(n\) under normal play. The required quantity is
$$g(n)=\sum_{k=2}^{n}F_k(n),$$
evaluated at \(n=200\) modulo \(10^9+7\). The solution does not enumerate all game trees of all partitions directly. Instead, it first determines the single-heap Sprague-Grundy laws and then counts whole partitions by XOR dynamic programming.
For a partition \(\lambda=(s_1,\dots,s_t)\), let \(\operatorname{sg}_k(s)\) be the Sprague-Grundy value of one heap of size \(s\) in the version with parameter \(k\). By the Sprague-Grundy theorem, \(\lambda\) is losing exactly when
$$\operatorname{sg}_k(s_1)\oplus \operatorname{sg}_k(s_2)\oplus \cdots \oplus \operatorname{sg}_k(s_t)=0.$$
So the problem has two layers: determine \(\operatorname{sg}_k(s)\), then count the partitions of \(n\) whose heap nim-sum is zero.
If we write
$$L_k(n)=\#\left\{\lambda\vdash n:\bigoplus_{s\in\lambda}\operatorname{sg}_k(s)=0\right\},$$
then \(L_k(n)\) counts the losing partitions, while the winning partitions are
$$F_k(n)=p(n)-L_k(n),$$
where \(p(n)\) is the ordinary partition number. Therefore \(g(n)\) can be found once we know the heap Grundy values and can count XOR-zero partitions for each relevant \(k\).
When only two-way splits are allowed, a heap of size \(s\) can move to \(a+(s-a)\) with \(1\le a\le s-1\). The implementations use the exact law
$$\operatorname{sg}_2(s)=\begin{cases} 1,&s\equiv 0\pmod{2},\\ 0,&s\equiv 1\pmod{2}, \end{cases}\qquad s\ge1.$$
The induction is short. Assume the rule holds below \(s\). If \(s\) is even, every split has two parts of the same parity, so every option has xor \(0\), hence the mex is \(1\). If \(s\) is odd, every split has one odd and one even part, so every option has xor \(1\), hence the mex is \(0\).
This means that for \(k=2\), a partition is losing exactly when it contains an even number of even parts.
For three-way scattering, a heap of size \(s\) may be split into either two or three positive parts. There is no extra closed form in the implementations; instead they compute the Sprague-Grundy table directly from the mex definition:
$$\operatorname{sg}_3(s)=\operatorname{mex}\Bigl(A_2(s)\cup A_3(s)\Bigr),$$
with
$$A_2(s)=\left\{\operatorname{sg}_3(a)\oplus \operatorname{sg}_3(s-a):1\le a\le s-1\right\},$$
$$A_3(s)=\left\{\operatorname{sg}_3(a)\oplus \operatorname{sg}_3(b)\oplus \operatorname{sg}_3(c):a+b+c=s,\ a,b,c\ge1\right\}.$$
Starting from \(\operatorname{sg}_3(1)=0\), this gives the initial values
$$0,1,2,3,1,4,3,2,4,5,\dots$$
for heap sizes \(1,2,3,4,5,6,7,8,9,10,\dots\). Since the target is only \(n=200\), tabulating these values once is easily fast enough.
Once four-way splits are allowed, the single-heap game settles into the exact linear rule
$$\operatorname{sg}_k(s)=s-1\qquad (k\ge4,\ s\ge1).$$
The reason is that the mex saturates. Every move from a heap of size \(s\) creates \(r\ge2\) positive heaps \(x_1,\dots,x_r\), so under the linear law the option value is
$$\bigoplus_{i=1}^{r}(x_i-1).$$
This xor is always at most the ordinary sum, and therefore
$$\bigoplus_{i=1}^{r}(x_i-1)\le \sum_{i=1}^{r}(x_i-1)=s-r\le s-2,$$
so \(s-1\) is not reachable in one move. The four-way regime is already rich enough to realize every nimber from \(0\) through \(s-2\), which forces the mex to be exactly \(s-1\). Consequently all parameters \(k=4,5,\dots,n\) lead to the same partition-counting problem.
For a fixed \(k\), define a table \(D_k(t,x)\) as the number of partitions of total \(t\) whose heap Grundy xor equals \(x\). The initial condition is
$$D_k(0,0)=1.$$
Now process heap sizes \(s=1,2,\dots,n\) one by one. Because partitions are multisets, the update is the standard unbounded-partition order:
$$D_k(t,\ x\oplus \operatorname{sg}_k(s))\mathrel{+}=D_k(t-s,\ x)\qquad (t\ge s).$$
Iterating totals in increasing order allows the same size \(s\) to appear any number of times. When all heap sizes have been processed, the losing count is
$$L_k(n)=D_k(n,0).$$
The ordinary partition number \(p(n)\) is computed with the same coin-change idea but without the xor dimension, so finally
$$F_k(n)=p(n)-L_k(n)\pmod{10^9+7}.$$
The three regimes above imply that only three distinct counting problems remain:
$$k=2,\qquad k=3,\qquad k\ge4.$$
Therefore
$$g(n)=F_2(n)+F_3(n)+(n-3)F_4(n).$$
This is the decisive simplification: instead of solving \(n-1\) different games, the program solves only three.
The partitions of \(5\) are
$$5,\ 4+1,\ 3+2,\ 3+1+1,\ 2+2+1,\ 2+1+1+1,\ 1+1+1+1+1,$$
so \(p(5)=7\).
For \(k=2\), the heap values are \(0,1,0,1,0\) on sizes \(1\) through \(5\). A partition is losing iff it contains an even number of even parts, so the winning partitions are
$$4+1,\qquad 3+2,\qquad 2+1+1+1,$$
hence \(F_2(5)=3\).
For \(k=3\), the recurrence above gives
$$\operatorname{sg}_3(1),\dots,\operatorname{sg}_3(5)=0,1,2,3,1.$$
The only losing partitions are then
$$2+2+1,\qquad 1+1+1+1+1,$$
so \(F_3(5)=5\).
For every \(k\ge4\), the rule \(\operatorname{sg}_k(s)=s-1\) gives heap values \(0,1,2,3,4\), and the same two partitions remain losing, so \(F_4(5)=5\). Therefore
$$g(5)=F_2(5)+F_3(5)+2F_4(5)=3+5+2\cdot 5=18.$$
This small case matches the checkpoint values used by the implementations.
The C++, Python, and Java implementations follow the same plan. They first compute \(p(n)\) with the standard partition DP. Next they build three single-heap Grundy tables: the parity rule for \(k=2\), the direct mex table for \(k=3\), and the linear table \(s-1\) for the saturated regime \(k\ge4\).
For each of those three tables, the implementation runs a second DP over total sum and xor-state. The xor dimension has width \(256\), which is enough for every Grundy value that appears up to heap size \(200\). The count of losing partitions is the state with total \(n\) and xor \(0\), and subtracting that from \(p(n)\) yields the winning count for the regime.
Finally the program combines the three contributions as
$$F_2(n)+F_3(n)+(n-3)F_4(n)\pmod{10^9+7}.$$
It also checks small control values such as \(F_2(5)=3\), \(F_3(5)=5\), \(g(7)=66\), and \(g(10)=291\) before producing the final value for \(n=200\).
Let \(n\) be the target heap total and let \(X=256\) be the xor-state width. Computing the partition numbers costs \(O(n^2)\) time. Building the \(k=2\) and \(k\ge4\) Grundy tables is linear, while the direct mex recurrence for \(k=3\) costs \(O(n^3)\) time because each heap size scans all two-part and three-part splits. Each XOR-partition DP costs \(O(n^2X)\) time and \(O(nX)\) memory, and this is done for three regimes. Hence the overall complexity is
$$O(n^3+n^2X)\ \text{time},\qquad O(nX)\ \text{memory},$$
which is entirely practical for \(n=200\).
Eine Stellung ist eine Partition \(\lambda=(s_1,\dots,s_t)\) von \(n\), wobei jeder Teil einer Haufengröße entspricht. Für einen festen Parameter \(k\) besteht ein Zug darin, einen Haufen zu wählen und ihn durch eine Partition dieses Haufens in zwischen \(2\) und \(k\) nichtleere Haufen zu ersetzen. Sei \(F_k(n)\) die Anzahl gewinnender Partitionen von \(n\) im normalen Spiel. Gesucht ist
$$g(n)=\sum_{k=2}^{n}F_k(n),$$
ausgewertet bei \(n=200\) modulo \(10^9+7\). Die Lösung enumeriert nicht alle Spielbäume direkt, sondern bestimmt zuerst die Sprague-Grundy-Werte einzelner Haufen und zählt danach ganze Partitionen mit einer XOR-Dynamik.
Für eine Partition \(\lambda=(s_1,\dots,s_t)\) bezeichne \(\operatorname{sg}_k(s)\) den Sprague-Grundy-Wert eines einzelnen Haufens der Größe \(s\) in der Variante mit Parameter \(k\). Nach dem Sprague-Grundy-Satz ist \(\lambda\) genau dann verlierend, wenn
$$\operatorname{sg}_k(s_1)\oplus \operatorname{sg}_k(s_2)\oplus \cdots \oplus \operatorname{sg}_k(s_t)=0.$$
Damit besteht das Problem aus zwei Schritten: \(\operatorname{sg}_k(s)\) bestimmen und anschließend alle Partitionen von \(n\) mit Nim-Summe \(0\) zählen.
Schreiben wir
$$L_k(n)=\#\left\{\lambda\vdash n:\bigoplus_{s\in\lambda}\operatorname{sg}_k(s)=0\right\},$$
dann zählt \(L_k(n)\) die verlierenden Partitionen. Die gewinnenden Partitionen sind somit
$$F_k(n)=p(n)-L_k(n),$$
wobei \(p(n)\) die gewöhnliche Partitionsfunktion ist. Sobald die Haufen-Grundywerte bekannt sind und XOR-null-Partitionen gezählt werden können, ist also auch \(g(n)\) bestimmt.
Wenn nur Zweierteilungen erlaubt sind, kann ein Haufen der Größe \(s\) nur nach \(a+(s-a)\) mit \(1\le a\le s-1\) zerlegt werden. Die Implementierungen verwenden die exakte Formel
$$\operatorname{sg}_2(s)=\begin{cases} 1,&s\equiv 0\pmod{2},\\ 0,&s\equiv 1\pmod{2}, \end{cases}\qquad s\ge1.$$
Der Induktionsbeweis ist kurz. Ist \(s\) gerade, dann haben in jeder Zerlegung beide Teile dieselbe Parität, also hat jede Option XOR \(0\), und der mex ist \(1\). Ist \(s\) ungerade, dann besitzt jede Zerlegung einen geraden und einen ungeraden Teil, also hat jede Option XOR \(1\), und der mex ist \(0\).
Folglich ist eine Partition für \(k=2\) genau dann verlierend, wenn sie eine gerade Anzahl gerader Teile enthält.
Beim Drei-Wege-Streuen darf ein Haufen der Größe \(s\) entweder in zwei oder in drei positive Teile zerlegt werden. Die Implementierungen nehmen dafür keine weitere geschlossene Formel an, sondern berechnen die Sprague-Grundy-Tabelle direkt aus der mex-Definition:
$$\operatorname{sg}_3(s)=\operatorname{mex}\Bigl(A_2(s)\cup A_3(s)\Bigr),$$
wobei
$$A_2(s)=\left\{\operatorname{sg}_3(a)\oplus \operatorname{sg}_3(s-a):1\le a\le s-1\right\},$$
$$A_3(s)=\left\{\operatorname{sg}_3(a)\oplus \operatorname{sg}_3(b)\oplus \operatorname{sg}_3(c):a+b+c=s,\ a,b,c\ge1\right\}.$$
Ausgehend von \(\operatorname{sg}_3(1)=0\) erhält man zu Beginn die Werte
$$0,1,2,3,1,4,3,2,4,5,\dots$$
für die Haufengrößen \(1,2,3,4,5,6,7,8,9,10,\dots\). Da nur \(n=200\) benötigt wird, ist diese Tabellierung problemlos schnell genug.
Sobald Vierer-Zerlegungen erlaubt sind, stabilisiert sich das Ein-Haufen-Spiel auf die exakte lineare Regel
$$\operatorname{sg}_k(s)=s-1\qquad (k\ge4,\ s\ge1).$$
Der Grund ist eine Sättigung des mex. Jeder Zug von einem Haufen der Größe \(s\) erzeugt \(r\ge2\) positive Haufen \(x_1,\dots,x_r\), sodass unter der linearen Regel der Optionswert
$$\bigoplus_{i=1}^{r}(x_i-1)$$
ist. Dieses XOR ist nie größer als die gewöhnliche Summe, also
$$\bigoplus_{i=1}^{r}(x_i-1)\le \sum_{i=1}^{r}(x_i-1)=s-r\le s-2,$$
und damit ist \(s-1\) in einem Zug unerreichbar. Gleichzeitig ist das Vierer-Regime bereits reich genug, um jeden Nim-Wert von \(0\) bis \(s-2\) zu realisieren. Deshalb muss der mex gleich \(s-1\) sein. Somit führen alle Parameter \(k=4,5,\dots,n\) auf dieselbe Zählaufgabe.
Für festes \(k\) definieren wir \(D_k(t,x)\) als die Anzahl der Partitionen der Summe \(t\), deren Grundy-XOR gleich \(x\) ist. Die Anfangsbedingung lautet
$$D_k(0,0)=1.$$
Danach werden die Haufengrößen \(s=1,2,\dots,n\) nacheinander verarbeitet. Weil Partitionen Multimengen sind, verwendet man die übliche unbeschränkte Partitionsordnung:
$$D_k(t,\ x\oplus \operatorname{sg}_k(s))\mathrel{+}=D_k(t-s,\ x)\qquad (t\ge s).$$
Die aufsteigende Iteration über \(t\) erlaubt, dieselbe Größe \(s\) beliebig oft zu verwenden. Nach Verarbeitung aller Größen ist die Zahl der verlierenden Partitionen
$$L_k(n)=D_k(n,0).$$
Die gewöhnliche Partitionszahl \(p(n)\) wird mit derselben Münzwechsel-Idee, aber ohne XOR-Dimension berechnet. Am Ende gilt also
$$F_k(n)=p(n)-L_k(n)\pmod{10^9+7}.$$
Die drei obigen Regime zeigen, dass nur drei verschiedene Zählprobleme übrig bleiben:
$$k=2,\qquad k=3,\qquad k\ge4.$$
Daher folgt
$$g(n)=F_2(n)+F_3(n)+(n-3)F_4(n).$$
Genau das ist die entscheidende Vereinfachung: Statt \(n-1\) verschiedene Spiele zu lösen, löst das Programm nur drei.
Die Partitionen von \(5\) sind
$$5,\ 4+1,\ 3+2,\ 3+1+1,\ 2+2+1,\ 2+1+1+1,\ 1+1+1+1+1,$$
also \(p(5)=7\).
Für \(k=2\) lauten die Haufenwerte für die Größen \(1\) bis \(5\): \(0,1,0,1,0\). Verlieren heißt hier: gerade Anzahl gerader Teile. Gewinnt man also genau mit
$$4+1,\qquad 3+2,\qquad 2+1+1+1,$$
und daher ist \(F_2(5)=3\).
Für \(k=3\) liefert die Rekurrenz
$$\operatorname{sg}_3(1),\dots,\operatorname{sg}_3(5)=0,1,2,3,1.$$
Dann sind genau
$$2+2+1,\qquad 1+1+1+1+1$$
verlierend, also \(F_3(5)=5\).
Für jedes \(k\ge4\) ergibt die Regel \(\operatorname{sg}_k(s)=s-1\) die Haufenwerte \(0,1,2,3,4\). Wieder bleiben dieselben zwei Partitionen verlierend, also \(F_4(5)=5\). Damit
$$g(5)=F_2(5)+F_3(5)+2F_4(5)=3+5+2\cdot 5=18.$$
Dieser kleine Fall stimmt mit den in den Implementierungen verwendeten Kontrollwerten überein.
Die C++-, Python- und Java-Implementierungen folgen demselben Plan. Zuerst berechnen sie \(p(n)\) mit der üblichen Partitions-DP. Danach entstehen drei Tabellen für Einzelhaufen: die Paritätsregel für \(k=2\), die direkte mex-Tabelle für \(k=3\) und die lineare Tabelle \(s-1\) für das gesättigte Regime \(k\ge4\).
Für jede dieser drei Tabellen läuft anschließend eine zweite DP über Gesamtsumme und XOR-Zustand. Die XOR-Dimension hat Breite \(256\); das genügt für alle Grundywerte, die bis zur Haufengröße \(200\) auftreten. Die Zahl der verlierenden Partitionen ist genau der Zustand mit Gesamtsumme \(n\) und XOR \(0\), und durch Subtraktion von \(p(n)\) erhält man die Anzahl gewinnender Partitionen im jeweiligen Regime.
Zum Schluss kombiniert das Programm die drei Beiträge als
$$F_2(n)+F_3(n)+(n-3)F_4(n)\pmod{10^9+7}.$$
Vor der Endausgabe für \(n=200\) werden außerdem kleine Kontrollwerte wie \(F_2(5)=3\), \(F_3(5)=5\), \(g(7)=66\) und \(g(10)=291\) geprüft.
Sei \(n\) die Zielsumme und \(X=256\) die Breite des XOR-Zustandsraums. Die Berechnung der Partitionszahlen kostet \(O(n^2)\) Zeit. Die Tabellen für \(k=2\) und \(k\ge4\) entstehen linear, während die direkte mex-Rekurrenz für \(k=3\) \(O(n^3)\) Zeit benötigt, weil für jede Haufengröße alle Zwei- und Drei-Zerlegungen betrachtet werden. Jede XOR-Partitons-DP kostet \(O(n^2X)\) Zeit und \(O(nX)\) Speicher, und sie wird für drei Regime durchgeführt. Insgesamt ergibt das
$$O(n^3+n^2X)\ \text{Zeit},\qquad O(nX)\ \text{Speicher},$$
was für \(n=200\) völlig unproblematisch ist.
Bir konum, \(n\) sayısının \(\lambda=(s_1,\dots,s_t)\) biçimindeki bir partition'ıdır; her parça bir yığın boyutunu temsil eder. Sabit bir \(k\) parametresi için bir hamle, bir yığını seçip onu \(2\) ile \(k\) arasında sayıda boş olmayan alt yığına ayırmaktır. \(F_k(n)\), normal oyunda \(n\)'in kazanan partition sayısı olsun. İstenen büyüklük
$$g(n)=\sum_{k=2}^{n}F_k(n),$$
olup \(n=200\) için \(10^9+7\) modunda hesaplanır. Çözüm, tüm partition'ların bütün oyun ağaçlarını tek tek dolaşmaz. Önce tek yığın için Sprague-Grundy yasalarını çıkarır, sonra tüm partition'ları XOR dinamik programlamasıyla sayar.
\(\lambda=(s_1,\dots,s_t)\) partition'ı için, \(k\) parametresindeki oyunda boyutu \(s\) olan tek bir yığının Sprague-Grundy değerine \(\operatorname{sg}_k(s)\) diyelim. Sprague-Grundy teoremine göre \(\lambda\) tam ve ancak şu durumda kaybedendir:
$$\operatorname{sg}_k(s_1)\oplus \operatorname{sg}_k(s_2)\oplus \cdots \oplus \operatorname{sg}_k(s_t)=0.$$
Dolayısıyla problem iki katmandan oluşur: önce \(\operatorname{sg}_k(s)\)'yi belirlemek, sonra yığın nim-toplamı sıfır olan \(n\) partition'larını saymak.
Şunu tanımlayalım:
$$L_k(n)=\#\left\{\lambda\vdash n:\bigoplus_{s\in\lambda}\operatorname{sg}_k(s)=0\right\}.$$
Burada \(L_k(n)\) kaybeden partition'ları sayar. O halde kazanan partition sayısı
$$F_k(n)=p(n)-L_k(n),$$
olur; burada \(p(n)\) sıradan partition sayısıdır. Yani yığın Grundy değerleri biliniyorsa ve XOR'u sıfır olan partition'lar sayılabiliyorsa, \(g(n)\) de doğrudan bulunur.
Sadece ikiye ayırmaya izin verildiğinde, boyutu \(s\) olan bir yığın ancak \(a+(s-a)\) biçiminde ayrılabilir; burada \(1\le a\le s-1\). İmplementasyonların kullandığı tam kural şudur:
$$\operatorname{sg}_2(s)=\begin{cases} 1,&s\equiv 0\pmod{2},\\ 0,&s\equiv 1\pmod{2}, \end{cases}\qquad s\ge1.$$
İndüksiyon çok kısadır. \(s\) çiftse her ayrımda iki parça aynı paritededir; dolayısıyla her hamlenin XOR değeri \(0\) olur ve mex \(1\)'dir. \(s\) tekse her ayrım bir tek ve bir çift parça üretir; dolayısıyla her hamlenin XOR değeri \(1\) olur ve mex \(0\)'dır.
Böylece \(k=2\) için bir partition tam ve ancak çift sayıda çift parça içeriyorsa kaybedendir.
Üçe saçma durumunda, boyutu \(s\) olan bir yığın ya iki ya da üç pozitif parçaya bölünebilir. İmplementasyonlar burada ek bir kapalı form kullanmaz; Sprague-Grundy tablosunu mex tanımından doğrudan üretir:
$$\operatorname{sg}_3(s)=\operatorname{mex}\Bigl(A_2(s)\cup A_3(s)\Bigr),$$
burada
$$A_2(s)=\left\{\operatorname{sg}_3(a)\oplus \operatorname{sg}_3(s-a):1\le a\le s-1\right\},$$
$$A_3(s)=\left\{\operatorname{sg}_3(a)\oplus \operatorname{sg}_3(b)\oplus \operatorname{sg}_3(c):a+b+c=s,\ a,b,c\ge1\right\}.$$
\(\operatorname{sg}_3(1)=0\) tabanından başlayınca ilk değerler
$$0,1,2,3,1,4,3,2,4,5,\dots$$
şeklinde gelir; bunlar sırasıyla yığın boyutları \(1,2,3,4,5,6,7,8,9,10,\dots\) içindir. Hedef yalnızca \(n=200\) olduğu için bu tabloyu bir kez üretmek fazlasıyla yeterlidir.
Dörde ayırma izni geldiği anda, tek yığın oyunu şu tam doğrusal kurala oturur:
$$\operatorname{sg}_k(s)=s-1\qquad (k\ge4,\ s\ge1).$$
Bunun nedeni mex'in doygunlaşmasıdır. Boyutu \(s\) olan bir yığından yapılan her hamle, \(r\ge2\) tane pozitif yığın \(x_1,\dots,x_r\) üretir. Doğrusal yasa altında hamlenin değeri
$$\bigoplus_{i=1}^{r}(x_i-1)$$
olur. Bu XOR değeri sıradan toplamı hiçbir zaman aşmaz; dolayısıyla
$$\bigoplus_{i=1}^{r}(x_i-1)\le \sum_{i=1}^{r}(x_i-1)=s-r\le s-2,$$
yani \(s-1\) tek hamlede erişilemez. Öte yandan dört parçaya kadar bölme serbestliği, \(0\) ile \(s-2\) arasındaki her nim-değerini üretmeye yeter. Bu yüzden mex tam olarak \(s-1\) olur. Sonuç olarak \(k=4,5,\dots,n\) için aynı partition sayım problemi ortaya çıkar.
Sabit bir \(k\) için \(D_k(t,x)\), toplamı \(t\) olan ve yığın Grundy XOR'u \(x\) çıkan partition sayısı olsun. Başlangıç koşulu
$$D_k(0,0)=1$$
şeklindedir. Ardından \(s=1,2,\dots,n\) yığın boyutları teker teker işlenir. Partition'lar çokluk içeren kümeler olduğu için güncelleme, sınırsız kullanım düzeninde yapılır:
$$D_k(t,\ x\oplus \operatorname{sg}_k(s))\mathrel{+}=D_k(t-s,\ x)\qquad (t\ge s).$$
Toplamı artan sırada dolaşmak, aynı \(s\) boyutunun istenildiği kadar kez kullanılmasını sağlar. Tüm boyutlar işlendiğinde kaybeden sayısı
$$L_k(n)=D_k(n,0)$$
olur. Sıradan partition sayısı \(p(n)\) aynı madeni para değişimi fikriyle ama XOR boyutu olmadan hesaplanır. Sonuçta
$$F_k(n)=p(n)-L_k(n)\pmod{10^9+7}$$
elde edilir.
Yukarıdaki üç rejim, gerçekte sadece üç farklı sayım problemi kaldığını gösterir:
$$k=2,\qquad k=3,\qquad k\ge4.$$
Bu yüzden
$$g(n)=F_2(n)+F_3(n)+(n-3)F_4(n)$$
olur. Asıl kritik sadeleştirme budur: program \(n-1\) farklı oyun çözmek yerine yalnızca üç tanesini çözer.
\(5\)'in partition'ları şunlardır:
$$5,\ 4+1,\ 3+2,\ 3+1+1,\ 2+2+1,\ 2+1+1+1,\ 1+1+1+1+1,$$
dolayısıyla \(p(5)=7\).
\(k=2\) için, \(1\) ile \(5\) arasındaki yığın boyutlarının değerleri \(0,1,0,1,0\)'dır. Bir partition ancak çift sayıda çift parça içeriyorsa kaybedendir. O halde kazananlar
$$4+1,\qquad 3+2,\qquad 2+1+1+1$$
olur ve \(F_2(5)=3\) çıkar.
\(k=3\) için yukarıdaki özyineleme
$$\operatorname{sg}_3(1),\dots,\operatorname{sg}_3(5)=0,1,2,3,1$$
değerlerini verir. Bu durumda sadece
$$2+2+1,\qquad 1+1+1+1+1$$
partition'ları kaybedendir; dolayısıyla \(F_3(5)=5\).
Her \(k\ge4\) için \(\operatorname{sg}_k(s)=s-1\) kuralı, yığın değerlerini \(0,1,2,3,4\) yapar. Yine aynı iki partition kaybeden kalır; bu yüzden \(F_4(5)=5\). Sonuç olarak
$$g(5)=F_2(5)+F_3(5)+2F_4(5)=3+5+2\cdot 5=18.$$
Bu küçük örnek, implementasyonların kullandığı kontrol değerleriyle tam uyumludur.
C++, Python ve Java implementasyonları aynı planı izler. Önce standart partition DP ile \(p(n)\) hesaplanır. Sonra tek yığın için üç tablo hazırlanır: \(k=2\) için parite kuralı, \(k=3\) için doğrudan mex tablosu ve doygun rejim \(k\ge4\) için doğrusal \(s-1\) tablosu.
Bu üç tablonun her biri için, toplam ve XOR durumu üzerinde ikinci bir DP çalıştırılır. XOR boyutunun genişliği \(256\)'dır; bu, \(200\)'e kadar olan yığın boyutlarında ortaya çıkan tüm Grundy değerleri için yeterlidir. Kaybeden partition sayısı, toplamı \(n\) ve XOR'u \(0\) olan durumdur. Bunu \(p(n)\)'den çıkarmak o rejimin kazanan sayısını verir.
Son adımda program üç katkıyı şu şekilde birleştirir:
$$F_2(n)+F_3(n)+(n-3)F_4(n)\pmod{10^9+7}.$$
Ayrıca \(n=200\) için son değeri üretmeden önce \(F_2(5)=3\), \(F_3(5)=5\), \(g(7)=66\) ve \(g(10)=291\) gibi küçük kontrol değerleri de doğrulanır.
\(n\) hedef toplam, \(X=256\) ise XOR durum uzayının genişliği olsun. Partition sayılarını hesaplamak \(O(n^2)\) zaman alır. \(k=2\) ve \(k\ge4\) tabloları doğrusal zamanda kurulur. Buna karşılık \(k=3\) için doğrudan mex özyinelemesi, her yığın boyutunda tüm iki parçalı ve üç parçalı ayrımları taradığı için \(O(n^3)\) zaman ister. Her XOR-partition DP'si \(O(n^2X)\) zaman ve \(O(nX)\) bellek kullanır; bu işlem üç rejim için yapılır. Dolayısıyla toplam karmaşıklık
$$O(n^3+n^2X)\ \text{zaman},\qquad O(nX)\ \text{bellek}$$
olur; \(n=200\) için bu rahatlıkla uygulanabilir.
Una posición es una partición entera \(\lambda=(s_1,\dots,s_t)\) de \(n\), donde cada parte representa el tamaño de un montón. Para un parámetro fijo \(k\), un movimiento elige un montón y lo reemplaza por cualquier partición de ese montón en entre \(2\) y \(k\) montones no vacíos. Sea \(F_k(n)\) el número de particiones ganadoras de \(n\) en juego normal. La cantidad pedida es
$$g(n)=\sum_{k=2}^{n}F_k(n),$$
evaluada en \(n=200\) módulo \(10^9+7\). La solución no recorre directamente todos los árboles de juego de todas las particiones. Primero determina las leyes de Sprague-Grundy para un solo montón y luego cuenta particiones completas mediante programación dinámica con XOR.
Para una partición \(\lambda=(s_1,\dots,s_t)\), sea \(\operatorname{sg}_k(s)\) el valor de Sprague-Grundy de un solo montón de tamaño \(s\) en la variante con parámetro \(k\). Por el teorema de Sprague-Grundy, \(\lambda\) es perdedora exactamente cuando
$$\operatorname{sg}_k(s_1)\oplus \operatorname{sg}_k(s_2)\oplus \cdots \oplus \operatorname{sg}_k(s_t)=0.$$
Así, el problema tiene dos capas: determinar \(\operatorname{sg}_k(s)\) y después contar las particiones de \(n\) cuya suma Nim es cero.
Definamos
$$L_k(n)=\#\left\{\lambda\vdash n:\bigoplus_{s\in\lambda}\operatorname{sg}_k(s)=0\right\}.$$
Entonces \(L_k(n)\) cuenta las particiones perdedoras, mientras que las ganadoras son
$$F_k(n)=p(n)-L_k(n),$$
donde \(p(n)\) es el número ordinario de particiones. Por lo tanto, \(g(n)\) queda determinado en cuanto conocemos los valores Grundy de los montones y podemos contar las particiones con XOR nulo.
Cuando solo se permiten divisiones en dos partes, un montón de tamaño \(s\) puede pasar a \(a+(s-a)\) con \(1\le a\le s-1\). Las implementaciones usan la ley exacta
$$\operatorname{sg}_2(s)=\begin{cases} 1,&s\equiv 0\pmod{2},\\ 0,&s\equiv 1\pmod{2}, \end{cases}\qquad s\ge1.$$
La inducción es corta. Si \(s\) es par, toda división produce dos partes de la misma paridad, así que toda opción tiene XOR \(0\) y el mex es \(1\). Si \(s\) es impar, toda división produce una parte par y otra impar, así que toda opción tiene XOR \(1\) y el mex es \(0\).
En consecuencia, para \(k=2\) una partición es perdedora exactamente cuando contiene un número par de partes pares.
En la versión de tres vías, un montón de tamaño \(s\) puede dividirse en dos o en tres partes positivas. Las implementaciones no suponen aquí ninguna fórmula cerrada adicional; calculan la tabla de Sprague-Grundy directamente desde la definición de mex:
$$\operatorname{sg}_3(s)=\operatorname{mex}\Bigl(A_2(s)\cup A_3(s)\Bigr),$$
con
$$A_2(s)=\left\{\operatorname{sg}_3(a)\oplus \operatorname{sg}_3(s-a):1\le a\le s-1\right\},$$
$$A_3(s)=\left\{\operatorname{sg}_3(a)\oplus \operatorname{sg}_3(b)\oplus \operatorname{sg}_3(c):a+b+c=s,\ a,b,c\ge1\right\}.$$
Partiendo de \(\operatorname{sg}_3(1)=0\), los valores iniciales son
$$0,1,2,3,1,4,3,2,4,5,\dots$$
para tamaños de montón \(1,2,3,4,5,6,7,8,9,10,\dots\). Como el objetivo solo llega hasta \(n=200\), basta con tabularlos una sola vez.
En cuanto se permiten divisiones en cuatro partes, el juego de un solo montón se estabiliza en la regla lineal exacta
$$\operatorname{sg}_k(s)=s-1\qquad (k\ge4,\ s\ge1).$$
La razón es que el mex se satura. Todo movimiento desde un montón de tamaño \(s\) crea \(r\ge2\) montones positivos \(x_1,\dots,x_r\), de modo que bajo la ley lineal el valor alcanzado es
$$\bigoplus_{i=1}^{r}(x_i-1).$$
Ese XOR nunca supera la suma ordinaria, así que
$$\bigoplus_{i=1}^{r}(x_i-1)\le \sum_{i=1}^{r}(x_i-1)=s-r\le s-2,$$
y por tanto \(s-1\) no es alcanzable en un solo movimiento. Al mismo tiempo, el régimen con cuatro vías ya es suficientemente rico para realizar todos los nimbers entre \(0\) y \(s-2\), lo que fuerza a que el mex sea exactamente \(s-1\). En consecuencia, todos los parámetros \(k=4,5,\dots,n\) conducen al mismo problema de conteo.
Para un \(k\) fijo, definimos \(D_k(t,x)\) como el número de particiones de suma total \(t\) cuyo XOR de valores Grundy es \(x\). La condición inicial es
$$D_k(0,0)=1.$$
Luego se procesan los tamaños de montón \(s=1,2,\dots,n\) uno por uno. Como las particiones son multisets, la actualización usa el orden estándar de particiones no acotadas:
$$D_k(t,\ x\oplus \operatorname{sg}_k(s))\mathrel{+}=D_k(t-s,\ x)\qquad (t\ge s).$$
Recorrer \(t\) en orden creciente permite usar el mismo tamaño \(s\) cualquier número de veces. Cuando todos los tamaños han sido procesados, el número de particiones perdedoras es
$$L_k(n)=D_k(n,0).$$
El número ordinario de particiones \(p(n)\) se calcula con la misma idea de cambio de monedas, pero sin la dimensión XOR. Por tanto, al final
$$F_k(n)=p(n)-L_k(n)\pmod{10^9+7}.$$
Los tres regímenes anteriores implican que solo quedan tres problemas de conteo distintos:
$$k=2,\qquad k=3,\qquad k\ge4.$$
Por ello
$$g(n)=F_2(n)+F_3(n)+(n-3)F_4(n).$$
Esa es la simplificación decisiva: en lugar de resolver \(n-1\) juegos diferentes, el programa solo resuelve tres.
Las particiones de \(5\) son
$$5,\ 4+1,\ 3+2,\ 3+1+1,\ 2+2+1,\ 2+1+1+1,\ 1+1+1+1+1,$$
de modo que \(p(5)=7\).
Para \(k=2\), los valores de los montones en tamaños \(1\) a \(5\) son \(0,1,0,1,0\). Una partición es perdedora si y solo si contiene un número par de partes pares, así que las ganadoras son
$$4+1,\qquad 3+2,\qquad 2+1+1+1,$$
y por tanto \(F_2(5)=3\).
Para \(k=3\), la recurrencia anterior produce
$$\operatorname{sg}_3(1),\dots,\operatorname{sg}_3(5)=0,1,2,3,1.$$
Las únicas particiones perdedoras son entonces
$$2+2+1,\qquad 1+1+1+1+1,$$
por lo que \(F_3(5)=5\).
Para todo \(k\ge4\), la regla \(\operatorname{sg}_k(s)=s-1\) da los valores \(0,1,2,3,4\), y vuelven a quedar perdedoras esas mismas dos particiones, así que \(F_4(5)=5\). En consecuencia,
$$g(5)=F_2(5)+F_3(5)+2F_4(5)=3+5+2\cdot 5=18.$$
Este caso pequeño coincide con los valores de control usados por las implementaciones.
Las implementaciones en C++, Python y Java siguen el mismo esquema. Primero calculan \(p(n)\) con la DP estándar de particiones. Después construyen tres tablas de Grundy para un solo montón: la regla de paridad para \(k=2\), la tabla mex directa para \(k=3\) y la tabla lineal \(s-1\) para el régimen saturado \(k\ge4\).
Para cada una de esas tres tablas, la implementación ejecuta una segunda DP sobre suma total y estado XOR. La dimensión XOR tiene anchura \(256\), suficiente para todos los valores Grundy que aparecen hasta tamaño \(200\). El número de particiones perdedoras es el estado con suma total \(n\) y XOR \(0\), y al restarlo de \(p(n)\) se obtiene la cantidad de particiones ganadoras en ese régimen.
Por último, el programa combina las tres contribuciones como
$$F_2(n)+F_3(n)+(n-3)F_4(n)\pmod{10^9+7}.$$
Antes de producir el valor final para \(n=200\), también verifica pequeños puntos de control como \(F_2(5)=3\), \(F_3(5)=5\), \(g(7)=66\) y \(g(10)=291\).
Sea \(n\) la suma objetivo y \(X=256\) la anchura del espacio XOR. Calcular los números de partición cuesta \(O(n^2)\) tiempo. Las tablas para \(k=2\) y \(k\ge4\) se construyen linealmente, mientras que la recurrencia mex directa para \(k=3\) cuesta \(O(n^3)\) porque para cada tamaño de montón se recorren todas las divisiones en dos y en tres partes. Cada DP XOR para particiones cuesta \(O(n^2X)\) tiempo y \(O(nX)\) memoria, y se ejecuta para tres regímenes. Por tanto, la complejidad total es
$$O(n^3+n^2X)\ \text{tiempo},\qquad O(nX)\ \text{memoria},$$
lo cual es totalmente práctico para \(n=200\).
一个局面是 \(n\) 的一个整数分拆 \(\lambda=(s_1,\dots,s_t)\)，其中每一部分都表示一堆石子的大小。对固定参数 \(k\)，一次操作是选中某一堆，然后把它改写成该堆大小的另一个分拆，且新堆数必须在 \(2\) 到 \(k\) 之间，并且每堆都非空。记 \(F_k(n)\) 为在正常规则下，大小总和为 \(n\) 的先手必胜分拆数。题目要求计算
$$g(n)=\sum_{k=2}^{n}F_k(n),$$
并在 \(n=200\) 时对 \(10^9+7\) 取模。解法并不是把所有分拆的全部博弈树都暴力跑一遍，而是先弄清单堆游戏的 Sprague-Grundy 规律，再用 XOR 动态规划统计整个位形空间。
对分拆 \(\lambda=(s_1,\dots,s_t)\)，记 \(\operatorname{sg}_k(s)\) 为参数 \(k\) 下、单个大小为 \(s\) 的堆的 Sprague-Grundy 值。根据 Sprague-Grundy 定理，\(\lambda\) 是必败局面当且仅当
$$\operatorname{sg}_k(s_1)\oplus \operatorname{sg}_k(s_2)\oplus \cdots \oplus \operatorname{sg}_k(s_t)=0.$$
所以整个问题可以拆成两层：先确定 \(\operatorname{sg}_k(s)\)，再统计总和为 \(n\) 且堆异或和为零的分拆个数。
定义
$$L_k(n)=\#\left\{\lambda\vdash n:\bigoplus_{s\in\lambda}\operatorname{sg}_k(s)=0\right\}.$$
这里 \(L_k(n)\) 就是必败分拆数，而必胜分拆数自然等于
$$F_k(n)=p(n)-L_k(n),$$
其中 \(p(n)\) 是普通整数分拆数。也就是说，只要知道每种堆大小的 Grundy 值，并且能够数出 XOR 为零的分拆，就能得到 \(g(n)\)。
当只允许把一堆拆成两堆时，大小为 \(s\) 的堆只能走到 \(a+(s-a)\)，其中 \(1\le a\le s-1\)。实现所使用的精确规律是
$$\operatorname{sg}_2(s)=\begin{cases} 1,&s\equiv 0\pmod{2},\\ 0,&s\equiv 1\pmod{2}, \end{cases}\qquad s\ge1.$$
这个结论可以直接归纳出来。假设小于 \(s\) 的情形都已经成立。如果 \(s\) 是偶数，那么任何拆分都会得到两个同奇偶性的部分，因此每个后继局面的 XOR 都是 \(0\)，所以 mex 为 \(1\)。如果 \(s\) 是奇数，那么任何拆分都会得到一个奇数部分和一个偶数部分，因此每个后继局面的 XOR 都是 \(1\)，所以 mex 为 \(0\)。
于是对于 \(k=2\)，一个分拆必败，当且仅当其中偶数部分的个数是偶数。
在三路散开的版本中，大小为 \(s\) 的一堆可以拆成两个正部分，也可以拆成三个正部分。实现并没有再假设额外的闭式，而是直接按 mex 定义递推出整张 Sprague-Grundy 表：
$$\operatorname{sg}_3(s)=\operatorname{mex}\Bigl(A_2(s)\cup A_3(s)\Bigr),$$
其中
$$A_2(s)=\left\{\operatorname{sg}_3(a)\oplus \operatorname{sg}_3(s-a):1\le a\le s-1\right\},$$
$$A_3(s)=\left\{\operatorname{sg}_3(a)\oplus \operatorname{sg}_3(b)\oplus \operatorname{sg}_3(c):a+b+c=s,\ a,b,c\ge1\right\}.$$
从 \(\operatorname{sg}_3(1)=0\) 出发，前面的若干项是
$$0,1,2,3,1,4,3,2,4,5,\dots$$
对应堆大小 \(1,2,3,4,5,6,7,8,9,10,\dots\)。因为题目只需要到 \(n=200\)，所以把这张表预先算到 \(200\) 完全足够。
一旦允许四路拆分，单堆游戏就稳定到精确的线性公式
$$\operatorname{sg}_k(s)=s-1\qquad (k\ge4,\ s\ge1).$$
原因是 mex 在这里发生了“饱和”。从大小为 \(s\) 的一堆出发，任何一步都会产生 \(r\ge2\) 个正堆 \(x_1,\dots,x_r\)。如果使用线性规律，那么该步到达的 nimber 是
$$\bigoplus_{i=1}^{r}(x_i-1).$$
这个 XOR 永远不会超过普通和，因此有
$$\bigoplus_{i=1}^{r}(x_i-1)\le \sum_{i=1}^{r}(x_i-1)=s-r\le s-2,$$
所以 \(s-1\) 不可能在一步之内到达。另一方面，允许至多四堆已经足够丰富，可以实现从 \(0\) 到 \(s-2\) 的每一个 nimber，于是 mex 被迫等于 \(s-1\)。这意味着所有 \(k=4,5,\dots,n\) 实际上都归并成同一个计数问题。
对固定 \(k\)，定义 \(D_k(t,x)\) 为“总和为 \(t\)、所有堆 Grundy 值异或结果为 \(x\) 的分拆个数”。初始条件是
$$D_k(0,0)=1.$$
然后按顺序处理堆大小 \(s=1,2,\dots,n\)。由于分拆本质上是多重集合，更新方式就是标准的“无限次取用”分拆递推：
$$D_k(t,\ x\oplus \operatorname{sg}_k(s))\mathrel{+}=D_k(t-s,\ x)\qquad (t\ge s).$$
按 \(t\) 递增遍历，就允许同一个大小 \(s\) 在分拆中出现任意多次。所有大小都处理完之后，必败分拆数正是
$$L_k(n)=D_k(n,0).$$
普通分拆数 \(p(n)\) 也用同样的“硬币兑换”思想计算，只是没有 XOR 这一维。因此最终有
$$F_k(n)=p(n)-L_k(n)\pmod{10^9+7}.$$
上面的三个规律说明，真正不同的只剩下三类问题：
$$k=2,\qquad k=3,\qquad k\ge4.$$
于是
$$g(n)=F_2(n)+F_3(n)+(n-3)F_4(n).$$
这是整个解法最关键的化简：程序不再需要处理 \(n-1\) 个不同的游戏参数，而只需要处理三个代表性情形。
\(5\) 的全部分拆是
$$5,\ 4+1,\ 3+2,\ 3+1+1,\ 2+2+1,\ 2+1+1+1,\ 1+1+1+1+1,$$
所以 \(p(5)=7\)。
对 \(k=2\)，大小 \(1\) 到 \(5\) 的单堆值分别为 \(0,1,0,1,0\)。一个分拆只有在偶数部分个数为偶数时才是必败，因此必胜分拆是
$$4+1,\qquad 3+2,\qquad 2+1+1+1,$$
从而 \(F_2(5)=3\)。
对 \(k=3\)，由上面的递推得到
$$\operatorname{sg}_3(1),\dots,\operatorname{sg}_3(5)=0,1,2,3,1.$$
这时唯一的必败分拆是
$$2+2+1,\qquad 1+1+1+1+1,$$
所以 \(F_3(5)=5\)。
对所有 \(k\ge4\)，线性规律 \(\operatorname{sg}_k(s)=s-1\) 给出 \(0,1,2,3,4\)，而必败分拆仍然是同样那两种，因此 \(F_4(5)=5\)。于是
$$g(5)=F_2(5)+F_3(5)+2F_4(5)=3+5+2\cdot 5=18.$$
这个小例子正好对应实现里使用的检查点。
C++、Python 和 Java 三个实现遵循完全相同的思路。它们先用标准分拆 DP 计算 \(p(n)\)。然后构造三张单堆 Grundy 表：\(k=2\) 的奇偶规律，\(k=3\) 的直接 mex 递推表，以及饱和区间 \(k\ge4\) 的线性表 \(s-1\)。
对这三张表中的每一张，实现都会再跑一次“总和 + XOR 状态”的动态规划。XOR 这一维的宽度取 \(256\)，足以覆盖到堆大小 \(200\) 时会出现的所有 Grundy 值。总和为 \(n\)、XOR 为 \(0\) 的状态就是必败分拆数；再用 \(p(n)\) 减掉它，就得到该区间下的必胜分拆数。
最后程序按
$$F_2(n)+F_3(n)+(n-3)F_4(n)\pmod{10^9+7}$$
把三部分合并起来，并在输出 \(n=200\) 的最终结果之前检查 \(F_2(5)=3\)、\(F_3(5)=5\)、\(g(7)=66\)、\(g(10)=291\) 这些小型校验值。
设目标总和为 \(n\)，XOR 状态宽度为 \(X=256\)。普通分拆数的计算需要 \(O(n^2)\) 时间。\(k=2\) 与 \(k\ge4\) 的单堆表都是线性时间，而 \(k=3\) 的直接 mex 递推因为每个堆大小都要扫描所有二拆与三拆，时间是 \(O(n^3)\)。每次 XOR 分拆 DP 需要 \(O(n^2X)\) 时间和 \(O(nX)\) 空间，并且这样的 DP 一共做三次。因此总复杂度为
$$O(n^3+n^2X)\ \text{时间},\qquad O(nX)\ \text{空间},$$
对 \(n=200\) 来说完全可行。
Позиция задается разбиением числа \(n\): \(\lambda=(s_1,\dots,s_t)\), где каждая часть означает размер одной кучи. При фиксированном параметре \(k\) ход состоит в том, чтобы выбрать одну кучу и заменить ее любым разбиением этой кучи на число непустых куч от \(2\) до \(k\). Обозначим через \(F_k(n)\) число выигрышных разбиений числа \(n\) при нормальной игре. Требуется вычислить
$$g(n)=\sum_{k=2}^{n}F_k(n),$$
а затем взять результат при \(n=200\) по модулю \(10^9+7\). Решение не перебирает напрямую все игровые деревья всех разбиений. Вместо этого сначала выясняются законы Sprague-Grundy для одной кучи, а затем целые разбиения подсчитываются через XOR-динамику.
Для разбиения \(\lambda=(s_1,\dots,s_t)\) обозначим через \(\operatorname{sg}_k(s)\) значение Sprague-Grundy одной кучи размера \(s\) в варианте с параметром \(k\). По теореме Шпрага-Гранди разбиение \(\lambda\) проигрышно тогда и только тогда, когда
$$\operatorname{sg}_k(s_1)\oplus \operatorname{sg}_k(s_2)\oplus \cdots \oplus \operatorname{sg}_k(s_t)=0.$$
Тем самым задача распадается на две части: сначала найти \(\operatorname{sg}_k(s)\), а затем посчитать все разбиения числа \(n\) с нулевой ним-суммой.
Введем обозначение
$$L_k(n)=\#\left\{\lambda\vdash n:\bigoplus_{s\in\lambda}\operatorname{sg}_k(s)=0\right\}.$$
Тогда \(L_k(n)\) — это число проигрышных разбиений, а число выигрышных разбиений равно
$$F_k(n)=p(n)-L_k(n),$$
где \(p(n)\) — обычная функция числа разбиений. Следовательно, как только известны значения Grundy для куч и можно посчитать разбиения с XOR, равным нулю, величина \(g(n)\) определяется автоматически.
Если разрешены только разбиения на две части, то куча размера \(s\) может перейти только в \(a+(s-a)\), где \(1\le a\le s-1\). В реализациях используется точный закон
$$\operatorname{sg}_2(s)=\begin{cases} 1,&s\equiv 0\pmod{2},\\ 0,&s\equiv 1\pmod{2}, \end{cases}\qquad s\ge1.$$
Индукция здесь совсем короткая. Если \(s\) четно, то в любом разбиении обе части имеют одинаковую четность, значит XOR каждого хода равен \(0\), и mex равен \(1\). Если \(s\) нечетно, то в любом разбиении одна часть четная, а другая нечетная, значит XOR каждого хода равен \(1\), и mex равен \(0\).
Итак, при \(k=2\) разбиение проигрышно ровно тогда, когда в нем четное число четных частей.
В трехчастном режиме куча размера \(s\) может быть разбита либо на две, либо на три положительные части. Реализации не используют здесь дополнительную замкнутую формулу, а строят таблицу Sprague-Grundy напрямую по определению mex:
$$\operatorname{sg}_3(s)=\operatorname{mex}\Bigl(A_2(s)\cup A_3(s)\Bigr),$$
где
$$A_2(s)=\left\{\operatorname{sg}_3(a)\oplus \operatorname{sg}_3(s-a):1\le a\le s-1\right\},$$
$$A_3(s)=\left\{\operatorname{sg}_3(a)\oplus \operatorname{sg}_3(b)\oplus \operatorname{sg}_3(c):a+b+c=s,\ a,b,c\ge1\right\}.$$
Начиная с \(\operatorname{sg}_3(1)=0\), получаем начальные значения
$$0,1,2,3,1,4,3,2,4,5,\dots$$
для размеров куч \(1,2,3,4,5,6,7,8,9,10,\dots\). Поскольку нужно только \(n=200\), такой прямой табуляции более чем достаточно.
Как только разрешены разбиения на четыре части, игра на одной куче стабилизируется на точном линейном правиле
$$\operatorname{sg}_k(s)=s-1\qquad (k\ge4,\ s\ge1).$$
Причина в насыщении mex. Любой ход из кучи размера \(s\) создает \(r\ge2\) положительных куч \(x_1,\dots,x_r\), и при линейном правиле значение позиции после хода равно
$$\bigoplus_{i=1}^{r}(x_i-1).$$
Этот XOR никогда не превосходит обычную сумму, поэтому
$$\bigoplus_{i=1}^{r}(x_i-1)\le \sum_{i=1}^{r}(x_i-1)=s-r\le s-2,$$
а значит \(s-1\) недостижимо за один ход. При этом режима с четырьмя частями уже хватает, чтобы реализовать все nim-значения от \(0\) до \(s-2\), поэтому mex вынужден быть равным \(s-1\). Следовательно, все параметры \(k=4,5,\dots,n\) приводят к одной и той же задаче подсчета.
Для фиксированного \(k\) определим \(D_k(t,x)\) как число разбиений суммы \(t\), у которых XOR значений Grundy равен \(x\). Начальное условие таково:
$$D_k(0,0)=1.$$
Далее размеры куч \(s=1,2,\dots,n\) обрабатываются по очереди. Поскольку разбиения — это мультимножества, используется стандартный порядок для неограниченных разбиений:
$$D_k(t,\ x\oplus \operatorname{sg}_k(s))\mathrel{+}=D_k(t-s,\ x)\qquad (t\ge s).$$
Проход по \(t\) в возрастающем порядке позволяет использовать один и тот же размер \(s\) сколько угодно раз. После обработки всех размеров число проигрышных разбиений равно
$$L_k(n)=D_k(n,0).$$
Обычное число разбиений \(p(n)\) вычисляется той же идеей размена монет, но без XOR-измерения. Поэтому в итоге
$$F_k(n)=p(n)-L_k(n)\pmod{10^9+7}.$$
Три режима выше показывают, что реально остается только три разных задачи подсчета:
$$k=2,\qquad k=3,\qquad k\ge4.$$
Отсюда
$$g(n)=F_2(n)+F_3(n)+(n-3)F_4(n).$$
Это и есть ключевое упрощение: вместо \(n-1\) разных игр программа решает только три представительных случая.
Разбиения числа \(5\) таковы:
$$5,\ 4+1,\ 3+2,\ 3+1+1,\ 2+2+1,\ 2+1+1+1,\ 1+1+1+1+1,$$
поэтому \(p(5)=7\).
Для \(k=2\) значения куч размеров от \(1\) до \(5\) равны \(0,1,0,1,0\). Разбиение проигрышно тогда и только тогда, когда в нем четное число четных частей. Значит, выигрышные разбиения — это
$$4+1,\qquad 3+2,\qquad 2+1+1+1,$$
и потому \(F_2(5)=3\).
Для \(k=3\) рекурсия дает
$$\operatorname{sg}_3(1),\dots,\operatorname{sg}_3(5)=0,1,2,3,1.$$
Тогда проигрышными оказываются только
$$2+2+1,\qquad 1+1+1+1+1,$$
так что \(F_3(5)=5\).
Для любого \(k\ge4\) правило \(\operatorname{sg}_k(s)=s-1\) дает значения \(0,1,2,3,4\), и те же две позиции остаются проигрышными, то есть \(F_4(5)=5\). Следовательно,
$$g(5)=F_2(5)+F_3(5)+2F_4(5)=3+5+2\cdot 5=18.$$
Этот малый пример совпадает с контрольными значениями, используемыми в реализациях.
Реализации на C++, Python и Java устроены одинаково. Сначала они вычисляют \(p(n)\) стандартной DP для разбиений. Затем строятся три таблицы Grundy для одной кучи: правило четности для \(k=2\), прямая mex-таблица для \(k=3\) и линейная таблица \(s-1\) для насыщенного режима \(k\ge4\).
Для каждой из этих трех таблиц реализация запускает вторую DP по общей сумме и XOR-состоянию. Ширина XOR-измерения равна \(256\), чего достаточно для всех значений Grundy, возникающих при размерах куч до \(200\). Число проигрышных разбиений — это состояние с суммой \(n\) и XOR, равным \(0\), а вычитание из \(p(n)\) дает число выигрышных разбиений для соответствующего режима.
В финале программа объединяет три вклада формулой
$$F_2(n)+F_3(n)+(n-3)F_4(n)\pmod{10^9+7}.$$
Перед выдачей ответа для \(n=200\) также проверяются малые контрольные значения: \(F_2(5)=3\), \(F_3(5)=5\), \(g(7)=66\) и \(g(10)=291\).
Пусть \(n\) — целевая сумма, а \(X=256\) — ширина XOR-пространства состояний. Вычисление обычных чисел разбиений стоит \(O(n^2)\) времени. Таблицы для \(k=2\) и \(k\ge4\) строятся линейно, а прямая mex-рекурсия для \(k=3\) требует \(O(n^3)\) времени, потому что для каждого размера кучи просматриваются все разбиения на две и на три части. Каждая XOR-DP для разбиений стоит \(O(n^2X)\) времени и \(O(nX)\) памяти, и таких DP выполняется три. Итак, общая сложность равна
$$O(n^3+n^2X)\ \text{по времени},\qquad O(nX)\ \text{по памяти},$$
что полностью практично для \(n=200\).
تمثل الحالة بتقسيم صحيح للعدد \(n\) على الصورة \(\lambda=(s_1,\dots,s_t)\)، حيث تمثل كل قطعة حجم كومة. عند تثبيت المعامل \(k\)، تكون الحركة باختيار كومة واحدة ثم استبدالها بأي تقسيم لذلك الحجم إلى عدد من الأكوام غير الفارغة بين \(2\) و\(k\). نرمز بـ \(F_k(n)\) إلى عدد التقسيمات الرابحة للمجموع \(n\) في اللعب العادي. والكمية المطلوبة هي
$$g(n)=\sum_{k=2}^{n}F_k(n),$$
ثم نقيمها عند \(n=200\) بترديد \(10^9+7\). الحل لا يعدد جميع أشجار اللعب لكل التقسيمات مباشرة، بل يحدد أولًا قوانين Sprague-Grundy لكومة واحدة، ثم يعد التقسيمات الكاملة بواسطة برمجة ديناميكية على XOR.
للتقسيم \(\lambda=(s_1,\dots,s_t)\)، نرمز بـ \(\operatorname{sg}_k(s)\) إلى قيمة Sprague-Grundy لكومة واحدة حجمها \(s\) في النسخة ذات المعامل \(k\). وبحسب نظرية Sprague-Grundy يكون \(\lambda\) وضعًا خاسرًا إذا وفقط إذا كان
$$\operatorname{sg}_k(s_1)\oplus \operatorname{sg}_k(s_2)\oplus \cdots \oplus \operatorname{sg}_k(s_t)=0.$$
إذًا تنقسم المسألة إلى طبقتين: تحديد \(\operatorname{sg}_k(s)\) أولًا، ثم عد جميع تقسيمات \(n\) التي يكون مجموعها النيمي XOR مساويًا للصفر.
نعرف
$$L_k(n)=\#\left\{\lambda\vdash n:\bigoplus_{s\in\lambda}\operatorname{sg}_k(s)=0\right\}.$$
وهكذا فإن \(L_k(n)\) يعد التقسيمات الخاسرة، بينما عدد التقسيمات الرابحة هو
$$F_k(n)=p(n)-L_k(n),$$
حيث \(p(n)\) هو عدد التقسيمات الصحيحية المعتاد. لذلك يصبح حساب \(g(n)\) ممكنًا بمجرد معرفة قيم Grundy للأكوام والقدرة على عد التقسيمات التي يكون XOR فيها صفرًا.
عندما يسمح فقط بالتقسيم إلى جزأين، فإن الكومة ذات الحجم \(s\) لا تنتقل إلا إلى \(a+(s-a)\) حيث \(1\le a\le s-1\). تستخدم التنفيذات القانون الدقيق التالي:
$$\operatorname{sg}_2(s)=\begin{cases} 1,&s\equiv 0\pmod{2},\\ 0,&s\equiv 1\pmod{2}, \end{cases}\qquad s\ge1.$$
والبرهان بالاستقراء قصير جدًا. إذا كان \(s\) زوجيًا فإن كل تقسيم يعطي جزأين لهما نفس الفردية، وبالتالي يكون XOR لكل حركة مساويًا للصفر، ومن ثم يكون mex هو \(1\). وإذا كان \(s\) فرديًا فإن كل تقسيم يعطي جزءًا زوجيًا وآخر فرديًا، وبالتالي يكون XOR لكل حركة مساويًا لـ \(1\)، ومن ثم يكون mex هو \(0\).
إذن في حالة \(k=2\)، يكون التقسيم خاسرًا إذا وفقط إذا احتوى على عدد زوجي من الأجزاء الزوجية.
في نمط التبعثر الثلاثي يمكن تقسيم كومة حجمها \(s\) إلى جزأين موجبين أو إلى ثلاثة أجزاء موجبة. التنفيذات لا تفترض هنا صيغة مغلقة إضافية، بل تبني جدول Sprague-Grundy مباشرة من تعريف mex:
$$\operatorname{sg}_3(s)=\operatorname{mex}\Bigl(A_2(s)\cup A_3(s)\Bigr),$$
حيث
$$A_2(s)=\left\{\operatorname{sg}_3(a)\oplus \operatorname{sg}_3(s-a):1\le a\le s-1\right\},$$
$$A_3(s)=\left\{\operatorname{sg}_3(a)\oplus \operatorname{sg}_3(b)\oplus \operatorname{sg}_3(c):a+b+c=s,\ a,b,c\ge1\right\}.$$
انطلاقًا من \(\operatorname{sg}_3(1)=0\)، نحصل في البداية على القيم
$$0,1,2,3,1,4,3,2,4,5,\dots$$
للأحجام \(1,2,3,4,5,6,7,8,9,10,\dots\). وبما أن الهدف لا يتجاوز \(n=200\)، فإن بناء هذا الجدول مرة واحدة يكفي تمامًا.
بمجرد السماح بالتقسيم إلى أربع كومات، تستقر لعبة الكومة الواحدة على القانون الخطي الدقيق
$$\operatorname{sg}_k(s)=s-1\qquad (k\ge4,\ s\ge1).$$
والسبب هو تشبع قيمة mex. فكل حركة من كومة حجمها \(s\) تنشئ \(r\ge2\) من الأكوام الموجبة \(x_1,\dots,x_r\)، وتحت القانون الخطي تصبح قيمة الوضع الناتج
$$\bigoplus_{i=1}^{r}(x_i-1).$$
وهذا XOR لا يتجاوز المجموع العادي، ومن ثم
$$\bigoplus_{i=1}^{r}(x_i-1)\le \sum_{i=1}^{r}(x_i-1)=s-r\le s-2,$$
أي إن \(s-1\) غير قابل للوصول في حركة واحدة. وفي المقابل فإن السماح حتى بأربع كومات يكفي لتحقيق كل nimber من \(0\) إلى \(s-2\)، ولهذا يجبر mex على أن يكون مساويًا تمامًا لـ \(s-1\). ونتيجة لذلك فإن جميع القيم \(k=4,5,\dots,n\) تعطي مسألة عد واحدة بعينها.
لـ \(k\) ثابت، لنعرف \(D_k(t,x)\) بأنه عدد التقسيمات ذات المجموع \(t\) والتي يكون XOR لقيم Grundy فيها مساويًا لـ \(x\). شرط البداية هو
$$D_k(0,0)=1.$$
بعد ذلك نعالج أحجام الأكوام \(s=1,2,\dots,n\) واحدًا واحدًا. ولأن التقسيمات تمثل متعددات مجموعات، فإن التحديث يكون بترتيب التقسيم غير المحدود القياسي:
$$D_k(t,\ x\oplus \operatorname{sg}_k(s))\mathrel{+}=D_k(t-s,\ x)\qquad (t\ge s).$$
اجتياز \(t\) تصاعديًا يسمح باستخدام الحجم نفسه \(s\) أي عدد من المرات. وبعد معالجة جميع الأحجام يصبح عدد التقسيمات الخاسرة هو
$$L_k(n)=D_k(n,0).$$
أما عدد التقسيمات المعتاد \(p(n)\) فيحسب بالفكرة نفسها الخاصة بتبديل العملات ولكن من دون بعد XOR. وعليه نحصل أخيرًا على
$$F_k(n)=p(n)-L_k(n)\pmod{10^9+7}.$$
توضح الأنظمة الثلاثة السابقة أن ما يبقى فعلًا هو ثلاث مسائل عد مختلفة فقط:
$$k=2,\qquad k=3,\qquad k\ge4.$$
ومن ثم
$$g(n)=F_2(n)+F_3(n)+(n-3)F_4(n).$$
وهذا هو التبسيط الحاسم: بدل حل \(n-1\) لعبة مختلفة، يكتفي البرنامج بحل ثلاث حالات ممثلة.
تقسيمات العدد \(5\) هي
$$5,\ 4+1,\ 3+2,\ 3+1+1,\ 2+2+1,\ 2+1+1+1,\ 1+1+1+1+1,$$
ولذلك \(p(5)=7\).
في حالة \(k=2\)، تكون قيم الأكوام للأحجام من \(1\) إلى \(5\) هي \(0,1,0,1,0\). ويكون التقسيم خاسرًا إذا وفقط إذا احتوى على عدد زوجي من الأجزاء الزوجية، ولذلك فإن التقسيمات الرابحة هي
$$4+1,\qquad 3+2,\qquad 2+1+1+1,$$
ومن ثم \(F_2(5)=3\).
وفي حالة \(k=3\)، تعطينا العلاقة العودية
$$\operatorname{sg}_3(1),\dots,\operatorname{sg}_3(5)=0,1,2,3,1.$$
وعندها لا يبقى خاسرًا إلا التقسيمان
$$2+2+1,\qquad 1+1+1+1+1,$$
ولذلك \(F_3(5)=5\).
أما لكل \(k\ge4\)، فإن القاعدة \(\operatorname{sg}_k(s)=s-1\) تعطي القيم \(0,1,2,3,4\)، ويبقى التقسيمان نفسيهما خاسرين، وبالتالي \(F_4(5)=5\). إذًا
$$g(5)=F_2(5)+F_3(5)+2F_4(5)=3+5+2\cdot 5=18.$$
وهذا المثال الصغير يطابق قيم التحقق المستخدمة في التنفيذات.
تسير التنفيذات في C++ وPython وJava وفق الخطة نفسها. أولًا تحسب \(p(n)\) ببرمجة ديناميكية قياسية للتقسيمات. ثم تبني ثلاث جداول لقيم Grundy لكومة واحدة: قاعدة الزوجية للحالة \(k=2\)، وجدول mex المباشر للحالة \(k=3\)، والجدول الخطي \(s-1\) لمنطقة التشبع \(k\ge4\).
وبالنسبة إلى كل واحد من هذه الجداول الثلاثة، تشغل التنفيذات برمجة ديناميكية ثانية على مجموع الأحجام وحالة XOR. عرض بعد XOR هو \(256\)، وهذا يكفي لجميع قيم Grundy التي تظهر حتى حجم كومة \(200\). وعدد التقسيمات الخاسرة هو الحالة التي يكون فيها المجموع \(n\) وXOR مساويًا للصفر، ثم يؤدي طرحها من \(p(n)\) إلى عدد التقسيمات الرابحة في ذلك النظام.
وفي النهاية يجمع البرنامج المساهمات الثلاث وفق
$$F_2(n)+F_3(n)+(n-3)F_4(n)\pmod{10^9+7}.$$
كما يفحص قبل إخراج النتيجة النهائية عند \(n=200\) قيم تحقق صغيرة مثل \(F_2(5)=3\) و\(F_3(5)=5\) و\(g(7)=66\) و\(g(10)=291\).
ليكن \(n\) هو المجموع المستهدف، ولتكن \(X=256\) هي سعة فضاء حالات XOR. حساب أعداد التقسيمات المعتادة يكلف \(O(n^2)\) زمنًا. أما جدولا \(k=2\) و\(k\ge4\) فيبنيان خطيًا، بينما تكلف العلاقة العودية المباشرة لـ mex في حالة \(k=3\) زمنًا مقداره \(O(n^3)\)، لأن كل حجم كومة يفحص جميع الانقسامات إلى جزأين وثلاثة أجزاء. وكل برمجة ديناميكية للتقسيمات مع XOR تكلف \(O(n^2X)\) زمنًا و\(O(nX)\) ذاكرة، ويتم تنفيذها لثلاثة أنظمة. ومن ثم فالتعقيد الكلي يساوي
$$O(n^3+n^2X),\qquad O(nX).$$
أي إن الزمن \(O(n^3+n^2X)\) والذاكرة \(O(nX)\)، وهو أمر عملي تمامًا عندما \(n=200\).