Problem Summary

Problem 1000 is a milestone problem that bundles three independent sub-problems whose answers are then fed into a single meta-recurrence. The final answer is one residue modulo $p=10^9+7$.

The three sub-problems are:

Max-And $I(n)$. Partition $\{1,2,\dots,n\}$ into two groups $A$ and $B$. Score a partition by $\sum_{a\in A,\,b\in B}(a \mathbin{\&} b)$, the sum of the bitwise AND over every cross pair. $I(n)$ is the maximum score. We are told $I(10)=50$ and must find $I(1000)$.
Max-Xor $X(N)$. For integers write $[x,y]=x^2\oplus y^2$ (the XOR of the squares). Consider sequences $a_0,a_1,\dots,a_r$ with $1\le a_i\le N$ whose consecutive weights strictly increase, $[a_{i-1},a_i]\lt [a_i,a_{i+1}]$. $X(N)$ is the maximum possible value of $\sum_i [a_{i-1},a_i]$. We are told $X(4)=71$ and $X(10)=702$, and must find $X(1000)$.
Unreachable Nim $C(N)$. In three-pile Nim a status $(a,b,c)$ is unreachable if it can only ever occur as a starting position. $C(N)$ counts unreachable statuses with $0\le a,b,c\lt N$. We are told $C(10)=123$ and must find $C(1000)$.

The meta-recurrence $M$ is then defined by

$$M(0)=I(1000),\quad M(1)=X(1000),\quad M(2)=C(1000),$$

$$M(k)=M(k-1)\,M(k-2)\,M(k-3)\pmod{p}\quad(k\ge 3),$$

with the checkpoint $M(4)\equiv 457587170 \pmod p$. The required answer is $M(1000)\bmod p$.

None of the three sub-problems is solved by brute force at $n=1000$; each collapses to a structural formula or a small dynamic program. The brute-force routines in the code exist only to validate the fast ones on small inputs.

Mathematical Approach

Sub-problem $I(n)$: a bitwise maximum cut

The bitwise AND distributes over bits. Writing the $k$-th bit of an integer $x$ as $x_k\in\{0,1\}$,

$$a \mathbin{\&} b=\sum_{k\ge0}2^k\,a_k b_k.$$

Summing over all cross pairs and exchanging the order of summation, the score depends on the bits only through how many elements on each side carry each bit:

$$\sum_{a\in A,\,b\in B}(a\mathbin{\&} b)=\sum_{k\ge0}2^k\Big(\sum_{a\in A}a_k\Big)\Big(\sum_{b\in B}b_k\Big)=\sum_{k\ge0}2^k\,x_k\,y_k,$$

where $x_k$ and $y_k$ count the elements of $A$ and $B$ having bit $k$ set. Let

$$m_k=\#\{1\le v\le n : v_k=1\}=x_k+y_k$$

be the total number of integers in $[1,n]$ whose bit $k$ is set. This total is fixed by $n$; only its split $(x_k,y_k)$ depends on the partition.

For each bit independently, $x_k y_k$ is maximized under $x_k+y_k=m_k$ by the most balanced split, giving $\big\lfloor m_k^2/4\big\rfloor$. Hence we always have the upper bound

$$I(n)\le U(n):=\sum_{k\ge0}2^k\left\lfloor\frac{m_k^2}{4}\right\rfloor.$$

The subtlety is that one single partition must balance every bit at once. The construction that does so is to colour each integer by the parity of its population count: put $v$ in $A$ when $\operatorname{popcount}(v)$ is even and in $B$ when it is odd. For a fixed bit $k$, let

$$s_k=\#\{v_k=1,\ \operatorname{popcount}(v)\text{ even}\}-\#\{v_k=1,\ \operatorname{popcount}(v)\text{ odd}\}$$

be the signed discrepancy. Then $x_k=(m_k+s_k)/2$, $y_k=(m_k-s_k)/2$, and the achieved value of bit $k$ is

$$x_k y_k=\frac{m_k^2-s_k^2}{4}.$$

This matches the optimum $\lfloor m_k^2/4\rfloor$ exactly when $|s_k|=m_k\bmod 2$, i.e. the parity colouring balances the integers carrying bit $k$ to within a single element. That is indeed the case: among the integers in $[1,n]$ with bit $k$ set, toggling the lowest bit different from $k$ is an involution that flips the population-count parity while staying inside the range, so it matches even-parity elements with odd-parity ones up to at most one leftover. Therefore $s_k=0$ when $m_k$ is even and $s_k=\pm1$ when $m_k$ is odd, and the parity partition is simultaneously optimal on every bit:

$$\boxed{\,I(n)=\sum_{k\ge0}2^k\left\lfloor\frac{m_k^2}{4}\right\rfloor\,}.$$

The code computes both $U(n)$ (the per-bit optimum) and the value achieved by the explicit parity partition, and asserts they are equal — turning the optimality proof into a runtime check.

Worked example $I(10)=50$. The bit totals over $\{1,\dots,10\}$ are $m_0=5$ (odd numbers $1,3,5,7,9$), $m_1=5$ ($2,3,6,7,10$), $m_2=4$ ($4,5,6,7$), $m_3=3$ ($8,9,10$). Hence

$$I(10)=1\!\cdot\!\Big\lfloor\tfrac{25}{4}\Big\rfloor+2\!\cdot\!\Big\lfloor\tfrac{25}{4}\Big\rfloor+4\!\cdot\!\Big\lfloor\tfrac{16}{4}\Big\rfloor+8\!\cdot\!\Big\lfloor\tfrac{9}{4}\Big\rfloor=6+12+16+16=50.$$

Sub-problem $X(N)$: a longest increasing-weight walk

Place a vertex at each integer $1,\dots,N$ and give the (undirected) edge between $u$ and $v$ the weight

$$w(u,v)=u^2\oplus v^2.$$

A valid sequence $a_0,a_1,\dots,a_r$ is a walk $a_0\to a_1\to\cdots\to a_r$ whose consecutive edge weights are strictly increasing, and $X(N)$ is the maximum total weight of such a walk. This is the classic longest path under increasing edge weights, which is solvable greedily by processing edges in nondecreasing weight order.

Maintain $\textit{best}[v]$ = the largest total weight of a valid (strictly increasing) walk that ends at vertex $v$; initialise all entries to $0$ (an empty walk). Sort all directed edges by weight and sweep through them. For an edge $u\to v$ of weight $w$, a walk ending at $u$ with all weights $\lt w$ can be extended by this edge, giving the candidate $\textit{best}[u]+w$. To honour the strict inequality, all edges sharing the same weight $w$ must be handled as one batch: every candidate in the batch is computed from the $\textit{best}$ values before the batch, and only after the whole batch is scored are the $\textit{best}$ entries updated. This prevents two equal-weight edges from chaining inside one walk. The answer is the maximum candidate seen over the whole sweep:

$$X(N)=\max_{\text{edges }u\to v}\big(\textit{best}[u]+w(u,v)\big).$$

Correctness. In any valid walk the weights strictly increase, so when an edge of weight $w$ is processed every lighter edge has already been relaxed and $\textit{best}[u]$ already reflects the best walk into $u$ using only weights $\lt w$. Batching equal weights guarantees no walk uses two edges of the same weight consecutively, which is exactly the strict-increase condition. The published checkpoints $X(4)=71$ and $X(10)=702$ are reproduced by this sweep.

Sub-problem $C(N)$: unreachable Nim positions by digit DP

In normal-play Nim each move strictly decreases exactly one pile. Recall the Sprague–Grundy / Bouton theory: a position is a losing $P$-position exactly when the nim-sum $s=a\oplus b\oplus c$ is $0$; otherwise it is a winning $N$-position and the winning move sends it to a $P$-position. Under optimal play the visited positions therefore alternate $N,P,N,P,\dots$

Fix an $N$-position $(a,b,c)$ with nim-sum $s\ne0$ and let $\beta$ be the highest set bit of $s$. Suppose it is reached as the result of a move out of a $P$-position $(x,y,z)$ (so $x\oplus y\oplus z=0$) by reducing one pile, say $z\to z'\lt z$. The new nim-sum is $z\oplus z'$, whose top bit is the highest bit where $z$ and $z'$ differ; since $z'\lt z$, that pile $z'$ does not carry bit $\beta$. So any $N$-position that can follow a $P$-position has at least one pile lacking bit $\beta$. Contrapositively:

$$\big(a,b,c\big)\text{ is unreachable }\iff s\ne0\ \text{ and bit }\beta\text{ is set in all of }a,b,c.$$

(If some pile lacks bit $\beta$, one can raise that pile to the XOR of the other two — a strictly larger value, since the missing top bit forces it up — producing a genuine $P$-position predecessor, so the position does occur mid-game.) Hence

$$C(N)=\#\Big\{(a,b,c)\in[0,N)^3 : s=a\oplus b\oplus c\ne0,\ a_\beta=b_\beta=c_\beta=1,\ \beta=\text{top bit of }s\Big\}.$$

This is counted with a bitwise digit DP. Enumerate the candidate top bit $\beta$. For a triple to contribute with this $\beta$:

at every bit above $\beta$, the three bits must XOR to $0$ (so $s$ has no set bit above $\beta$);
at bit $\beta$ all three bits are $1$ (so $s$ has bit $\beta$, it is the top bit, and all piles carry it);
at every bit below $\beta$ the bits are free.

Each pile must additionally satisfy $a,b,c\le N-1$. The DP scans bits from most to least significant carrying a $3$-bit mask recording which of the three piles is still tight (equal so far to the prefix of $N-1$); a tight pile may not exceed the corresponding bit of $N-1$, and stays tight only while it matches. Summing the surviving counts over all $\beta$ gives $C(N)$; the code checks the published value $C(10)=123$ and cross-checks the DP against the triple loop for all $n\le20$.

The meta-recurrence $M$

With the three answers in hand, the seeds are $M(0)=I(1000)$, $M(1)=X(1000)$, $M(2)=C(1000)$, and

$$M(k)\equiv M(k-1)\,M(k-2)\,M(k-3)\pmod{p},\qquad p=10^9+7.$$

Because every term is taken modulo the prime $p$, each step is just two modular multiplications, and reaching $k=1000$ costs only about a thousand multiplications. The code slides a window of the last three values forward, reducing modulo $p$ at each step. The intermediate checkpoint $M(4)\equiv457587170$ guards the chain, and the final output is $M(1000)\bmod p$.

How the Code Works

The C++, Python, and Java implementations follow the same pipeline. Helper routines parity_sign (population-count parity via repeated $v \mathbin{\&}(v-1)$), bit_count, and highest_bit provide the bit utilities.

parity_and_candidate sweeps $1\le v\le n$, accumulating for each bit the total $m_k$ and the signed parity discrepancy $s_k$; it returns both $U(n)=\sum2^k\lfloor m_k^2/4\rfloor$ and the parity-partition value $\sum2^k(m_k^2-s_k^2)/4$. max_and_value asserts these are equal, which is the runtime certificate that the parity partition is optimal, and returns $I(n)$. brute_max_and verifies $I(10)=50$ by trying all $2^{10}$ partitions.

max_xor_sum tabulates the squares, builds every directed edge $(u^2\oplus v^2,\,u,\,v)$, sorts by weight, and runs the batched longest-increasing-weight DP described above, returning $X(n)$.

count_unreachable_nim runs the digit DP: an outer loop over the top bit $\beta$, an inner descent over bits maintaining the $8$-state tightness mask, applying the "XOR to zero above $\beta$", "all ones at $\beta$", and "free below $\beta$" rules together with the $\le N-1$ bound. brute_unreachable_nim recomputes $C(n)$ directly for the cross-check.

mul_mod multiplies modulo $p$ (the C++ version widens to $128$ bits; Java keeps the product inside $64$ bits because both factors are already $\lt p$); meta_value iterates the triple-product recurrence. run_checkpoints asserts $I(10)=50$, $X(4)=71$, $X(10)=702$, $C(n)=$brute for $n\le20$, and $C(10)=123$; main then verifies $M(4)\equiv457587170$ before printing $M(1000)\bmod p$.

Complexity Analysis

$I(n)$: tabulating the bit totals costs $O(n\log n)$ (each of $n$ integers contributes to $O(\log n)$ bits), and combining them is $O(\log n)$; memory is $O(\log n)$.

$X(N)$: the graph has $\Theta(N^2)$ directed edges, so building and sorting them dominates at $O(N^2\log N)$ time and $O(N^2)$ memory. This is the most expensive stage; for $N=1000$ it is on the order of a million edges, completed in well under a second.

$C(N)$: the digit DP has $O(\log N)$ choices of $\beta$, each an $O(\log N)$ descent over a constant $8\times 8$ state space, so $O(\log^2 N)$ time and $O(1)$ memory.

Meta-recurrence: $O(k)$ modular multiplications, i.e. $O(1000)$ here. The overall running time is therefore governed by the $\Theta(N^2\log N)$ of the Max-Xor stage.

Footnotes and References

Problem page: Project Euler 1000
Maximum cut: Wikipedia - Maximum cut
Bitwise operation (AND / XOR): Wikipedia - Bitwise operation
Hamming weight (population count): Wikipedia - Hamming weight
Nim and the Bouton / Sprague–Grundy theory: Wikipedia - Nim
Longest path problem (DAG / edge ordering): Wikipedia - Longest path problem
Modular arithmetic: Wikipedia - Modular arithmetic

Problemzusammenfassung

Problem 1000 ist ein Meilenstein-Problem, das drei unabhängige Teilprobleme bündelt, deren Antworten dann in eine einzige Meta-Rekurrenz eingespeist werden. Die endgültige Antwort ist ein Rest modulo $p=10^9+7$.

Die drei Teilprobleme sind:

Max-And $I(n)$. Zerlege $\{1,2,\dots,n\}$ in zwei Gruppen $A$ und $B$. Bewerte eine Zerlegung durch $\sum_{a\in A,\,b\in B}(a \mathbin{\&} b)$, die Summe des bitweisen UND über jedes Kreuzpaar. $I(n)$ ist die maximale Bewertung. Es ist uns gegeben, dass $I(10)=50$, und wir müssen $I(1000)$ finden.
Max-Xor $X(N)$. Für ganze Zahlen schreibe $[x,y]=x^2\oplus y^2$ (das XOR der Quadrate). Betrachte Folgen $a_0,a_1,\dots,a_r$ mit $1\le a_i\le N$, deren aufeinanderfolgende Gewichte streng zunehmen, $[a_{i-1},a_i]\lt [a_i,a_{i+1}]$. $X(N)$ ist der maximal mögliche Wert von $\sum_i [a_{i-1},a_i]$. Es ist uns gegeben, dass $X(4)=71$ und $X(10)=702$, und wir müssen $X(1000)$ finden.
Unerreichbares Nim $C(N)$. Beim Drei-Haufen-Nim ist ein Zustand $(a,b,c)$ unerreichbar, wenn er nur jemals als Startposition auftreten kann. $C(N)$ zählt unerreichbare Zustände mit $0\le a,b,c\lt N$. Es ist uns gegeben, dass $C(10)=123$, und wir müssen $C(1000)$ finden.

Die Meta-Rekurrenz $M$ wird dann definiert durch

$$M(0)=I(1000),\quad M(1)=X(1000),\quad M(2)=C(1000),$$

$$M(k)=M(k-1)\,M(k-2)\,M(k-3)\pmod{p}\quad(k\ge 3),$$

mit dem Kontrollpunkt $M(4)\equiv 457587170 \pmod p$. Die gesuchte Antwort ist $M(1000)\bmod p$.

Keines der drei Teilprobleme wird bei $n=1000$ durch Brute Force gelöst; jedes reduziert sich auf eine strukturelle Formel oder ein kleines dynamisches Programm. Die Brute-Force-Routinen im Code existieren nur, um die schnellen Verfahren bei kleinen Eingaben zu validieren.

Mathematischer Ansatz

Teilproblem $I(n)$: ein bitweiser maximaler Schnitt

Das bitweise UND verteilt sich über die Bits. Wenn man das $k$-te Bit einer ganzen Zahl $x$ als $x_k\in\{0,1\}$ schreibt,

$$a \mathbin{\&} b=\sum_{k\ge0}2^k\,a_k b_k.$$

Summiert man über alle Kreuzpaare und vertauscht die Summationsreihenfolge, so hängt die Bewertung von den Bits nur darüber ab, wie viele Elemente auf jeder Seite jedes Bit tragen:

$$\sum_{a\in A,\,b\in B}(a\mathbin{\&} b)=\sum_{k\ge0}2^k\Big(\sum_{a\in A}a_k\Big)\Big(\sum_{b\in B}b_k\Big)=\sum_{k\ge0}2^k\,x_k\,y_k,$$

wobei $x_k$ und $y_k$ die Elemente von $A$ und $B$ zählen, bei denen Bit $k$ gesetzt ist. Sei

$$m_k=\#\{1\le v\le n : v_k=1\}=x_k+y_k$$

die Gesamtzahl der ganzen Zahlen in $[1,n]$, deren Bit $k$ gesetzt ist. Diese Gesamtzahl ist durch $n$ festgelegt; nur ihre Aufteilung $(x_k,y_k)$ hängt von der Zerlegung ab.

Für jedes Bit unabhängig wird $x_k y_k$ unter $x_k+y_k=m_k$ durch die ausgewogenste Aufteilung maximiert, was $\big\lfloor m_k^2/4\big\rfloor$ ergibt. Daher haben wir stets die obere Schranke

$$I(n)\le U(n):=\sum_{k\ge0}2^k\left\lfloor\frac{m_k^2}{4}\right\rfloor.$$

Die Feinheit besteht darin, dass eine einzige Zerlegung jedes Bit gleichzeitig ausbalancieren muss. Die Konstruktion, die dies leistet, besteht darin, jede ganze Zahl nach der Parität ihrer Bevölkerungszahl (Population Count) zu färben: $v$ kommt nach $A$, wenn $\operatorname{popcount}(v)$ gerade ist, und nach $B$, wenn sie ungerade ist. Für ein festes Bit $k$ sei

$$s_k=\#\{v_k=1,\ \operatorname{popcount}(v)\text{ even}\}-\#\{v_k=1,\ \operatorname{popcount}(v)\text{ odd}\}$$

die vorzeichenbehaftete Diskrepanz. Dann ist $x_k=(m_k+s_k)/2$, $y_k=(m_k-s_k)/2$, und der erreichte Wert von Bit $k$ ist

$$x_k y_k=\frac{m_k^2-s_k^2}{4}.$$

Dies stimmt genau dann mit dem Optimum $\lfloor m_k^2/4\rfloor$ überein, wenn $|s_k|=m_k\bmod 2$, d.h. die Paritätsfärbung balanciert die ganzen Zahlen, die Bit $k$ tragen, bis auf ein einzelnes Element aus. Das ist tatsächlich der Fall: Unter den ganzen Zahlen in $[1,n]$ mit gesetztem Bit $k$ ist das Umschalten des niedrigsten von $k$ verschiedenen Bits eine Involution, die die Parität der Bevölkerungszahl umkehrt, während sie innerhalb des Bereichs bleibt; sie paart also Elemente gerader Parität mit solchen ungerader Parität bis auf höchstens ein übrig bleibendes. Daher ist $s_k=0$, wenn $m_k$ gerade ist, und $s_k=\pm1$, wenn $m_k$ ungerade ist, und die Paritätszerlegung ist auf jedem Bit gleichzeitig optimal:

$$\boxed{\,I(n)=\sum_{k\ge0}2^k\left\lfloor\frac{m_k^2}{4}\right\rfloor\,}.$$

Der Code berechnet sowohl $U(n)$ (das Optimum pro Bit) als auch den Wert, der durch die explizite Paritätszerlegung erreicht wird, und versichert, dass sie gleich sind — und verwandelt damit den Optimalitätsbeweis in eine Laufzeitprüfung.

Durchgerechnetes Beispiel $I(10)=50$. Die Bit-Summen über $\{1,\dots,10\}$ sind $m_0=5$ (ungerade Zahlen $1,3,5,7,9$), $m_1=5$ ($2,3,6,7,10$), $m_2=4$ ($4,5,6,7$), $m_3=3$ ($8,9,10$). Daher

Teilproblem $X(N)$: ein längster Weg mit zunehmenden Gewichten

Platziere einen Knoten an jeder ganzen Zahl $1,\dots,N$ und gib der (ungerichteten) Kante zwischen $u$ und $v$ das Gewicht

$$w(u,v)=u^2\oplus v^2.$$

Eine gültige Folge $a_0,a_1,\dots,a_r$ ist ein Weg $a_0\to a_1\to\cdots\to a_r$, dessen aufeinanderfolgende Kantengewichte streng zunehmen, und $X(N)$ ist das maximale Gesamtgewicht eines solchen Weges. Dies ist der klassische längste Weg unter zunehmenden Kantengewichten, der sich gierig lösen lässt, indem man die Kanten in nichtfallender Gewichtsreihenfolge verarbeitet.

Halte $\textit{best}[v]$ = das größte Gesamtgewicht eines gültigen (streng zunehmenden) Weges, der am Knoten $v$ endet, aufrecht; initialisiere alle Einträge mit $0$ (ein leerer Weg). Sortiere alle gerichteten Kanten nach Gewicht und durchlaufe sie. Für eine Kante $u\to v$ mit Gewicht $w$ kann ein Weg, der bei $u$ mit allen Gewichten $\lt w$ endet, um diese Kante verlängert werden, was den Kandidaten $\textit{best}[u]+w$ ergibt. Um die strenge Ungleichung zu wahren, müssen alle Kanten mit demselben Gewicht $w$ als ein Stapel behandelt werden: Jeder Kandidat im Stapel wird aus den $\textit{best}$-Werten vor dem Stapel berechnet, und erst nachdem der gesamte Stapel bewertet wurde, werden die $\textit{best}$-Einträge aktualisiert. Dies verhindert, dass zwei gleichgewichtige Kanten innerhalb eines Weges verkettet werden. Die Antwort ist der maximale Kandidat, der über den gesamten Durchlauf gesehen wird:

$$X(N)=\max_{\text{edges }u\to v}\big(\textit{best}[u]+w(u,v)\big).$$

Korrektheit. In jedem gültigen Weg nehmen die Gewichte streng zu, sodass bei der Verarbeitung einer Kante mit Gewicht $w$ jede leichtere Kante bereits relaxiert wurde und $\textit{best}[u]$ bereits den besten Weg nach $u$ widerspiegelt, der nur Gewichte $\lt w$ verwendet. Das Stapeln gleicher Gewichte garantiert, dass kein Weg zwei Kanten desselben Gewichts nacheinander verwendet, was genau die Bedingung der strengen Zunahme ist. Die veröffentlichten Kontrollpunkte $X(4)=71$ und $X(10)=702$ werden durch diesen Durchlauf reproduziert.

Teilproblem $C(N)$: unerreichbare Nim-Positionen durch Ziffern-DP

Beim normalen Nim-Spiel verringert jeder Zug genau einen Haufen streng. Erinnere dich an die Sprague–Grundy- / Bouton-Theorie: Eine Position ist genau dann eine verlierende $P$-Position, wenn die Nim-Summe $s=a\oplus b\oplus c$ gleich $0$ ist; andernfalls ist sie eine gewinnende $N$-Position, und der Gewinnzug überführt sie in eine $P$-Position. Bei optimalem Spiel wechseln sich die besuchten Positionen daher als $N,P,N,P,\dots$ ab.

Fixiere eine $N$-Position $(a,b,c)$ mit Nim-Summe $s\ne0$ und sei $\beta$ das höchste gesetzte Bit von $s$. Angenommen, sie wird als Ergebnis eines Zuges aus einer $P$-Position $(x,y,z)$ (sodass $x\oplus y\oplus z=0$) erreicht, indem ein Haufen verringert wird, etwa $z\to z'\lt z$. Die neue Nim-Summe ist $z\oplus z'$, deren oberstes Bit das höchste Bit ist, in dem sich $z$ und $z'$ unterscheiden; da $z'\lt z$, trägt dieser Haufen $z'$ das Bit $\beta$ nicht. Also hat jede $N$-Position, die auf eine $P$-Position folgen kann, mindestens einen Haufen, dem das Bit $\beta$ fehlt. Kontrapositiv:

$$\big(a,b,c\big)\text{ is unreachable }\iff s\ne0\ \text{ and bit }\beta\text{ is set in all of }a,b,c.$$

(Fehlt einem Haufen das Bit $\beta$, so kann man diesen Haufen auf das XOR der anderen beiden anheben — einen streng größeren Wert, da das fehlende oberste Bit ihn nach oben zwingt — und so einen echten $P$-Positions-Vorgänger erzeugen; die Position tritt also mitten im Spiel auf.) Daher

$$C(N)=\#\Big\{(a,b,c)\in[0,N)^3 : s=a\oplus b\oplus c\ne0,\ a_\beta=b_\beta=c_\beta=1,\ \beta=\text{top bit of }s\Big\}.$$

Dies wird mit einem bitweisen Ziffern-DP gezählt. Zähle das mögliche oberste Bit $\beta$ auf. Damit ein Tripel mit diesem $\beta$ beiträgt:

bei jedem Bit oberhalb von $\beta$ müssen die drei Bits zu $0$ XOR-en (sodass $s$ kein gesetztes Bit oberhalb von $\beta$ hat);
bei Bit $\beta$ sind alle drei Bits $1$ (sodass $s$ das Bit $\beta$ hat, es das oberste Bit ist und alle Haufen es tragen);
bei jedem Bit unterhalb von $\beta$ sind die Bits frei.

Jeder Haufen muss zusätzlich $a,b,c\le N-1$ erfüllen. Das DP durchläuft die Bits vom höchstwertigen zum niedrigstwertigen und führt dabei eine $3$-Bit-Maske mit, die aufzeichnet, welcher der drei Haufen noch knapp ist (bisher gleich dem Präfix von $N-1$); ein knapper Haufen darf das entsprechende Bit von $N-1$ nicht überschreiten und bleibt nur knapp, solange er übereinstimmt. Die Summierung der überlebenden Zählungen über alle $\beta$ ergibt $C(N)$; der Code prüft den veröffentlichten Wert $C(10)=123$ und gleicht das DP für alle $n\le20$ mit der Tripelschleife ab.

Die Meta-Rekurrenz $M$

Mit den drei Antworten in der Hand sind die Startwerte $M(0)=I(1000)$, $M(1)=X(1000)$, $M(2)=C(1000)$, und

$$M(k)\equiv M(k-1)\,M(k-2)\,M(k-3)\pmod{p},\qquad p=10^9+7.$$

Da jeder Term modulo der Primzahl $p$ genommen wird, besteht jeder Schritt nur aus zwei modularen Multiplikationen, und das Erreichen von $k=1000$ kostet nur etwa tausend Multiplikationen. Der Code schiebt ein Fenster der letzten drei Werte vorwärts und reduziert bei jedem Schritt modulo $p$. Der zwischenliegende Kontrollpunkt $M(4)\equiv457587170$ sichert die Kette ab, und die endgültige Ausgabe ist $M(1000)\bmod p$.

Wie der Code arbeitet

Die C++-, Python- und Java-Implementierungen folgen derselben Pipeline. Hilfsroutinen parity_sign (Parität der Bevölkerungszahl über wiederholtes $v \mathbin{\&}(v-1)$), bit_count und highest_bit stellen die Bit-Hilfsmittel bereit.

parity_and_candidate durchläuft $1\le v\le n$ und akkumuliert für jedes Bit die Gesamtzahl $m_k$ und die vorzeichenbehaftete Paritätsdiskrepanz $s_k$; es gibt sowohl $U(n)=\sum2^k\lfloor m_k^2/4\rfloor$ als auch den Paritätszerlegungs-Wert $\sum2^k(m_k^2-s_k^2)/4$ zurück. max_and_value versichert, dass diese gleich sind, was das Laufzeit-Zertifikat dafür ist, dass die Paritätszerlegung optimal ist, und gibt $I(n)$ zurück. brute_max_and verifiziert $I(10)=50$, indem es alle $2^{10}$ Zerlegungen ausprobiert.

max_xor_sum tabelliert die Quadrate, baut jede gerichtete Kante $(u^2\oplus v^2,\,u,\,v)$, sortiert nach Gewicht und führt das oben beschriebene gestapelte DP für den längsten Weg mit zunehmenden Gewichten aus und gibt $X(n)$ zurück.

count_unreachable_nim führt das Ziffern-DP aus: eine äußere Schleife über das oberste Bit $\beta$, ein innerer Abstieg über die Bits, der die $8$-Zustands-Knappheitsmaske aufrechterhält und die Regeln „XOR zu Null oberhalb von $\beta$“, „alle Einsen bei $\beta$“ und „frei unterhalb von $\beta$“ zusammen mit der Schranke $\le N-1$ anwendet. brute_unreachable_nim berechnet $C(n)$ für den Abgleich direkt neu.

mul_mod multipliziert modulo $p$ (die C++-Version erweitert auf $128$ Bits; Java hält das Produkt innerhalb von $64$ Bits, da beide Faktoren bereits $\lt p$ sind); meta_value iteriert die Tripelprodukt-Rekurrenz. run_checkpoints versichert $I(10)=50$, $X(4)=71$, $X(10)=702$, $C(n)=$brute für $n\le20$ und $C(10)=123$; main verifiziert dann $M(4)\equiv457587170$, bevor es $M(1000)\bmod p$ ausgibt.

Komplexitätsanalyse

$I(n)$: Das Tabellieren der Bit-Summen kostet $O(n\log n)$ (jede der $n$ ganzen Zahlen trägt zu $O(\log n)$ Bits bei), und ihre Kombination ist $O(\log n)$; der Speicher ist $O(\log n)$.

$X(N)$: Der Graph hat $\Theta(N^2)$ gerichtete Kanten, sodass ihr Aufbau und ihre Sortierung mit $O(N^2\log N)$ Zeit und $O(N^2)$ Speicher dominieren. Dies ist die teuerste Phase; für $N=1000$ liegt sie in der Größenordnung von einer Million Kanten und ist deutlich unter einer Sekunde abgeschlossen.

$C(N)$: Das Ziffern-DP hat $O(\log N)$ Wahlmöglichkeiten für $\beta$, jede ein $O(\log N)$-Abstieg über einen konstanten $8\times 8$-Zustandsraum, also $O(\log^2 N)$ Zeit und $O(1)$ Speicher.

Meta-Rekurrenz: $O(k)$ modulare Multiplikationen, d.h. hier $O(1000)$. Die Gesamtlaufzeit wird daher durch das $\Theta(N^2\log N)$ der Max-Xor-Phase bestimmt.

Fußnoten und Referenzen

Problemseite: Project Euler 1000
Maximaler Schnitt: Wikipedia - Maximum cut
Bitweise Operation (UND / XOR): Wikipedia - Bitwise operation
Hamming-Gewicht (Bevölkerungszahl): Wikipedia - Hamming weight
Nim und die Bouton- / Sprague–Grundy-Theorie: Wikipedia - Nim
Längster-Weg-Problem (DAG / Kantenordnung): Wikipedia - Longest path problem
Modulare Arithmetik: Wikipedia - Modular arithmetic

Problem Özeti

Problem 1000, üç bağımsız alt problemi bir araya getiren bir kilometre taşı problemidir; bu alt problemlerin cevapları daha sonra tek bir meta-yinelemeye beslenir. Nihai cevap, $p=10^9+7$ modülünde tek bir kalandır.

Üç alt problem şunlardır:

Max-And $I(n)$. $\{1,2,\dots,n\}$ kümesini $A$ ve $B$ olmak üzere iki gruba ayırın. Bir ayrımı $\sum_{a\in A,\,b\in B}(a \mathbin{\&} b)$ ile, yani her çapraz çift üzerindeki bit düzeyinde AND'lerin toplamıyla puanlayın. $I(n)$, en yüksek puandır. Bize $I(10)=50$ verilmiştir ve $I(1000)$ değerini bulmamız gerekir.
Max-Xor $X(N)$. Tam sayılar için $[x,y]=x^2\oplus y^2$ (karelerin XOR'u) yazın. Ardışık ağırlıkları kesin olarak artan, $[a_{i-1},a_i]\lt [a_i,a_{i+1}]$ olacak şekilde $1\le a_i\le N$ ile $a_0,a_1,\dots,a_r$ dizilerini düşünün. $X(N)$, $\sum_i [a_{i-1},a_i]$ toplamının alabileceği en büyük değerdir. Bize $X(4)=71$ ve $X(10)=702$ verilmiştir ve $X(1000)$ değerini bulmamız gerekir.
Ulaşılamaz Nim $C(N)$. Üç yığınlı Nim'de bir durum $(a,b,c)$, yalnızca bir başlangıç konumu olarak ortaya çıkabiliyorsa ulaşılamazdır. $C(N)$, $0\le a,b,c\lt N$ olan ulaşılamaz durumları sayar. Bize $C(10)=123$ verilmiştir ve $C(1000)$ değerini bulmamız gerekir.

Meta-yineleme $M$ ardından şöyle tanımlanır:

$$M(0)=I(1000),\quad M(1)=X(1000),\quad M(2)=C(1000),$$

$$M(k)=M(k-1)\,M(k-2)\,M(k-3)\pmod{p}\quad(k\ge 3),$$

$M(4)\equiv 457587170 \pmod p$ kontrol noktası ile. İstenen cevap $M(1000)\bmod p$'dir.

Üç alt problemin hiçbiri $n=1000$'de kaba kuvvetle çözülmez; her biri yapısal bir formüle veya küçük bir dinamik programa indirgenir. Koddaki kaba kuvvet rutinleri yalnızca hızlı olanları küçük girdiler üzerinde doğrulamak için vardır.

Matematiksel Yaklaşım

Alt problem $I(n)$: bit düzeyinde bir maksimum kesim

Bit düzeyinde AND, bitler üzerinde dağılır. Bir $x$ tam sayısının $k$. bitini $x_k\in\{0,1\}$ olarak yazarsak,

$$a \mathbin{\&} b=\sum_{k\ge0}2^k\,a_k b_k.$$

Tüm çapraz çiftler üzerinde toplayıp toplama sırasını değiştirince, puan bitlere yalnızca her tarafta her bir biti taşıyan kaç eleman olduğu üzerinden bağlı olur:

$$\sum_{a\in A,\,b\in B}(a\mathbin{\&} b)=\sum_{k\ge0}2^k\Big(\sum_{a\in A}a_k\Big)\Big(\sum_{b\in B}b_k\Big)=\sum_{k\ge0}2^k\,x_k\,y_k,$$

burada $x_k$ ve $y_k$, $A$ ve $B$'nin $k$. biti set olan elemanlarını sayar. Şu şekilde tanımlayalım:

$$m_k=\#\{1\le v\le n : v_k=1\}=x_k+y_k$$

bu, $[1,n]$ aralığında $k$. biti set olan tam sayıların toplam sayısıdır. Bu toplam $n$ tarafından sabitlenir; yalnızca $(x_k,y_k)$ bölünmesi ayrıma bağlıdır.

Her bit için bağımsız olarak, $x_k+y_k=m_k$ altında $x_k y_k$ en dengeli bölünmeyle, yani $\big\lfloor m_k^2/4\big\rfloor$ vererek maksimize edilir. Dolayısıyla daima şu üst sınıra sahibiz:

$$I(n)\le U(n):=\sum_{k\ge0}2^k\left\lfloor\frac{m_k^2}{4}\right\rfloor.$$

İncelik şudur ki tek bir ayrımın her biti aynı anda dengelemesi gerekir. Bunu yapan yapı, her tam sayıyı nüfus sayımının (popülasyon sayısının) pariteliğine göre renklendirmektir: $\operatorname{popcount}(v)$ çift olduğunda $v$'yi $A$'ya, tek olduğunda $B$'ye koyun. Sabit bir $k$ biti için şu şekilde tanımlayalım:

$$s_k=\#\{v_k=1,\ \operatorname{popcount}(v)\text{ even}\}-\#\{v_k=1,\ \operatorname{popcount}(v)\text{ odd}\}$$

bu işaretli farktır. O zaman $x_k=(m_k+s_k)/2$, $y_k=(m_k-s_k)/2$ olur ve $k$ bitinin elde edilen değeri şudur:

$$x_k y_k=\frac{m_k^2-s_k^2}{4}.$$

Bu, $|s_k|=m_k\bmod 2$ olduğunda, yani parite renklendirmesi $k$ bitini taşıyan tam sayıları tek bir eleman içinde dengelediğinde, optimumla $\lfloor m_k^2/4\rfloor$ tam olarak eşleşir. Durum gerçekten de böyledir: $[1,n]$ aralığında $k$. biti set olan tam sayılar arasında, $k$'dan farklı en düşük biti çevirmek, aralık içinde kalırken nüfus sayımı paritesini ters çeviren bir involüsyondur, dolayısıyla çift parite elemanlarını tek parite olanlarla en fazla bir artık kalacak şekilde eşler. Bu nedenle $m_k$ çift olduğunda $s_k=0$ ve $m_k$ tek olduğunda $s_k=\pm1$ olur ve parite ayrımı her bit üzerinde aynı anda optimaldir:

$$\boxed{\,I(n)=\sum_{k\ge0}2^k\left\lfloor\frac{m_k^2}{4}\right\rfloor\,}.$$

Kod, hem $U(n)$'yi (bit başına optimum) hem de açık parite ayrımıyla elde edilen değeri hesaplar ve bunların eşit olduğunu öne sürer — optimallik kanıtını bir çalışma zamanı kontrolüne dönüştürür.

Çözümlü örnek $I(10)=50$. $\{1,\dots,10\}$ üzerindeki bit toplamları $m_0=5$ (tek sayılar $1,3,5,7,9$), $m_1=5$ ($2,3,6,7,10$), $m_2=4$ ($4,5,6,7$), $m_3=3$ ($8,9,10$)'dür. Dolayısıyla

Alt problem $X(N)$: en uzun artan ağırlıklı yürüyüş

Her $1,\dots,N$ tam sayısına bir köşe yerleştirin ve $u$ ile $v$ arasındaki (yönsüz) kenara şu ağırlığı verin:

$$w(u,v)=u^2\oplus v^2.$$

Geçerli bir $a_0,a_1,\dots,a_r$ dizisi, ardışık kenar ağırlıkları kesin olarak artan bir $a_0\to a_1\to\cdots\to a_r$ yürüyüşüdür ve $X(N)$, böyle bir yürüyüşün en büyük toplam ağırlığıdır. Bu, klasik artan kenar ağırlıkları altında en uzun yol problemidir ve kenarları artmayan ağırlık sırasında işleyerek açgözlü biçimde çözülebilir.

$\textit{best}[v]$ = $v$ köşesinde biten geçerli bir (kesin olarak artan) yürüyüşün en büyük toplam ağırlığı olarak tutun; tüm girişleri $0$ (boş bir yürüyüş) olarak başlatın. Tüm yönlü kenarları ağırlığa göre sıralayın ve üzerlerinden geçin. $w$ ağırlıklı bir $u\to v$ kenarı için, tüm ağırlıkları $\lt w$ olup $u$'da biten bir yürüyüş bu kenarla genişletilebilir ve $\textit{best}[u]+w$ adayını verir. Kesin eşitsizliğe uymak için, aynı $w$ ağırlığını paylaşan tüm kenarlar tek bir parti olarak ele alınmalıdır: partideki her aday, parti öncesindeki $\textit{best}$ değerlerinden hesaplanır ve yalnızca tüm parti puanlandıktan sonra $\textit{best}$ girişleri güncellenir. Bu, eşit ağırlıklı iki kenarın tek bir yürüyüş içinde zincirlenmesini engeller. Cevap, tüm tarama boyunca görülen en büyük adaydır:

$$X(N)=\max_{\text{edges }u\to v}\big(\textit{best}[u]+w(u,v)\big).$$

Doğruluk. Herhangi bir geçerli yürüyüşte ağırlıklar kesin olarak artar, dolayısıyla $w$ ağırlıklı bir kenar işlendiğinde her daha hafif kenar zaten gevşetilmiştir ve $\textit{best}[u]$ zaten yalnızca $\lt w$ ağırlıkları kullanarak $u$'ya giren en iyi yürüyüşü yansıtır. Eşit ağırlıkları partilemek, hiçbir yürüyüşün aynı ağırlıktan iki kenarı ardışık kullanmamasını garanti eder ki bu tam olarak kesin-artış koşuludur. Yayımlanmış kontrol noktaları $X(4)=71$ ve $X(10)=702$, bu taramayla yeniden üretilir.

Alt problem $C(N)$: basamak DP ile ulaşılamaz Nim konumları

Normal oyunlu Nim'de her hamle tam olarak bir yığını kesin olarak azaltır. Sprague–Grundy / Bouton teorisini hatırlayın: bir konum, tam olarak nim-toplamı $s=a\oplus b\oplus c$ sıfır $0$ olduğunda kaybeden bir $P$-konumudur; aksi takdirde kazanan bir $N$-konumudur ve kazanan hamle onu bir $P$-konumuna gönderir. Dolayısıyla optimal oyun altında ziyaret edilen konumlar $N,P,N,P,\dots$ şeklinde dönüşümlü olur.

Nim-toplamı $s\ne0$ olan bir $N$-konumu $(a,b,c)$ sabitleyin ve $\beta$, $s$'nin en yüksek set biti olsun. Bunun bir $P$-konumu $(x,y,z)$'den (yani $x\oplus y\oplus z=0$) bir yığını azaltarak, diyelim $z\to z'\lt z$, yapılan bir hamlenin sonucu olarak ulaşıldığını varsayalım. Yeni nim-toplamı $z\oplus z'$'dir, en üst biti $z$ ile $z'$'nin farklı olduğu en yüksek bittir; $z'\lt z$ olduğundan, o $z'$ yığını $\beta$ bitini taşımaz. Dolayısıyla bir $P$-konumunu takip edebilen herhangi bir $N$-konumunun $\beta$ bitinden yoksun en az bir yığını vardır. Karşıt-tersi olarak:

$$\big(a,b,c\big)\text{ is unreachable }\iff s\ne0\ \text{ and bit }\beta\text{ is set in all of }a,b,c.$$

(Bir yığın $\beta$ bitinden yoksunsa, o yığını diğer ikisinin XOR'una yükseltebilir — eksik en üst bit onu yukarı zorladığından, kesin olarak daha büyük bir değer — gerçek bir $P$-konumu öncülü üreterek, böylece konum oyun ortasında ortaya çıkar.) Dolayısıyla

$$C(N)=\#\Big\{(a,b,c)\in[0,N)^3 : s=a\oplus b\oplus c\ne0,\ a_\beta=b_\beta=c_\beta=1,\ \beta=\text{top bit of }s\Big\}.$$

Bu, bit düzeyinde bir basamak DP ile sayılır. Aday en üst bit $\beta$'yı sıralayın. Bir üçlünün bu $\beta$ ile katkıda bulunması için:

$\beta$'nın üstündeki her bitte, üç bitin XOR'u $0$ olmalıdır (böylece $s$'nin $\beta$'nın üstünde set biti yoktur);
$\beta$ bitinde üç bitin hepsi $1$'dir (böylece $s$'nin $\beta$ biti vardır, bu en üst bittir ve tüm yığınlar onu taşır);
$\beta$'nın altındaki her bitte bitler serbesttir.

Her yığın ayrıca $a,b,c\le N-1$ koşulunu sağlamalıdır. DP, bitleri en anlamlıdan en az anlamlıya doğru tarar ve hangi üç yığından hangisinin hâlâ sıkı (şimdiye kadar $N-1$'in önekiyle eşit) olduğunu kaydeden bir $3$-bitlik maske taşır; sıkı bir yığın $N-1$'in karşılık gelen bitini aşamaz ve yalnızca eşleştiği sürece sıkı kalır. Hayatta kalan sayıları tüm $\beta$ değerleri üzerinde toplamak $C(N)$'yi verir; kod yayımlanmış değer $C(10)=123$'ü kontrol eder ve DP'yi tüm $n\le20$ için üçlü döngüye karşı çapraz kontrol eder.

Meta-yineleme $M$

Üç cevap elde edildiğinde, başlangıç değerleri $M(0)=I(1000)$, $M(1)=X(1000)$, $M(2)=C(1000)$'dir ve

$$M(k)\equiv M(k-1)\,M(k-2)\,M(k-3)\pmod{p},\qquad p=10^9+7.$$

Her terim $p$ asalı modülünde alındığından, her adım yalnızca iki modüler çarpmadır ve $k=1000$'e ulaşmak yalnızca yaklaşık bin çarpmaya mal olur. Kod, son üç değerin penceresini ileri kaydırır ve her adımda $p$ modülünde indirger. Ara kontrol noktası $M(4)\equiv457587170$ zinciri korur ve nihai çıktı $M(1000)\bmod p$'dir.

Kod Nasıl Çalışır

C++, Python ve Java uygulamaları aynı boru hattını izler. Yardımcı rutinler parity_sign (tekrarlı $v \mathbin{\&}(v-1)$ ile nüfus sayımı paritesi), bit_count ve highest_bit bit yardımcılarını sağlar.

parity_and_candidate, $1\le v\le n$ boyunca tarar, her bit için toplam $m_k$'yi ve işaretli parite farkı $s_k$'yi biriktirir; hem $U(n)=\sum2^k\lfloor m_k^2/4\rfloor$'yi hem de parite-ayrımı değeri $\sum2^k(m_k^2-s_k^2)/4$'yi döndürür. max_and_value, bunların eşit olduğunu öne sürer; bu, parite ayrımının optimal olduğunun çalışma zamanı sertifikasıdır ve $I(n)$'yi döndürür. brute_max_and, tüm $2^{10}$ ayrımı deneyerek $I(10)=50$'yi doğrular.

max_xor_sum, kareleri tablolar, her yönlü kenarı $(u^2\oplus v^2,\,u,\,v)$ oluşturur, ağırlığa göre sıralar ve yukarıda açıklanan partili en-uzun-artan-ağırlık DP'sini çalıştırarak $X(n)$'yi döndürür.

count_unreachable_nim, basamak DP'sini çalıştırır: en üst bit $\beta$ üzerinde bir dış döngü, $8$ durumlu sıkılık maskesini koruyan bitler üzerinde bir iç iniş, $\beta$'nın "üstünde XOR sıfır", "$\beta$'da hepsi bir" ve "$\beta$'nın altında serbest" kurallarını $\le N-1$ sınırıyla birlikte uygular. brute_unreachable_nim, çapraz kontrol için $C(n)$'yi doğrudan yeniden hesaplar.

mul_mod, $p$ modülünde çarpar (C++ sürümü $128$ bite genişletir; Java, her iki çarpan zaten $\lt p$ olduğundan çarpımı $64$ bit içinde tutar); meta_value, üçlü-çarpım yinelemesini yineler. run_checkpoints, $I(10)=50$, $X(4)=71$, $X(10)=702$, $n\le20$ için $C(n)=$brute ve $C(10)=123$ olduğunu öne sürer; main ardından $M(1000)\bmod p$'yi yazdırmadan önce $M(4)\equiv457587170$'i doğrular.

Karmaşıklık Analizi

$I(n)$: bit toplamlarının tablolanması $O(n\log n)$ maliyetindedir (her bir $n$ tam sayısı $O(\log n)$ bite katkıda bulunur) ve bunların birleştirilmesi $O(\log n)$'dir; bellek $O(\log n)$'dir.

$X(N)$: grafın $\Theta(N^2)$ yönlü kenarı vardır, dolayısıyla bunların oluşturulması ve sıralanması $O(N^2\log N)$ zaman ve $O(N^2)$ bellekle baskındır. Bu en pahalı aşamadır; $N=1000$ için bir milyon kenar mertebesindedir ve bir saniyenin çok altında tamamlanır.

$C(N)$: basamak DP'sinin $O(\log N)$ $\beta$ seçeneği vardır, her biri sabit bir $8\times 8$ durum uzayı üzerinde $O(\log N)$ iniştir, dolayısıyla $O(\log^2 N)$ zaman ve $O(1)$ bellektir.

Meta-yineleme: $O(k)$ modüler çarpma, yani burada $O(1000)$. Genel çalışma süresi bu nedenle Max-Xor aşamasının $\Theta(N^2\log N)$'si tarafından belirlenir.

Dipnotlar ve Referanslar

Problem sayfası: Project Euler 1000
Maksimum kesim: Wikipedia - Maximum cut
Bit düzeyinde işlem (AND / XOR): Wikipedia - Bitwise operation
Hamming ağırlığı (nüfus sayımı): Wikipedia - Hamming weight
Nim ve Bouton / Sprague–Grundy teorisi: Wikipedia - Nim
En uzun yol problemi (DAG / kenar sıralaması): Wikipedia - Longest path problem
Modüler aritmetik: Wikipedia - Modular arithmetic

Resumen del Problema

El Problema 1000 es un problema hito que agrupa tres subproblemas independientes cuyas respuestas se introducen luego en una única meta-recurrencia. La respuesta final es un residuo módulo $p=10^9+7$.

Los tres subproblemas son:

Max-And $I(n)$. Particiona $\{1,2,\dots,n\}$ en dos grupos $A$ y $B$. Puntúa una partición mediante $\sum_{a\in A,\,b\in B}(a \mathbin{\&} b)$, la suma del AND bit a bit sobre cada par cruzado. $I(n)$ es la puntuación máxima. Se nos dice que $I(10)=50$ y debemos hallar $I(1000)$.
Max-Xor $X(N)$. Para enteros escribimos $[x,y]=x^2\oplus y^2$ (el XOR de los cuadrados). Considera sucesiones $a_0,a_1,\dots,a_r$ con $1\le a_i\le N$ cuyos pesos consecutivos crecen estrictamente, $[a_{i-1},a_i]\lt [a_i,a_{i+1}]$. $X(N)$ es el valor máximo posible de $\sum_i [a_{i-1},a_i]$. Se nos dice que $X(4)=71$ y $X(10)=702$, y debemos hallar $X(1000)$.
Nim inalcanzable $C(N)$. En el Nim de tres montones un estado $(a,b,c)$ es inalcanzable si solo puede aparecer como posición inicial. $C(N)$ cuenta los estados inalcanzables con $0\le a,b,c\lt N$. Se nos dice que $C(10)=123$ y debemos hallar $C(1000)$.

La meta-recurrencia $M$ se define entonces por

$$M(0)=I(1000),\quad M(1)=X(1000),\quad M(2)=C(1000),$$

$$M(k)=M(k-1)\,M(k-2)\,M(k-3)\pmod{p}\quad(k\ge 3),$$

con el punto de control $M(4)\equiv 457587170 \pmod p$. La respuesta requerida es $M(1000)\bmod p$.

Ninguno de los tres subproblemas se resuelve por fuerza bruta en $n=1000$; cada uno se reduce a una fórmula estructural o a un pequeño programa dinámico. Las rutinas de fuerza bruta del código existen únicamente para validar las rápidas con entradas pequeñas.

Enfoque Matemático

Subproblema $I(n)$: un corte máximo bit a bit

El AND bit a bit se distribuye sobre los bits. Escribiendo el $k$-ésimo bit de un entero $x$ como $x_k\in\{0,1\}$,

$$a \mathbin{\&} b=\sum_{k\ge0}2^k\,a_k b_k.$$

Sumando sobre todos los pares cruzados e intercambiando el orden de sumación, la puntuación depende de los bits solo a través de cuántos elementos de cada lado portan cada bit:

$$\sum_{a\in A,\,b\in B}(a\mathbin{\&} b)=\sum_{k\ge0}2^k\Big(\sum_{a\in A}a_k\Big)\Big(\sum_{b\in B}b_k\Big)=\sum_{k\ge0}2^k\,x_k\,y_k,$$

donde $x_k$ e $y_k$ cuentan los elementos de $A$ y $B$ que tienen el bit $k$ activado. Sea

$$m_k=\#\{1\le v\le n : v_k=1\}=x_k+y_k$$

el número total de enteros en $[1,n]$ cuyo bit $k$ está activado. Este total está fijado por $n$; solo su división $(x_k,y_k)$ depende de la partición.

Para cada bit por separado, $x_k y_k$ se maximiza bajo $x_k+y_k=m_k$ mediante la división más equilibrada, dando $\big\lfloor m_k^2/4\big\rfloor$. Por tanto siempre tenemos la cota superior

$$I(n)\le U(n):=\sum_{k\ge0}2^k\left\lfloor\frac{m_k^2}{4}\right\rfloor.$$

La sutileza es que una única partición debe equilibrar todos los bits a la vez. La construcción que lo logra consiste en colorear cada entero según la paridad de su recuento de población: poner $v$ en $A$ cuando $\operatorname{popcount}(v)$ es par y en $B$ cuando es impar. Para un bit fijo $k$, sea

$$s_k=\#\{v_k=1,\ \operatorname{popcount}(v)\text{ even}\}-\#\{v_k=1,\ \operatorname{popcount}(v)\text{ odd}\}$$

la discrepancia con signo. Entonces $x_k=(m_k+s_k)/2$, $y_k=(m_k-s_k)/2$, y el valor alcanzado del bit $k$ es

$$x_k y_k=\frac{m_k^2-s_k^2}{4}.$$

Esto coincide con el óptimo $\lfloor m_k^2/4\rfloor$ exactamente cuando $|s_k|=m_k\bmod 2$, es decir, cuando la coloración por paridad equilibra los enteros que portan el bit $k$ hasta un único elemento. Y ese es efectivamente el caso: entre los enteros en $[1,n]$ con el bit $k$ activado, alternar el bit más bajo distinto de $k$ es una involución que invierte la paridad del recuento de población permaneciendo dentro del rango, de modo que empareja elementos de paridad par con los de paridad impar salvo a lo sumo un sobrante. Por tanto $s_k=0$ cuando $m_k$ es par y $s_k=\pm1$ cuando $m_k$ es impar, y la partición por paridad es simultáneamente óptima en todos los bits:

$$\boxed{\,I(n)=\sum_{k\ge0}2^k\left\lfloor\frac{m_k^2}{4}\right\rfloor\,}.$$

El código calcula tanto $U(n)$ (el óptimo por bit) como el valor alcanzado por la partición por paridad explícita, y comprueba que son iguales, convirtiendo la demostración de optimalidad en una verificación en tiempo de ejecución.

Ejemplo resuelto $I(10)=50$. Los totales de bits sobre $\{1,\dots,10\}$ son $m_0=5$ (los números impares $1,3,5,7,9$), $m_1=5$ ($2,3,6,7,10$), $m_2=4$ ($4,5,6,7$), $m_3=3$ ($8,9,10$). Por tanto

Subproblema $X(N)$: un camino más largo con pesos crecientes

Coloca un vértice en cada entero $1,\dots,N$ y asigna a la arista (no dirigida) entre $u$ y $v$ el peso

$$w(u,v)=u^2\oplus v^2.$$

Una sucesión válida $a_0,a_1,\dots,a_r$ es un camino $a_0\to a_1\to\cdots\to a_r$ cuyos pesos de aristas consecutivas son estrictamente crecientes, y $X(N)$ es el peso total máximo de tal camino. Este es el clásico camino más largo con pesos de aristas crecientes, que se resuelve de forma voraz procesando las aristas en orden no decreciente de peso.

Mantén $\textit{best}[v]$ = el mayor peso total de un camino válido (estrictamente creciente) que termina en el vértice $v$; inicializa todas las entradas a $0$ (un camino vacío). Ordena todas las aristas dirigidas por peso y recórrelas. Para una arista $u\to v$ de peso $w$, un camino que termina en $u$ con todos los pesos $\lt w$ puede extenderse con esta arista, dando el candidato $\textit{best}[u]+w$. Para respetar la desigualdad estricta, todas las aristas que comparten el mismo peso $w$ deben tratarse como un solo lote: cada candidato del lote se calcula a partir de los valores $\textit{best}$ anteriores al lote, y solo después de puntuar todo el lote se actualizan las entradas $\textit{best}$. Esto impide que dos aristas de igual peso se encadenen dentro de un mismo camino. La respuesta es el candidato máximo visto durante todo el recorrido:

$$X(N)=\max_{\text{edges }u\to v}\big(\textit{best}[u]+w(u,v)\big).$$

Corrección. En cualquier camino válido los pesos crecen estrictamente, así que cuando se procesa una arista de peso $w$ toda arista más ligera ya ha sido relajada y $\textit{best}[u]$ ya refleja el mejor camino hacia $u$ usando únicamente pesos $\lt w$. Agrupar pesos iguales garantiza que ningún camino use dos aristas del mismo peso consecutivamente, que es exactamente la condición de crecimiento estricto. Los puntos de control publicados $X(4)=71$ y $X(10)=702$ se reproducen con este recorrido.

Subproblema $C(N)$: posiciones de Nim inalcanzables mediante DP por dígitos

En el juego normal de Nim cada movimiento disminuye estrictamente exactamente un montón. Recuerda la teoría de Sprague–Grundy / Bouton: una posición es una $P$-posición perdedora exactamente cuando la nim-suma $s=a\oplus b\oplus c$ es $0$; en caso contrario es una $N$-posición ganadora y el movimiento ganador la lleva a una $P$-posición. Bajo juego óptimo las posiciones visitadas alternan, por tanto, $N,P,N,P,\dots$

Fija una $N$-posición $(a,b,c)$ con nim-suma $s\ne0$ y sea $\beta$ el bit más alto activado de $s$. Supón que se alcanza como resultado de un movimiento que sale de una $P$-posición $(x,y,z)$ (de modo que $x\oplus y\oplus z=0$) reduciendo un montón, digamos $z\to z'\lt z$. La nueva nim-suma es $z\oplus z'$, cuyo bit superior es el bit más alto donde $z$ y $z'$ difieren; como $z'\lt z$, ese montón $z'$ no porta el bit $\beta$. De modo que cualquier $N$-posición que pueda seguir a una $P$-posición tiene al menos un montón al que le falta el bit $\beta$. Por contraposición:

$$\big(a,b,c\big)\text{ is unreachable }\iff s\ne0\ \text{ and bit }\beta\text{ is set in all of }a,b,c.$$

(Si a algún montón le falta el bit $\beta$, se puede elevar ese montón al XOR de los otros dos —un valor estrictamente mayor, ya que el bit superior ausente lo fuerza a subir— produciendo un predecesor genuino que es una $P$-posición, por lo que la posición sí ocurre a mitad de partida.) Por tanto

$$C(N)=\#\Big\{(a,b,c)\in[0,N)^3 : s=a\oplus b\oplus c\ne0,\ a_\beta=b_\beta=c_\beta=1,\ \beta=\text{top bit of }s\Big\}.$$

Esto se cuenta con una DP por dígitos bit a bit. Enumera el bit superior candidato $\beta$. Para que una terna contribuya con este $\beta$:

en cada bit por encima de $\beta$, los tres bits deben dar XOR $0$ (de modo que $s$ no tiene ningún bit activado por encima de $\beta$);
en el bit $\beta$ los tres bits son $1$ (de modo que $s$ tiene el bit $\beta$, este es el bit superior, y todos los montones lo portan);
en cada bit por debajo de $\beta$ los bits son libres.

Cada montón debe satisfacer además $a,b,c\le N-1$. La DP recorre los bits del más al menos significativo arrastrando una máscara de $3$ bits que registra cuáles de los tres montones siguen ajustados (iguales hasta ahora al prefijo de $N-1$); un montón ajustado no puede exceder el bit correspondiente de $N-1$, y permanece ajustado solo mientras coincide. Sumando los conteos supervivientes sobre todos los $\beta$ se obtiene $C(N)$; el código comprueba el valor publicado $C(10)=123$ y contrasta la DP con el bucle triple para todo $n\le20$.

La meta-recurrencia $M$

Con las tres respuestas en mano, las semillas son $M(0)=I(1000)$, $M(1)=X(1000)$, $M(2)=C(1000)$, y

$$M(k)\equiv M(k-1)\,M(k-2)\,M(k-3)\pmod{p},\qquad p=10^9+7.$$

Como cada término se toma módulo el primo $p$, cada paso son solo dos multiplicaciones modulares, y alcanzar $k=1000$ cuesta apenas unas mil multiplicaciones. El código desliza hacia adelante una ventana de los últimos tres valores, reduciendo módulo $p$ en cada paso. El punto de control intermedio $M(4)\equiv457587170$ protege la cadena, y la salida final es $M(1000)\bmod p$.

Cómo Funciona el Código

Las implementaciones en C++, Python y Java siguen la misma cadena de procesamiento. Las rutinas auxiliares parity_sign (paridad del recuento de población mediante $v \mathbin{\&}(v-1)$ repetido), bit_count y highest_bit proporcionan las utilidades de bits.

parity_and_candidate recorre $1\le v\le n$, acumulando para cada bit el total $m_k$ y la discrepancia de paridad con signo $s_k$; devuelve tanto $U(n)=\sum2^k\lfloor m_k^2/4\rfloor$ como el valor de la partición por paridad $\sum2^k(m_k^2-s_k^2)/4$. max_and_value comprueba que son iguales, lo cual es el certificado en tiempo de ejecución de que la partición por paridad es óptima, y devuelve $I(n)$. brute_max_and verifica $I(10)=50$ probando las $2^{10}$ particiones.

max_xor_sum tabula los cuadrados, construye cada arista dirigida $(u^2\oplus v^2,\,u,\,v)$, ordena por peso, y ejecuta la DP por lotes de camino más largo con pesos crecientes descrita arriba, devolviendo $X(n)$.

count_unreachable_nim ejecuta la DP por dígitos: un bucle externo sobre el bit superior $\beta$, un descenso interno sobre los bits manteniendo la máscara de ajuste de $8$ estados, aplicando las reglas de "XOR a cero por encima de $\beta$", "todos unos en $\beta$" y "libres por debajo de $\beta$" junto con la cota $\le N-1$. brute_unreachable_nim recalcula $C(n)$ directamente para el contraste.

mul_mod multiplica módulo $p$ (la versión de C++ se amplía a $128$ bits; Java mantiene el producto dentro de $64$ bits porque ambos factores ya son $\lt p$); meta_value itera la recurrencia del triple producto. run_checkpoints comprueba $I(10)=50$, $X(4)=71$, $X(10)=702$, $C(n)=$brute para $n\le20$, y $C(10)=123$; main verifica entonces $M(4)\equiv457587170$ antes de imprimir $M(1000)\bmod p$.

Análisis de Complejidad

$I(n)$: tabular los totales de bits cuesta $O(n\log n)$ (cada uno de los $n$ enteros contribuye a $O(\log n)$ bits), y combinarlos es $O(\log n)$; la memoria es $O(\log n)$.

$X(N)$: el grafo tiene $\Theta(N^2)$ aristas dirigidas, así que construirlas y ordenarlas domina con $O(N^2\log N)$ en tiempo y $O(N^2)$ en memoria. Esta es la etapa más costosa; para $N=1000$ es del orden de un millón de aristas, completada en bastante menos de un segundo.

$C(N)$: la DP por dígitos tiene $O(\log N)$ elecciones de $\beta$, cada una un descenso $O(\log N)$ sobre un espacio de estados constante de $8\times 8$, de modo que $O(\log^2 N)$ en tiempo y $O(1)$ en memoria.

Meta-recurrencia: $O(k)$ multiplicaciones modulares, es decir, $O(1000)$ aquí. El tiempo de ejecución global está gobernado, por tanto, por el $\Theta(N^2\log N)$ de la etapa Max-Xor.

Notas al pie y referencias

Página del problema: Project Euler 1000
Corte máximo: Wikipedia - Maximum cut
Operación bit a bit (AND / XOR): Wikipedia - Bitwise operation
Peso de Hamming (recuento de población): Wikipedia - Hamming weight
Nim y la teoría de Bouton / Sprague–Grundy: Wikipedia - Nim
Problema del camino más largo (DAG / ordenación de aristas): Wikipedia - Longest path problem
Aritmética modular: Wikipedia - Modular arithmetic

问题概述

问题 1000 是一道里程碑式的题目，它将三个相互独立的子问题打包在一起，再把它们的答案输入到同一个元递推中。最终答案是模 $p=10^9+7$ 的一个余数。

这三个子问题是：

Max-And $I(n)$。 把 $\{1,2,\dots,n\}$ 划分为两组 $A$ 和 $B$。一个划分的得分为 $\sum_{a\in A,\,b\in B}(a \mathbin{\&} b)$，即所有跨组对的按位与之和。$I(n)$ 是最大得分。已知 $I(10)=50$，需要求出 $I(1000)$。
Max-Xor $X(N)$。 对整数定义 $[x,y]=x^2\oplus y^2$（平方的异或）。考虑序列 $a_0,a_1,\dots,a_r$，其中 $1\le a_i\le N$，且相邻权重严格递增，$[a_{i-1},a_i]\lt [a_i,a_{i+1}]$。$X(N)$ 是 $\sum_i [a_{i-1},a_i]$ 可能取到的最大值。已知 $X(4)=71$ 和 $X(10)=702$，需要求出 $X(1000)$。
Unreachable Nim $C(N)$。 在三堆 Nim 中，如果一个状态 $(a,b,c)$ 只可能作为起始局面出现，则称其为不可达的。$C(N)$ 统计满足 $0\le a,b,c\lt N$ 的不可达状态数。已知 $C(10)=123$，需要求出 $C(1000)$。

随后元递推 $M$ 定义为

$$M(0)=I(1000),\quad M(1)=X(1000),\quad M(2)=C(1000),$$

$$M(k)=M(k-1)\,M(k-2)\,M(k-3)\pmod{p}\quad(k\ge 3),$$

其检查点为 $M(4)\equiv 457587170 \pmod p$。所求答案是 $M(1000)\bmod p$。

这三个子问题在 $n=1000$ 时都无法通过暴力求解；每一个都归结为一个结构化公式或一个小型动态规划。代码中的暴力例程只是为了在小规模输入上验证快速算法。

数学方法

子问题 $I(n)$：按位最大割

按位与在各个比特上是可分配的。将整数 $x$ 的第 $k$ 位记为 $x_k\in\{0,1\}$，则

$$a \mathbin{\&} b=\sum_{k\ge0}2^k\,a_k b_k.$$

对所有跨组对求和并交换求和次序，得分仅通过每一侧有多少个元素携带各比特而依赖于这些比特：

$$\sum_{a\in A,\,b\in B}(a\mathbin{\&} b)=\sum_{k\ge0}2^k\Big(\sum_{a\in A}a_k\Big)\Big(\sum_{b\in B}b_k\Big)=\sum_{k\ge0}2^k\,x_k\,y_k,$$

其中 $x_k$ 和 $y_k$ 分别统计 $A$ 和 $B$ 中第 $k$ 位被置位的元素个数。令

$$m_k=\#\{1\le v\le n : v_k=1\}=x_k+y_k$$

为 $[1,n]$ 中第 $k$ 位被置位的整数总数。这个总数由 $n$ 决定；只有它的拆分 $(x_k,y_k)$ 取决于具体划分。

对每一比特独立而言，在 $x_k+y_k=m_k$ 约束下，$x_k y_k$ 在最均衡的拆分时取得最大值，即 $\big\lfloor m_k^2/4\big\rfloor$。因此我们总有上界

$$I(n)\le U(n):=\sum_{k\ge0}2^k\left\lfloor\frac{m_k^2}{4}\right\rfloor.$$

微妙之处在于，单个划分必须同时平衡每一个比特。能做到这一点的构造是：按整数的种群计数（popcount）的奇偶性来给每个整数着色：当 $\operatorname{popcount}(v)$ 为偶时把 $v$ 放入 $A$，为奇时放入 $B$。对固定的比特 $k$，令

$$s_k=\#\{v_k=1,\ \operatorname{popcount}(v)\text{ even}\}-\#\{v_k=1,\ \operatorname{popcount}(v)\text{ odd}\}$$

为带符号的差值。则 $x_k=(m_k+s_k)/2$，$y_k=(m_k-s_k)/2$，而第 $k$ 位达成的值为

$$x_k y_k=\frac{m_k^2-s_k^2}{4}.$$

当 $|s_k|=m_k\bmod 2$ 时，这恰好等于最优值 $\lfloor m_k^2/4\rfloor$，也就是说奇偶着色把携带第 $k$ 位的整数平衡到至多相差一个元素。事实确实如此：在 $[1,n]$ 中第 $k$ 位被置位的整数里，翻转与 $k$ 不同的最低位是一个对合，它在保持仍处于区间内的同时翻转种群计数的奇偶性，从而把偶奇偶性的元素与奇奇偶性的元素配对，至多剩下一个落单。因此当 $m_k$ 为偶时 $s_k=0$，当 $m_k$ 为奇时 $s_k=\pm1$，于是奇偶划分在每一比特上同时最优：

$$\boxed{\,I(n)=\sum_{k\ge0}2^k\left\lfloor\frac{m_k^2}{4}\right\rfloor\,}.$$

代码同时计算 $U(n)$（逐比特最优值）和显式奇偶划分所达成的值，并断言二者相等——从而把最优性证明变成了运行时检查。

算例 $I(10)=50$。 在 $\{1,\dots,10\}$ 上的各比特总数为 $m_0=5$（奇数 $1,3,5,7,9$），$m_1=5$（$2,3,6,7,10$），$m_2=4$（$4,5,6,7$），$m_3=3$（$8,9,10$）。因此

子问题 $X(N)$：最长递增权重游走

在每个整数 $1,\dots,N$ 处放置一个顶点，并给 $u$ 与 $v$ 之间的（无向）边赋予权重

$$w(u,v)=u^2\oplus v^2.$$

一个合法序列 $a_0,a_1,\dots,a_r$ 即一条游走 $a_0\to a_1\to\cdots\to a_r$，其相邻边权严格递增，而 $X(N)$ 是此类游走的最大总权重。这是经典的边权递增下的最长路径问题，可以通过按权重非递减次序处理边来贪心求解。

维护 $\textit{best}[v]$ = 以顶点 $v$ 结尾的合法（严格递增）游走的最大总权重；将所有项初始化为 $0$（空游走）。把所有有向边按权重排序并逐一扫过。对于一条权重为 $w$ 的边 $u\to v$，一条以 $u$ 结尾且所有权重均 $\lt w$ 的游走可由该边延伸，得到候选值 $\textit{best}[u]+w$。为了遵守严格不等式，所有权重相同 $w$ 的边必须作为一批一起处理：批内每个候选值都由该批之前的 $\textit{best}$ 值计算，只有在整批评分完毕后才更新 $\textit{best}$ 各项。这就防止了两条等权边在同一条游走里相接。答案是整个扫描过程中所见的最大候选值：

$$X(N)=\max_{\text{edges }u\to v}\big(\textit{best}[u]+w(u,v)\big).$$

正确性。 在任何合法游走中权重都严格递增，因此当处理一条权重为 $w$ 的边时，每条更轻的边都已被松弛，$\textit{best}[u]$ 也已反映出仅使用权重 $\lt w$ 进入 $u$ 的最佳游走。对等权边分批保证了没有游走连续使用两条同权边，这正是严格递增条件。已公布的检查点 $X(4)=71$ 和 $X(10)=702$ 都能由此扫描复现。

子问题 $C(N)$：用数位 DP 统计不可达 Nim 局面

在正常玩法的 Nim 中，每一步都严格减少恰好一堆。回顾 Sprague–Grundy / Bouton 理论：当且仅当 nim 和 $s=a\oplus b\oplus c$ 为 $0$ 时，局面是必败的 $P$ 局面；否则它是必胜的 $N$ 局面，且获胜走法把它送往一个 $P$ 局面。因此在最优博弈下，所访问的局面交替为 $N,P,N,P,\dots$

固定一个 nim 和 $s\ne0$ 的 $N$ 局面 $(a,b,c)$，令 $\beta$ 为 $s$ 的最高置位。假设它是从某个 $P$ 局面 $(x,y,z)$（即 $x\oplus y\oplus z=0$）通过减少某一堆，比如 $z\to z'\lt z$，移动而到达的。新的 nim 和为 $z\oplus z'$，其最高位是 $z$ 与 $z'$ 相异的最高位；由于 $z'\lt z$，那一堆 $z'$ 不携带第 $\beta$ 位。所以任何能跟随在 $P$ 局面之后的 $N$ 局面，至少有一堆缺少第 $\beta$ 位。逆否而言：

$$\big(a,b,c\big)\text{ is unreachable }\iff s\ne0\ \text{ and bit }\beta\text{ is set in all of }a,b,c.$$

（如果某一堆缺少第 $\beta$ 位，就可以把该堆抬升为另外两堆的异或——这是一个严格更大的值，因为缺失的最高位迫使它增大——从而产生一个真正的 $P$ 局面前驱，于是该局面会在对局中途出现。）因此

$$C(N)=\#\Big\{(a,b,c)\in[0,N)^3 : s=a\oplus b\oplus c\ne0,\ a_\beta=b_\beta=c_\beta=1,\ \beta=\text{top bit of }s\Big\}.$$

这用一个按位数位 DP 来统计。枚举候选最高位 $\beta$。一个三元组要以此 $\beta$ 作出贡献：

在 $\beta$ 之上的每一位，三个比特必须异或为 $0$（这样 $s$ 在 $\beta$ 之上没有置位）；
在第 $\beta$ 位三个比特全为 $1$（这样 $s$ 具有第 $\beta$ 位，它是最高位，且所有堆都携带它）；
在 $\beta$ 之下的每一位比特自由取值。

每一堆还必须额外满足 $a,b,c\le N-1$。该 DP 从最高位到最低位扫描各比特，携带一个 $3$ 比特掩码，记录三堆中哪些仍然紧贴（到目前为止等于 $N-1$ 的前缀）；一个紧贴的堆不可超过 $N-1$ 对应位，且只有在匹配时才保持紧贴。把所有 $\beta$ 上存活的计数相加即得 $C(N)$；代码核对已公布的值 $C(10)=123$，并对所有 $n\le20$ 用三重循环与 DP 交叉验证。

元递推 $M$

有了这三个答案，种子值为 $M(0)=I(1000)$，$M(1)=X(1000)$，$M(2)=C(1000)$，且

$$M(k)\equiv M(k-1)\,M(k-2)\,M(k-3)\pmod{p},\qquad p=10^9+7.$$

由于每一项都取模素数 $p$，每一步只是两次模乘，到达 $k=1000$ 仅需约一千次乘法。代码向前滑动一个由最近三个值组成的窗口，每步取模 $p$。中间检查点 $M(4)\equiv457587170$ 守护着这条链，最终输出为 $M(1000)\bmod p$。

代码原理

C++、Python 和 Java 实现遵循相同的流程。辅助例程 parity_sign（通过反复执行 $v \mathbin{\&}(v-1)$ 得到种群计数的奇偶性）、bit_count 和 highest_bit 提供了位运算工具。

parity_and_candidate 扫描 $1\le v\le n$，为每一比特累加总数 $m_k$ 与带符号的奇偶差值 $s_k$；它返回 $U(n)=\sum2^k\lfloor m_k^2/4\rfloor$ 与奇偶划分值 $\sum2^k(m_k^2-s_k^2)/4$ 两者。max_and_value 断言二者相等，这就是奇偶划分最优的运行时证明，并返回 $I(n)$。brute_max_and 通过尝试全部 $2^{10}$ 个划分来验证 $I(10)=50$。

max_xor_sum 制表各平方，构建每条有向边 $(u^2\oplus v^2,\,u,\,v)$，按权重排序，并运行上文所述的分批最长递增权重 DP，返回 $X(n)$。

count_unreachable_nim 运行数位 DP：外层循环遍历最高位 $\beta$，内层沿各比特下降并维护 $8$ 状态的紧贴掩码，把"$\beta$ 之上异或为零"、"在 $\beta$ 全为一"和"$\beta$ 之下自由"这些规则与 $\le N-1$ 上界一起应用。brute_unreachable_nim 直接重新计算 $C(n)$ 用于交叉验证。

mul_mod 模 $p$ 相乘（C++ 版本扩展到 $128$ 位；Java 把乘积保持在 $64$ 位内，因为两个因子都已 $\lt p$）；meta_value 迭代三元积递推。run_checkpoints 断言 $I(10)=50$、$X(4)=71$、$X(10)=702$、对 $n\le20$ 有 $C(n)=$暴力值，以及 $C(10)=123$；随后 main 在打印 $M(1000)\bmod p$ 之前先验证 $M(4)\equiv457587170$。

复杂度分析

$I(n)$： 制表各比特总数耗时 $O(n\log n)$（$n$ 个整数中的每一个都对 $O(\log n)$ 个比特有贡献），合并它们为 $O(\log n)$；内存为 $O(\log n)$。

$X(N)$： 该图有 $\Theta(N^2)$ 条有向边，因此构建并排序它们以 $O(N^2\log N)$ 时间和 $O(N^2)$ 内存主导整体。这是最昂贵的阶段；对 $N=1000$ 它约为百万条边的量级，可在远不到一秒内完成。

$C(N)$： 数位 DP 有 $O(\log N)$ 种 $\beta$ 的选择，每种是在常数级 $8\times 8$ 状态空间上的 $O(\log N)$ 下降，所以是 $O(\log^2 N)$ 时间和 $O(1)$ 内存。

元递推： $O(k)$ 次模乘，即这里的 $O(1000)$。因此整体运行时间由 Max-Xor 阶段的 $\Theta(N^2\log N)$ 支配。

脚注与参考文献

问题页面：Project Euler 1000
最大割：Wikipedia - Maximum cut
按位运算（AND / XOR）：Wikipedia - Bitwise operation
汉明重量（种群计数）：Wikipedia - Hamming weight
Nim 与 Bouton / Sprague–Grundy 理论：Wikipedia - Nim
最长路径问题（DAG / 边排序）：Wikipedia - Longest path problem
模运算：Wikipedia - Modular arithmetic

Краткое описание

Задача 1000 — это юбилейная задача, которая объединяет три независимые подзадачи, ответы которых затем подаются в единую мета-рекуррентность. Окончательный ответ — это один остаток по модулю $p=10^9+7$.

Три подзадачи таковы:

Max-And $I(n)$. Разбейте $\{1,2,\dots,n\}$ на две группы $A$ и $B$. Оцените разбиение величиной $\sum_{a\in A,\,b\in B}(a \mathbin{\&} b)$ — суммой побитового И по каждой перекрёстной паре. $I(n)$ — это максимальная оценка. Нам дано, что $I(10)=50$, и нужно найти $I(1000)$.
Max-Xor $X(N)$. Для целых чисел положим $[x,y]=x^2\oplus y^2$ (исключающее ИЛИ квадратов). Рассмотрим последовательности $a_0,a_1,\dots,a_r$ с $1\le a_i\le N$, у которых последовательные веса строго возрастают, $[a_{i-1},a_i]\lt [a_i,a_{i+1}]$. $X(N)$ — это максимально возможное значение $\sum_i [a_{i-1},a_i]$. Нам дано, что $X(4)=71$ и $X(10)=702$, и нужно найти $X(1000)$.
Недостижимый Ним $C(N)$. В трёхкучном Ниме состояние $(a,b,c)$ называется недостижимым, если оно может встречаться только в качестве начальной позиции. $C(N)$ подсчитывает недостижимые состояния с $0\le a,b,c\lt N$. Нам дано, что $C(10)=123$, и нужно найти $C(1000)$.

Мета-рекуррентность $M$ затем определяется как

$$M(0)=I(1000),\quad M(1)=X(1000),\quad M(2)=C(1000),$$

$$M(k)=M(k-1)\,M(k-2)\,M(k-3)\pmod{p}\quad(k\ge 3),$$

с контрольной точкой $M(4)\equiv 457587170 \pmod p$. Требуемый ответ — это $M(1000)\bmod p$.

Ни одна из трёх подзадач не решается полным перебором при $n=1000$; каждая сводится к структурной формуле или небольшой динамической программе. Подпрограммы полного перебора в коде существуют только для проверки быстрых подпрограмм на малых входных данных.

Математический подход

Подзадача $I(n)$: побитовый максимальный разрез

Побитовое И распределяется по битам. Записывая $k$-й бит целого числа $x$ как $x_k\in\{0,1\}$,

$$a \mathbin{\&} b=\sum_{k\ge0}2^k\,a_k b_k.$$

Суммируя по всем перекрёстным парам и меняя порядок суммирования, оценка зависит от битов только через то, сколько элементов на каждой стороне несут каждый бит:

$$\sum_{a\in A,\,b\in B}(a\mathbin{\&} b)=\sum_{k\ge0}2^k\Big(\sum_{a\in A}a_k\Big)\Big(\sum_{b\in B}b_k\Big)=\sum_{k\ge0}2^k\,x_k\,y_k,$$

где $x_k$ и $y_k$ подсчитывают элементы $A$ и $B$, у которых установлен бит $k$. Пусть

$$m_k=\#\{1\le v\le n : v_k=1\}=x_k+y_k$$

— полное число целых чисел в $[1,n]$, у которых установлен бит $k$. Это полное число фиксировано величиной $n$; только его расщепление $(x_k,y_k)$ зависит от разбиения.

Для каждого бита по отдельности $x_k y_k$ максимизируется при $x_k+y_k=m_k$ наиболее сбалансированным расщеплением, что даёт $\big\lfloor m_k^2/4\big\rfloor$. Следовательно, мы всегда имеем верхнюю границу

$$I(n)\le U(n):=\sum_{k\ge0}2^k\left\lfloor\frac{m_k^2}{4}\right\rfloor.$$

Тонкость в том, что одно-единственное разбиение должно сбалансировать каждый бит одновременно. Конструкция, которая это делает, состоит в том, чтобы окрасить каждое целое число по чётности его числа единичных битов: поместить $v$ в $A$, когда $\operatorname{popcount}(v)$ чётно, и в $B$, когда нечётно. Для фиксированного бита $k$ пусть

$$s_k=\#\{v_k=1,\ \operatorname{popcount}(v)\text{ even}\}-\#\{v_k=1,\ \operatorname{popcount}(v)\text{ odd}\}$$

— знаковое расхождение. Тогда $x_k=(m_k+s_k)/2$, $y_k=(m_k-s_k)/2$, а достигнутое значение бита $k$ равно

$$x_k y_k=\frac{m_k^2-s_k^2}{4}.$$

Это в точности совпадает с оптимумом $\lfloor m_k^2/4\rfloor$, когда $|s_k|=m_k\bmod 2$, то есть окраска по чётности балансирует целые числа, несущие бит $k$, с точностью до одного элемента. И это действительно так: среди целых чисел в $[1,n]$ с установленным битом $k$ переключение наименьшего бита, отличного от $k$, является инволюцией, которая меняет чётность числа единичных битов, оставаясь внутри диапазона, поэтому она сопоставляет элементы чётной чётности элементам нечётной чётности с точностью до не более чем одного остаточного. Следовательно, $s_k=0$, когда $m_k$ чётно, и $s_k=\pm1$, когда $m_k$ нечётно, и разбиение по чётности одновременно оптимально на каждом бите:

$$\boxed{\,I(n)=\sum_{k\ge0}2^k\left\lfloor\frac{m_k^2}{4}\right\rfloor\,}.$$

Код вычисляет как $U(n)$ (побитовый оптимум), так и значение, достигаемое явным разбиением по чётности, и утверждает, что они равны, превращая доказательство оптимальности в проверку во время выполнения.

Разобранный пример $I(10)=50$. Суммы битов по $\{1,\dots,10\}$ равны $m_0=5$ (нечётные числа $1,3,5,7,9$), $m_1=5$ ($2,3,6,7,10$), $m_2=4$ ($4,5,6,7$), $m_3=3$ ($8,9,10$). Следовательно

Подзадача $X(N)$: самый длинный обход с возрастающим весом

Поместите вершину в каждое целое число $1,\dots,N$ и присвойте (неориентированному) ребру между $u$ и $v$ вес

$$w(u,v)=u^2\oplus v^2.$$

Допустимая последовательность $a_0,a_1,\dots,a_r$ — это обход $a_0\to a_1\to\cdots\to a_r$, у которого последовательные веса рёбер строго возрастают, а $X(N)$ — это максимальный суммарный вес такого обхода. Это классический самый длинный путь при возрастающих весах рёбер, который решается жадно путём обработки рёбер в порядке неубывания веса.

Поддерживайте $\textit{best}[v]$ = наибольший суммарный вес допустимого (строго возрастающего) обхода, оканчивающегося в вершине $v$; инициализируйте все записи значением $0$ (пустой обход). Отсортируйте все направленные рёбра по весу и пройдитесь по ним. Для ребра $u\to v$ веса $w$ обход, оканчивающийся в $u$ со всеми весами $\lt w$, может быть продолжен этим ребром, давая кандидата $\textit{best}[u]+w$. Чтобы соблюсти строгое неравенство, все рёбра, разделяющие один и тот же вес $w$, должны обрабатываться как один пакет: каждый кандидат в пакете вычисляется из значений $\textit{best}$ до пакета, и только после того, как весь пакет оценён, записи $\textit{best}$ обновляются. Это предотвращает сцепление двух рёбер одинакового веса внутри одного обхода. Ответом является максимальный кандидат, увиденный за весь проход:

$$X(N)=\max_{\text{edges }u\to v}\big(\textit{best}[u]+w(u,v)\big).$$

Корректность. В любом допустимом обходе веса строго возрастают, поэтому, когда обрабатывается ребро веса $w$, каждое более лёгкое ребро уже было релаксировано, и $\textit{best}[u]$ уже отражает наилучший обход в $u$, использующий только веса $\lt w$. Группировка равных весов в пакеты гарантирует, что ни один обход не использует два ребра одинакового веса подряд, что в точности и есть условие строгого возрастания. Опубликованные контрольные точки $X(4)=71$ и $X(10)=702$ воспроизводятся этим проходом.

Подзадача $C(N)$: недостижимые позиции Нима через цифровую динамику

В Ниме обычной игры каждый ход строго уменьшает ровно одну кучу. Напомним теорию Шпрага–Гранди / Бутона: позиция является проигрышной $P$-позицией ровно тогда, когда ним-сумма $s=a\oplus b\oplus c$ равна $0$; в противном случае это выигрышная $N$-позиция, и выигрышный ход переводит её в $P$-позицию. При оптимальной игре посещаемые позиции, следовательно, чередуются $N,P,N,P,\dots$

Зафиксируем $N$-позицию $(a,b,c)$ с ним-суммой $s\ne0$ и пусть $\beta$ — старший установленный бит $s$. Предположим, что она достигнута как результат хода из $P$-позиции $(x,y,z)$ (так что $x\oplus y\oplus z=0$) путём уменьшения одной кучи, скажем $z\to z'\lt z$. Новая ним-сумма равна $z\oplus z'$, старший бит которой — это старший бит, в котором $z$ и $z'$ различаются; поскольку $z'\lt z$, эта куча $z'$ не несёт бит $\beta$. Итак, любая $N$-позиция, которая может следовать за $P$-позицией, имеет по крайней мере одну кучу, лишённую бита $\beta$. Контрапозитивно:

$$\big(a,b,c\big)\text{ is unreachable }\iff s\ne0\ \text{ and bit }\beta\text{ is set in all of }a,b,c.$$

(Если какая-то куча лишена бита $\beta$, можно поднять эту кучу до исключающего ИЛИ двух остальных — строго большего значения, поскольку отсутствующий старший бит вынуждает его вверх — порождая настоящего предшественника-$P$-позицию, так что эта позиция действительно встречается в середине игры.) Следовательно

$$C(N)=\#\Big\{(a,b,c)\in[0,N)^3 : s=a\oplus b\oplus c\ne0,\ a_\beta=b_\beta=c_\beta=1,\ \beta=\text{top bit of }s\Big\}.$$

Это подсчитывается побитовой цифровой динамикой. Перебираем кандидата на старший бит $\beta$. Чтобы тройка вносила вклад с этим $\beta$:

в каждом бите выше $\beta$ три бита должны давать XOR $0$ (так что у $s$ нет установленного бита выше $\beta$);
в бите $\beta$ все три бита равны $1$ (так что у $s$ есть бит $\beta$, он является старшим битом, и все кучи его несут);
в каждом бите ниже $\beta$ биты свободны.

Каждая куча должна дополнительно удовлетворять $a,b,c\le N-1$. Динамика сканирует биты от старшего к младшему, неся $3$-битную маску, записывающую, какая из трёх куч всё ещё зажата (равна до сих пор префиксу $N-1$); зажатая куча не может превышать соответствующий бит $N-1$ и остаётся зажатой только пока она совпадает. Суммирование выживших количеств по всем $\beta$ даёт $C(N)$; код проверяет опубликованное значение $C(10)=123$ и перекрёстно сверяет динамику с тройным циклом для всех $n\le20$.

Мета-рекуррентность $M$

Имея на руках три ответа, начальные значения суть $M(0)=I(1000)$, $M(1)=X(1000)$, $M(2)=C(1000)$, и

$$M(k)\equiv M(k-1)\,M(k-2)\,M(k-3)\pmod{p},\qquad p=10^9+7.$$

Поскольку каждый член берётся по модулю простого числа $p$, каждый шаг — это всего лишь два модульных умножения, и достижение $k=1000$ обходится всего лишь примерно в тысячу умножений. Код продвигает вперёд окно из последних трёх значений, приводя по модулю $p$ на каждом шаге. Промежуточная контрольная точка $M(4)\equiv457587170$ охраняет цепочку, а окончательный вывод — это $M(1000)\bmod p$.

Как работает код

Реализации на C++, Python и Java следуют одному и тому же конвейеру. Вспомогательные подпрограммы parity_sign (чётность числа единичных битов через повторяющееся $v \mathbin{\&}(v-1)$), bit_count и highest_bit предоставляют битовые утилиты.

parity_and_candidate проходит по $1\le v\le n$, накапливая для каждого бита итог $m_k$ и знаковое расхождение по чётности $s_k$; она возвращает как $U(n)=\sum2^k\lfloor m_k^2/4\rfloor$, так и значение разбиения по чётности $\sum2^k(m_k^2-s_k^2)/4$. max_and_value утверждает, что они равны, что является сертификатом во время выполнения того, что разбиение по чётности оптимально, и возвращает $I(n)$. brute_max_and проверяет $I(10)=50$, перебирая все $2^{10}$ разбиений.

max_xor_sum табулирует квадраты, строит каждое направленное ребро $(u^2\oplus v^2,\,u,\,v)$, сортирует по весу и запускает пакетную динамику самого длинного возрастающего веса, описанную выше, возвращая $X(n)$.

count_unreachable_nim выполняет цифровую динамику: внешний цикл по старшему биту $\beta$, внутренний спуск по битам, поддерживающий $8$-состояний маску зажатости, применяя правила «XOR в ноль выше $\beta$», «все единицы в $\beta$» и «свобода ниже $\beta$» вместе с границей $\le N-1$. brute_unreachable_nim пересчитывает $C(n)$ напрямую для перекрёстной проверки.

mul_mod умножает по модулю $p$ (версия на C++ расширяется до $128$ бит; Java удерживает произведение в пределах $64$ бит, поскольку оба множителя уже $\lt p$); meta_value итерирует рекуррентность тройного произведения. run_checkpoints утверждает $I(10)=50$, $X(4)=71$, $X(10)=702$, $C(n)=$brute для $n\le20$ и $C(10)=123$; main затем проверяет $M(4)\equiv457587170$ перед выводом $M(1000)\bmod p$.

Анализ сложности

$I(n)$: табулирование сумм битов стоит $O(n\log n)$ (каждое из $n$ целых чисел вносит вклад в $O(\log n)$ битов), а их объединение — $O(\log n)$; память — $O(\log n)$.

$X(N)$: граф имеет $\Theta(N^2)$ направленных рёбер, поэтому их построение и сортировка доминируют при $O(N^2\log N)$ времени и $O(N^2)$ памяти. Это самая дорогостоящая стадия; для $N=1000$ это порядка миллиона рёбер, завершаемых значительно менее чем за секунду.

$C(N)$: цифровая динамика имеет $O(\log N)$ выборов $\beta$, каждый — спуск $O(\log N)$ по постоянному пространству состояний $8\times 8$, так что $O(\log^2 N)$ времени и $O(1)$ памяти.

Мета-рекуррентность: $O(k)$ модульных умножений, то есть $O(1000)$ здесь. Общее время работы, следовательно, определяется $\Theta(N^2\log N)$ стадии Max-Xor.

Сноски и источники

Страница задачи: Project Euler 1000
Максимальный разрез: Wikipedia - Maximum cut
Побитовая операция (И / XOR): Wikipedia - Bitwise operation
Вес Хэмминга (число единичных битов): Wikipedia - Hamming weight
Ним и теория Бутона / Шпрага–Гранди: Wikipedia - Nim
Задача о самом длинном пути (ориентированный ациклический граф / упорядочение рёбер): Wikipedia - Longest path problem
Модульная арифметика: Wikipedia - Modular arithmetic

ملخص المسألة

المسألة 1000 هي مسألة معلَم تجمع ثلاث مسائل فرعية مستقلة تُغذّى إجاباتها بعد ذلك في معاودة فوقية واحدة. الإجابة النهائية هي باقٍ واحد بالقياس النمطي $p=10^9+7$.

المسائل الفرعية الثلاث هي:

أكبر-وَ (Max-And) $I(n)$. قسّم $\{1,2,\dots,n\}$ إلى مجموعتين $A$ و$B$. تُسجَّل نقاط التقسيم بـ $\sum_{a\in A,\,b\in B}(a \mathbin{\&} b)$، وهو مجموع عملية "وَ" على مستوى البتات على كل زوج متقاطع. $I(n)$ هو أعلى نتيجة. أُخبِرنا بأن $I(10)=50$ وعلينا إيجاد $I(1000)$.
أكبر-أو-حصري (Max-Xor) $X(N)$. للأعداد الصحيحة نكتب $[x,y]=x^2\oplus y^2$ (الأو-الحصري لمربعَيهما). انظر إلى المتتاليات $a_0,a_1,\dots,a_r$ حيث $1\le a_i\le N$ والتي تتزايد أوزانها المتتالية تزايدًا حادًا، $[a_{i-1},a_i]\lt [a_i,a_{i+1}]$. $X(N)$ هو أكبر قيمة ممكنة لـ $\sum_i [a_{i-1},a_i]$. أُخبِرنا بأن $X(4)=71$ و$X(10)=702$، وعلينا إيجاد $X(1000)$.
نيم غير قابلة للبلوغ (Unreachable Nim) $C(N)$. في لعبة نيم ذات الأكوام الثلاثة تكون الحالة $(a,b,c)$ غير قابلة للبلوغ إذا لم يكن بإمكانها الحدوث إلا كموضع بداية. $C(N)$ يَعُدّ الحالات غير القابلة للبلوغ حيث $0\le a,b,c\lt N$. أُخبِرنا بأن $C(10)=123$ وعلينا إيجاد $C(1000)$.

تُعرَّف المعاودة الفوقية $M$ بعد ذلك بـ

$$M(0)=I(1000),\quad M(1)=X(1000),\quad M(2)=C(1000),$$

$$M(k)=M(k-1)\,M(k-2)\,M(k-3)\pmod{p}\quad(k\ge 3),$$

مع نقطة التحقق $M(4)\equiv 457587170 \pmod p$. الإجابة المطلوبة هي $M(1000)\bmod p$.

لا تُحَلّ أيٌّ من المسائل الفرعية الثلاث بالقوة الغاشمة عند $n=1000$؛ إذ تنهار كل منها إلى صيغة بنيوية أو برمجة ديناميكية صغيرة. توجد روتينات القوة الغاشمة في الكود فقط للتحقق من صحة الروتينات السريعة على المدخلات الصغيرة.

المنهج الرياضي

المسألة الفرعية $I(n)$: قَطْع أعظمي على مستوى البتات

تتوزّع عملية "وَ" على مستوى البتات عبر البتات. إذا كتبنا البت $k$ للعدد الصحيح $x$ بصيغة $x_k\in\{0,1\}$،

$$a \mathbin{\&} b=\sum_{k\ge0}2^k\,a_k b_k.$$

بالجمع على كل الأزواج المتقاطعة وتبديل ترتيب الجمع، تعتمد النتيجة على البتات فقط من خلال عدد العناصر في كل جانب التي تحمل كل بت:

$$\sum_{a\in A,\,b\in B}(a\mathbin{\&} b)=\sum_{k\ge0}2^k\Big(\sum_{a\in A}a_k\Big)\Big(\sum_{b\in B}b_k\Big)=\sum_{k\ge0}2^k\,x_k\,y_k,$$

حيث يَعُدّ $x_k$ و$y_k$ عناصر $A$ و$B$ التي يكون فيها البت $k$ مضبوطًا. ليكن

$$m_k=\#\{1\le v\le n : v_k=1\}=x_k+y_k$$

هو إجمالي عدد الأعداد الصحيحة في $[1,n]$ التي يكون بتُها $k$ مضبوطًا. هذا الإجمالي مثبَّت بـ $n$؛ وفقط تقسيمه $(x_k,y_k)$ يعتمد على التقسيم.

لكل بت على حدة، تُعظَّم $x_k y_k$ تحت القيد $x_k+y_k=m_k$ بالتقسيم الأكثر توازنًا، مما يعطي $\big\lfloor m_k^2/4\big\rfloor$. ومن ثَمّ يكون لدينا دائمًا الحدّ الأعلى

$$I(n)\le U(n):=\sum_{k\ge0}2^k\left\lfloor\frac{m_k^2}{4}\right\rfloor.$$

الدقيقة هنا هي أن تقسيمًا واحدًا فقط يجب أن يوازن كل بت في آنٍ واحد. والبناء الذي يحقق ذلك هو تلوين كل عدد صحيح بحسب زوجية عدد آحاده الثنائية: ضع $v$ في $A$ حين تكون $\operatorname{popcount}(v)$ زوجية وفي $B$ حين تكون فردية. لبت ثابت $k$، ليكن

$$s_k=\#\{v_k=1,\ \operatorname{popcount}(v)\text{ even}\}-\#\{v_k=1,\ \operatorname{popcount}(v)\text{ odd}\}$$

هو التفاوت ذو الإشارة. عندئذٍ $x_k=(m_k+s_k)/2$ و$y_k=(m_k-s_k)/2$، والقيمة المحقَّقة للبت $k$ هي

$$x_k y_k=\frac{m_k^2-s_k^2}{4}.$$

وهذا يطابق المثالية $\lfloor m_k^2/4\rfloor$ بالضبط عندما $|s_k|=m_k\bmod 2$، أي أن تلوين الزوجية يوازن الأعداد الصحيحة الحاملة للبت $k$ في حدود عنصر واحد. وهذا هو الحال فعلًا: من بين الأعداد الصحيحة في $[1,n]$ التي يكون فيها البت $k$ مضبوطًا، فإن قَلب أدنى بت يختلف عن $k$ هو تَقابُلٌ ذاتيٌّ (involution) يقلب زوجية عدد الآحاد الثنائية مع بقائه داخل المجال، فيطابق العناصر ذات الزوجية الزوجية بتلك ذات الزوجية الفردية مع بقاء عنصر واحد على الأكثر. لذلك $s_k=0$ عندما تكون $m_k$ زوجية و$s_k=\pm1$ عندما تكون $m_k$ فردية، ويكون تقسيم الزوجية مثاليًا في آنٍ واحد على كل بت:

$$\boxed{\,I(n)=\sum_{k\ge0}2^k\left\lfloor\frac{m_k^2}{4}\right\rfloor\,}.$$

يحسب الكود كلًّا من $U(n)$ (المثالية لكل بت) والقيمة المحقَّقة بتقسيم الزوجية الصريح، ويؤكّد أنهما متساويتان — مُحوِّلًا برهان المثالية إلى فحص أثناء التشغيل.

مثال محلول $I(10)=50$. إجماليّات البتات على $\{1,\dots,10\}$ هي $m_0=5$ (الأعداد الفردية $1,3,5,7,9$)، و$m_1=5$ ($2,3,6,7,10$)، و$m_2=4$ ($4,5,6,7$)، و$m_3=3$ ($8,9,10$). ومن ثَمّ

المسألة الفرعية $X(N)$: أطول مسير بأوزان متزايدة

ضع رأسًا عند كل عدد صحيح $1,\dots,N$ وأعطِ الحافة (غير الموجَّهة) بين $u$ و$v$ الوزن

$$w(u,v)=u^2\oplus v^2.$$

المتتالية الصالحة $a_0,a_1,\dots,a_r$ هي مسير $a_0\to a_1\to\cdots\to a_r$ تتزايد أوزان حوافه المتتالية تزايدًا حادًا، و$X(N)$ هو أعلى وزن إجمالي لمثل هذا المسير. وهذا هو المسألة الكلاسيكية أطول مسار تحت أوزان حواف متزايدة، القابلة للحل بطمعٍ عبر معالجة الحواف بترتيب وزني غير متناقص.

حافظ على $\textit{best}[v]$ = أكبر وزن إجمالي لمسير صالح (متزايد تزايدًا حادًا) ينتهي عند الرأس $v$؛ هيّئ كل المدخلات إلى $0$ (مسير فارغ). رتّب كل الحواف الموجَّهة بحسب الوزن وامسح خلالها. لحافة $u\to v$ ذات الوزن $w$، يمكن تمديد مسير ينتهي عند $u$ بكل أوزان $\lt w$ بهذه الحافة، مما يعطي المرشّح $\textit{best}[u]+w$. ولاحترام عدم المساواة الحادّ، يجب التعامل مع كل الحواف التي تشترك في الوزن نفسه $w$ كدفعة واحدة: يُحسب كل مرشّح في الدفعة من قيم $\textit{best}$ قبل الدفعة، وفقط بعد تسجيل الدفعة كلها تُحدَّث مدخلات $\textit{best}$. يمنع هذا أن تتسلسل حافتان متساويتا الوزن داخل مسير واحد. الإجابة هي أكبر مرشّح يُرى عبر المسح بأكمله:

$$X(N)=\max_{\text{edges }u\to v}\big(\textit{best}[u]+w(u,v)\big).$$

الصحّة. في أي مسير صالح تتزايد الأوزان تزايدًا حادًا، لذلك عند معالجة حافة ذات وزن $w$ تكون كل حافة أخفّ قد ارتُخِيَت بالفعل وتعكس $\textit{best}[u]$ بالفعل أفضل مسير إلى $u$ باستخدام أوزان $\lt w$ فقط. ويضمن تجميع الأوزان المتساوية في دفعات ألا يستخدم أي مسير حافتين متساويتي الوزن على التوالي، وهو بالضبط شرط التزايد الحاد. ونقطتا التحقق المنشورتان $X(4)=71$ و$X(10)=702$ يعيد هذا المسح إنتاجهما.

المسألة الفرعية $C(N)$: مواضع نيم غير القابلة للبلوغ عبر برمجة ديناميكية على الأرقام

في نيم اللعب العادي تُنقِص كل حركة كومةً واحدة بالضبط إنقاصًا حادًا. تذكّر نظرية سبراغ–غراندي / بوتون: يكون الموضع موضع خسارة $P$ بالضبط عندما يكون مجموع نيم $s=a\oplus b\oplus c$ مساويًا $0$؛ وإلا فهو موضع كسب $N$ وتنقله الحركة الكاسبة إلى موضع $P$. وتحت اللعب الأمثل تتناوب المواضع المزارة بالتالي $N,P,N,P,\dots$

ثبّت موضع كسب $N$ هو $(a,b,c)$ بمجموع نيم $s\ne0$ وليكن $\beta$ أعلى بت مضبوط في $s$. افترض أنه بُلِغ نتيجةً لحركة خارج موضع $P$ هو $(x,y,z)$ (حيث $x\oplus y\oplus z=0$) بإنقاص كومة واحدة، ولنقل $z\to z'\lt z$. مجموع نيم الجديد هو $z\oplus z'$، وأعلى بت فيه هو أعلى بت يختلف عنده $z$ و$z'$؛ وبما أن $z'\lt z$، فإن تلك الكومة $z'$ لا تحمل البت $\beta$. إذن أيُّ موضع كسب $N$ يمكن أن يلي موضع $P$ يكون فيه كومة واحدة على الأقل تفتقر إلى البت $\beta$. وبعكس النقيض:

$$\big(a,b,c\big)\text{ is unreachable }\iff s\ne0\ \text{ and bit }\beta\text{ is set in all of }a,b,c.$$

(إذا افتقرت إحدى الأكوام إلى البت $\beta$، فيمكن رفع تلك الكومة إلى الأو-الحصري للكومتين الأخريين — وهو قيمة أكبر تمامًا، لأن البت الأعلى المفقود يفرض رفعها — مما يُنتِج سَلَفًا حقيقيًا في موضع $P$، ولذا يحدث الموضع فعلًا في منتصف اللعبة.) ومن ثَمّ

$$C(N)=\#\Big\{(a,b,c)\in[0,N)^3 : s=a\oplus b\oplus c\ne0,\ a_\beta=b_\beta=c_\beta=1,\ \beta=\text{top bit of }s\Big\}.$$

يُحصى هذا ببرمجة ديناميكية على مستوى البتات على الأرقام. عَدِّد البت الأعلى المرشّح $\beta$. لكي يساهم ثلاثيّ بهذا الـ $\beta$:

عند كل بت فوق $\beta$، يجب أن يكون الأو-الحصري للبتات الثلاثة $0$ (بحيث لا يكون لـ $s$ أي بت مضبوط فوق $\beta$)؛
عند البت $\beta$ تكون البتات الثلاثة كلها $1$ (بحيث يكون لـ $s$ البت $\beta$، وهو البت الأعلى، وتحمله كل الأكوام)؛
عند كل بت تحت $\beta$ تكون البتات حرّة.

يجب على كل كومة بالإضافة إلى ذلك أن تحقّق $a,b,c\le N-1$. تمسح البرمجة الديناميكية البتات من الأكثر دلالة إلى الأقل دلالة حاملةً قناعًا من $3$ بتات يسجّل أيٌّ من الأكوام الثلاث ما يزال محكمًا (مساويًا حتى الآن لبادئة $N-1$)؛ لا يجوز لكومة محكمة أن تتجاوز البت المقابل من $N-1$، وتبقى محكمة فقط ما دامت تطابقه. وبجمع الأعداد الناجية على كل $\beta$ ينتج $C(N)$؛ يفحص الكود القيمة المنشورة $C(10)=123$ ويقابل البرمجة الديناميكية بحلقة الثلاثيات لكل $n\le20$.

المعاودة الفوقية $M$

وبامتلاك الإجابات الثلاث، تكون البذور $M(0)=I(1000)$ و$M(1)=X(1000)$ و$M(2)=C(1000)$، و

$$M(k)\equiv M(k-1)\,M(k-2)\,M(k-3)\pmod{p},\qquad p=10^9+7.$$

ولأن كل حدّ يُؤخَذ بالقياس النمطي للعدد الأولي $p$، فإن كل خطوة هي مجرد ضربتين نمطيتين، وبلوغ $k=1000$ يكلّف نحو ألف ضربة فقط. ينزلق الكود بنافذة من آخر ثلاث قيم إلى الأمام، مختزِلًا بالقياس النمطي $p$ عند كل خطوة. وتحرس نقطة التحقق الوسيطة $M(4)\equiv457587170$ السلسلة، والمخرَج النهائي هو $M(1000)\bmod p$.

كيف يعمل الكود

تتّبع تطبيقات C++ وPython وJava خطّ المعالجة نفسه. توفّر الروتينات المساعدة parity_sign (زوجية عدد الآحاد الثنائية عبر التكرار $v \mathbin{\&}(v-1)$) وbit_count وhighest_bit أدوات البتات.

تمسح parity_and_candidate القيم $1\le v\le n$، مُراكِمةً لكل بت الإجمالي $m_k$ والتفاوت الزوجي ذا الإشارة $s_k$؛ وتُرجِع كلًّا من $U(n)=\sum2^k\lfloor m_k^2/4\rfloor$ وقيمة تقسيم الزوجية $\sum2^k(m_k^2-s_k^2)/4$. وتؤكّد max_and_value أنهما متساويتان، وهو الشهادة أثناء التشغيل على أن تقسيم الزوجية مثاليّ، وتُرجِع $I(n)$. وتتحقّق brute_max_and من $I(10)=50$ بتجريب كل التقسيمات الـ $2^{10}$.

تجدول max_xor_sum المربعات، وتبني كل حافة موجَّهة $(u^2\oplus v^2,\,u,\,v)$، وترتّب بحسب الوزن، وتُجري البرمجة الديناميكية لأطول وزن متزايد بالدفعات الموصوفة أعلاه، مُرجِعةً $X(n)$.

تُجري count_unreachable_nim البرمجة الديناميكية على الأرقام: حلقة خارجية على البت الأعلى $\beta$، ونزولٌ داخليٌّ عبر البتات يحافظ على قناع الإحكام ذي الحالات الـ $8$، مطبِّقةً قواعد "الأو-الحصري إلى صفر فوق $\beta$" و"كلها آحاد عند $\beta$" و"حرّة تحت $\beta$" مع القيد $\le N-1$. وتعيد brute_unreachable_nim حساب $C(n)$ مباشرةً للمقابلة.

تضرب mul_mod بالقياس النمطي $p$ (نسخة C++ تتوسّع إلى $128$ بت؛ وJava تُبقي الجداء داخل $64$ بت لأن كلا العاملين أصلًا $\lt p$)؛ وتُكرّر meta_value معاودة الجداء الثلاثي. وتؤكّد run_checkpoints أن $I(10)=50$ و$X(4)=71$ و$X(10)=702$ و$C(n)=$القوة الغاشمة لـ $n\le20$ و$C(10)=123$؛ ثم تتحقّق main من $M(4)\equiv457587170$ قبل طباعة $M(1000)\bmod p$.

تحليل التعقيد

$I(n)$: جدولة إجماليّات البتات تكلّف $O(n\log n)$ (كلّ من الأعداد الصحيحة الـ $n$ يساهم في $O(\log n)$ بت)، ودمجها هو $O(\log n)$؛ والذاكرة هي $O(\log n)$.

$X(N)$: يحوي البيان $\Theta(N^2)$ حافة موجَّهة، لذا يهيمن بناؤها وترتيبها بزمن $O(N^2\log N)$ وذاكرة $O(N^2)$. وهذه هي أكثر المراحل تكلفة؛ ولأجل $N=1000$ فهي بترتيب مليون حافة، تكتمل في أقلّ من ثانية بكثير.

$C(N)$: للبرمجة الديناميكية على الأرقام $O(\log N)$ خيارًا لـ $\beta$، كلٌّ منها نزولٌ بطول $O(\log N)$ على فضاء حالات ثابت $8\times 8$، فيكون الزمن $O(\log^2 N)$ والذاكرة $O(1)$.

المعاودة الفوقية: $O(k)$ ضربة نمطية، أي $O(1000)$ هنا. ومن ثَمّ يحكم زمنَ التشغيل الإجمالي العاملُ $\Theta(N^2\log N)$ لمرحلة أكبر-أو-حصري.

هوامش ومراجع

صفحة المسألة: Project Euler 1000
القَطْع الأعظمي: Wikipedia - Maximum cut
العملية على مستوى البتات (وَ / أو-حصري): Wikipedia - Bitwise operation
وزن هامينغ (عدد الآحاد الثنائية): Wikipedia - Hamming weight
نيم ونظرية بوتون / سبراغ–غراندي: Wikipedia - Nim
مسألة أطول مسار (بيان لاحلقي موجَّه / ترتيب الحواف): Wikipedia - Longest path problem
الحساب النمطي: Wikipedia - Modular arithmetic

Problem Summary

Mathematical Approach

Sub-problem \(I(n)\): a bitwise maximum cut

Sub-problem \(X(N)\): a longest increasing-weight walk

Sub-problem \(C(N)\): unreachable Nim positions by digit DP

The meta-recurrence \(M\)

How the Code Works

Complexity Analysis

Footnotes and References

Problemzusammenfassung

Mathematischer Ansatz

Teilproblem \(I(n)\): ein bitweiser maximaler Schnitt

Teilproblem \(X(N)\): ein längster Weg mit zunehmenden Gewichten

Teilproblem \(C(N)\): unerreichbare Nim-Positionen durch Ziffern-DP

Die Meta-Rekurrenz \(M\)

Wie der Code arbeitet

Komplexitätsanalyse

Fußnoten und Referenzen

Problem Özeti

Matematiksel Yaklaşım

Alt problem \(I(n)\): bit düzeyinde bir maksimum kesim

Alt problem \(X(N)\): en uzun artan ağırlıklı yürüyüş

Alt problem \(C(N)\): basamak DP ile ulaşılamaz Nim konumları

Meta-yineleme \(M\)

Kod Nasıl Çalışır

Karmaşıklık Analizi

Dipnotlar ve Referanslar

Resumen del Problema

Enfoque Matemático

Subproblema \(I(n)\): un corte máximo bit a bit

Subproblema \(X(N)\): un camino más largo con pesos crecientes

Subproblema \(C(N)\): posiciones de Nim inalcanzables mediante DP por dígitos

La meta-recurrencia \(M\)

Cómo Funciona el Código

Análisis de Complejidad

Notas al pie y referencias

问题概述

数学方法

子问题 \(I(n)\)：按位最大割

子问题 \(X(N)\)：最长递增权重游走

子问题 \(C(N)\)：用数位 DP 统计不可达 Nim 局面

元递推 \(M\)

代码原理

复杂度分析

脚注与参考文献

Краткое описание

Математический подход

Подзадача \(I(n)\): побитовый максимальный разрез

Подзадача \(X(N)\): самый длинный обход с возрастающим весом

Подзадача \(C(N)\): недостижимые позиции Нима через цифровую динамику

Мета-рекуррентность \(M\)

Как работает код

Анализ сложности

Сноски и источники

ملخص المسألة

المنهج الرياضي

المسألة الفرعية \(I(n)\): قَطْع أعظمي على مستوى البتات

المسألة الفرعية \(X(N)\): أطول مسير بأوزان متزايدة

المسألة الفرعية \(C(N)\): مواضع نيم غير القابلة للبلوغ عبر برمجة ديناميكية على الأرقام

المعاودة الفوقية \(M\)

كيف يعمل الكود

تحليل التعقيد

هوامش ومراجع