Let \(p(n)\) denote the number of ways to write \(n\) as a sum of powers of \(2\), with unlimited repetition allowed. Problem 890 asks for
$$p\left(7^{777}\right)\pmod{10^9+7}.$$
The classical generating function is
$$\prod_{j\ge 0}\frac{1}{1-x^{2^j}}=\sum_{n\ge 0}p(n)x^n.$$
Because \(7^{777}\) is enormous, the implementation cannot iterate up to \(n\). Instead, it reads the binary digits of \(n\) and counts valid carry patterns. That turns the problem into a digit DP whose size depends on the bit-length of \(n\), not on \(n\) itself.
The key observation is that a binary partition can be read bit by bit. At each bit position we only need to know how many lower-power terms have paired up and carried into the next position.
Write
$$n=\sum_{k=0}^{L-1} b_k2^k,\qquad b_k\in\{0,1\}.$$
If a partition uses \(x_k\) copies of \(2^k\), then after combining pairs of \(2^k\)-terms into \(2^{k+1}\)-terms we get the balance equation
$$x_k+c_k=b_k+2c_{k+1},$$
where \(c_k\) is the carry entering bit \(k\), and \(c_{k+1}\) is the carry leaving it. For fixed \(c_k\) and \(c_{k+1}\), there is exactly one possible value of \(x_k\), namely
$$x_k=b_k+2c_{k+1}-c_k.$$
This value is valid if and only if it is nonnegative, so
$$c_k\le 2c_{k+1}+b_k.$$
Now define \(F_k(c)\) to be the number of ways to satisfy the lowest \(k\) bits of \(n\) and end with carry \(c\) into bit \(k\). Then for \(k\ge 1\),
$$F_{k+1}(u)=\sum_{c=0}^{2u+b_k}F_k(c).$$
After the least significant bit there is always exactly one choice once the outgoing carry is fixed, so
$$F_1(c)=1\qquad(c\ge 0).$$
This is also why the least significant bit does not need a special case later: both \(p(2m)\) and \(p(2m+1)\) start from the same initial carry polynomial.
The recurrence is a prefix sum evaluated at \(2u+b_k\), so starting from the constant function \(F_1(c)=1\), each step raises the degree by at most one. Therefore \(F_k(c)\) is always a polynomial of degree at most \(k-1\).
The implementation stores this polynomial in the basis
$$\binom{c}{0},\binom{c}{1},\binom{c}{2},\dots$$
so that
$$F_k(c)=\sum_{j=0}^{k-1}A_{k,j}\binom{c}{j}.$$
This basis is ideal because of the hockey-stick identity
$$\sum_{c=0}^{M}\binom{c}{j}=\binom{M+1}{j+1}.$$
Substituting the binomial expansion into the recurrence gives
$$F_{k+1}(u)=\sum_{j=0}^{k-1}A_{k,j}\binom{2u+b_k+1}{j+1}.$$
So the whole problem becomes: given the coefficient vector \((A_{k,0},\dots,A_{k,k-1})\), compute the next coefficient vector efficiently.
If the current bit is \(b_k=0\), then
$$F_{k+1}(u)=\sum_{j=0}^{k-1}A_{k,j}\binom{2u+1}{j+1}.$$
Using Pascal's identity,
$$\binom{2u+1}{j+1}=\binom{2u}{j+1}+\binom{2u}{j}.$$
Hence if we define an intermediate coefficient list by
$$B_r=A_{k,r}+A_{k,r-1},$$
with the convention that terms outside the valid range are \(0\), then
$$F_{k+1}(u)=\sum_{r=0}^{k}B_r\binom{2u}{r}.$$
We now need to re-expand \(\binom{2u}{r}\) in the basis \(\binom{u}{j}\). Start from
$$\sum_{r\ge 0}\binom{2u}{r}t^r=(1+t)^{2u}=((1+t)^2)^u=(1+2t+t^2)^u.$$
Expanding again,
$$ (1+2t+t^2)^u=\sum_{j\ge 0}\binom{u}{j}(2t+t^2)^j=\sum_{j\ge 0}\binom{u}{j}\sum_{m=0}^{j}\binom{j}{m}2^{j-m}t^{j+m}. $$
Therefore the coefficient of \(\binom{u}{j}\) inside \(\binom{2u}{j+m}\) is
$$w_j(m)=\binom{j}{m}2^{j-m}.$$
So the next coefficient vector is
$$A_{k+1,j}=\sum_{m\ge 0} B_{j+m}\,w_j(m).$$
In the finite arrays used by the implementation, the sum stops at
$$m_{\max}=\min(j,\;k-j).$$
If the current bit is \(b_k=1\), then
$$F_{k+1}(u)=\sum_{j=0}^{k-1}A_{k,j}\binom{2u+2}{j+1}.$$
Applying Pascal once more gives
$$\binom{2u+2}{j+1}=\binom{2u+1}{j+1}+\binom{2u+1}{j},$$
so the same intermediate coefficients \(B_r\) appear and
$$F_{k+1}(u)=\sum_{r=0}^{k}B_r\binom{2u+1}{r}.$$
Now use
$$\binom{2u+1}{r}=\binom{2u}{r}+\binom{2u}{r-1}.$$
This means the kernel for bit \(1\) is just the sum of two neighboring bit-\(0\) kernels:
$$w^{(1)}_j(m)=w_j(m)+w_j(m-1),$$
where \(w_j(m)=0\) whenever \(m<0\) or \(m>j\). Thus
$$A_{k+1,j}=\sum_{m\ge 0} B_{j+m}\,w^{(1)}_j(m).$$
In the finite implementation, the upper limit is
$$m_{\max}=\min(j+1,\;k-j).$$
After all \(L\) bits have been processed, there can be no carry beyond the most significant bit. Therefore the desired count is
$$p(n)=F_L(0).$$
In the binomial basis, this is especially simple:
$$F_L(0)=\sum_{j=0}^{L-1}A_{L,j}\binom{0}{j}=A_{L,0},$$
because \(\binom{0}{0}=1\) and \(\binom{0}{j}=0\) for every \(j>0\). That is why the implementation returns the first coefficient of the last state vector.
Take \(n=7=111_2\). We begin with
$$F_1(c)=1.$$
The second bit is \(1\), so
$$F_2(u)=\sum_{c=0}^{2u+1}1=2u+2.$$
In binomial form,
$$F_2(u)=2\binom{u}{0}+2\binom{u}{1}.$$
The third bit is again \(1\), therefore
$$F_3(u)=\sum_{c=0}^{2u+1}(2c+2)=(2u+2)(2u+3)=4u^2+10u+6.$$
Convert this polynomial back to the binomial basis:
$$F_3(u)=6\binom{u}{0}+14\binom{u}{1}+8\binom{u}{2}.$$
Hence
$$p(7)=F_3(0)=6,$$
which matches the known value and the implementation checkpoint.
The C++, Python, and Java implementations all target the same digit-DP formula. The C++ and Java implementations first convert \(n\) to binary, least significant bit first. They then precompute powers of \(2\) modulo \(10^9+7\), Pascal coefficients modulo \(10^9+7\), and two lower-triangular transition tables corresponding to the formulas for a current bit of \(0\) and \(1\).
The running state is the coefficient list of \(F_k(c)\) in the basis \(\binom{c}{j}\). For each new bit, the implementation first applies the Pascal update \(B_r=A_r+A_{r-1}\), then performs the appropriate convolution against the precomputed kernel. The C++ implementation can split the outer coefficient range across several threads, while the Java implementation performs the same arithmetic serially.
The Python implementation is a thin execution bridge: it compiles and runs the C++ solver when necessary, then parses the numeric output. In every language, the published answer is the first coefficient after the most significant bit has been processed.
Let \(L=\lfloor\log_2 n\rfloor+1\). Precomputing powers of \(2\), Pascal coefficients, and the two triangular transition tables costs \(O(L^2)\) time and \(O(L^2)\) memory. At stage \(k\), the convolution examines \(\Theta(k^2)\) coefficient pairs, so the full dynamic program costs
$$\sum_{k=1}^{L-1}\Theta(k^2)=\Theta(L^3)$$
time. The optional threading in the C++ implementation improves wall-clock time but does not change the asymptotic bound.
Sei \(p(n)\) die Anzahl der Darstellungen von \(n\) als Summe von Zweierpotenzen, wobei jede Zweierpotenz beliebig oft verwendet werden darf. In Problem 890 wird gesucht:
$$p\left(7^{777}\right)\pmod{10^9+7}.$$
Die klassische erzeugende Funktion lautet
$$\prod_{j\ge 0}\frac{1}{1-x^{2^j}}=\sum_{n\ge 0}p(n)x^n.$$
Da \(7^{777}\) astronomisch groß ist, kann man nicht bis \(n\) iterieren. Stattdessen liest die Lösung die Binärdarstellung von \(n\) aus und zählt zulässige Übertragsmuster. Dadurch hängt die Laufzeit nur von der Bitlänge von \(n\) ab.
Die Grundidee ist, eine binäre Partition bitweise zu betrachten. In jeder Stelle muss man nur wissen, wie viele kleinere Summanden zu Paaren zusammengefasst wurden und als Übertrag in die nächste Stelle gehen.
Schreibe
$$n=\sum_{k=0}^{L-1} b_k2^k,\qquad b_k\in\{0,1\}.$$
Verwendet eine Partition \(x_k\) Kopien von \(2^k\), dann gilt nach dem Zusammenfassen je zweier \(2^k\)-Summanden zu einem \(2^{k+1}\)-Summanden
$$x_k+c_k=b_k+2c_{k+1},$$
wobei \(c_k\) der eingehende Übertrag an Bit \(k\) und \(c_{k+1}\) der ausgehende Übertrag ist. Für feste \(c_k\) und \(c_{k+1}\) gibt es genau einen möglichen Wert von \(x_k\), nämlich
$$x_k=b_k+2c_{k+1}-c_k.$$
Dieser Wert ist genau dann zulässig, wenn er nichtnegativ ist, also
$$c_k\le 2c_{k+1}+b_k.$$
Nun sei \(F_k(c)\) die Anzahl der Möglichkeiten, die niedrigsten \(k\) Bits von \(n\) zu erfüllen und mit Übertrag \(c\) in Bit \(k\) zu enden. Dann gilt für \(k\ge 1\)
$$F_{k+1}(u)=\sum_{c=0}^{2u+b_k}F_k(c).$$
Nach dem niederwertigsten Bit gibt es für jeden fest gewählten ausgehenden Übertrag genau eine Möglichkeit, daher
$$F_1(c)=1\qquad(c\ge 0).$$
Deshalb braucht das niederwertigste Bit später auch keinen Spezialfall: Sowohl \(p(2m)\) als auch \(p(2m+1)\) starten mit demselben Anfangspolynom.
Die Rekursion ist eine Präfixsumme, ausgewertet bei \(2u+b_k\). Ausgehend von der Konstanten \(F_1(c)=1\) steigt der Grad daher in jedem Schritt höchstens um \(1\). Also ist \(F_k(c)\) immer ein Polynom vom Grad höchstens \(k-1\).
Die Implementierung speichert dieses Polynom in der Basis
$$\binom{c}{0},\binom{c}{1},\binom{c}{2},\dots$$
also
$$F_k(c)=\sum_{j=0}^{k-1}A_{k,j}\binom{c}{j}.$$
Diese Basis ist ideal wegen der Hockey-Stick-Identität
$$\sum_{c=0}^{M}\binom{c}{j}=\binom{M+1}{j+1}.$$
Setzt man die Entwicklung in die Rekursion ein, erhält man
$$F_{k+1}(u)=\sum_{j=0}^{k-1}A_{k,j}\binom{2u+b_k+1}{j+1}.$$
Damit reduziert sich alles auf die Frage, wie man aus dem Koeffizientenvektor \((A_{k,0},\dots,A_{k,k-1})\) effizient den nächsten Vektor berechnet.
Für \(b_k=0\) gilt
$$F_{k+1}(u)=\sum_{j=0}^{k-1}A_{k,j}\binom{2u+1}{j+1}.$$
Mit Pascalscher Identität
$$\binom{2u+1}{j+1}=\binom{2u}{j+1}+\binom{2u}{j}$$
und den Zwischenkoeffizienten
$$B_r=A_{k,r}+A_{k,r-1},$$
wobei Werte außerhalb des gültigen Bereichs als \(0\) zählen, folgt
$$F_{k+1}(u)=\sum_{r=0}^{k}B_r\binom{2u}{r}.$$
Nun muss \(\binom{2u}{r}\) wieder in der Basis \(\binom{u}{j}\) entwickelt werden. Dazu beginnt man mit
$$\sum_{r\ge 0}\binom{2u}{r}t^r=(1+t)^{2u}=((1+t)^2)^u=(1+2t+t^2)^u.$$
Noch einmal ausmultipliziert ergibt das
$$ (1+2t+t^2)^u=\sum_{j\ge 0}\binom{u}{j}(2t+t^2)^j=\sum_{j\ge 0}\binom{u}{j}\sum_{m=0}^{j}\binom{j}{m}2^{j-m}t^{j+m}. $$
Damit ist der Koeffizient von \(\binom{u}{j}\) in \(\binom{2u}{j+m}\)
$$w_j(m)=\binom{j}{m}2^{j-m}.$$
Somit lautet die Aktualisierung
$$A_{k+1,j}=\sum_{m\ge 0} B_{j+m}\,w_j(m).$$
In den endlichen Arrays der Implementierung endet die Summe bei
$$m_{\max}=\min(j,\;k-j).$$
Für \(b_k=1\) erhält man
$$F_{k+1}(u)=\sum_{j=0}^{k-1}A_{k,j}\binom{2u+2}{j+1}.$$
Mit Pascal folgt
$$\binom{2u+2}{j+1}=\binom{2u+1}{j+1}+\binom{2u+1}{j},$$
sodass dieselben Zwischenkoeffizienten \(B_r\) auftreten und
$$F_{k+1}(u)=\sum_{r=0}^{k}B_r\binom{2u+1}{r}$$
gilt. Nun benutzt man
$$\binom{2u+1}{r}=\binom{2u}{r}+\binom{2u}{r-1}.$$
Also ist der Kern für Bit \(1\) einfach die Summe zweier benachbarter Bit-\(0\)-Kerne:
$$w^{(1)}_j(m)=w_j(m)+w_j(m-1),$$
wobei \(w_j(m)=0\) für \(m<0\) oder \(m>j\). Damit
$$A_{k+1,j}=\sum_{m\ge 0} B_{j+m}\,w^{(1)}_j(m).$$
Im tatsächlichen Code ist die Obergrenze
$$m_{\max}=\min(j+1,\;k-j).$$
Nach allen \(L\) Bits darf es keinen Übertrag jenseits des höchstwertigen Bits mehr geben. Gesucht ist daher
$$p(n)=F_L(0).$$
In der Binomialbasis ist das besonders einfach:
$$F_L(0)=\sum_{j=0}^{L-1}A_{L,j}\binom{0}{j}=A_{L,0},$$
denn \(\binom{0}{0}=1\) und \(\binom{0}{j}=0\) für alle \(j>0\). Genau deshalb gibt die Implementierung den ersten Koeffizienten des letzten Zustandsvektors aus.
Setze \(n=7=111_2\). Wir starten mit
$$F_1(c)=1.$$
Das zweite Bit ist \(1\), also
$$F_2(u)=\sum_{c=0}^{2u+1}1=2u+2.$$
In Binomialform ist das
$$F_2(u)=2\binom{u}{0}+2\binom{u}{1}.$$
Auch das dritte Bit ist \(1\), daher
$$F_3(u)=\sum_{c=0}^{2u+1}(2c+2)=(2u+2)(2u+3)=4u^2+10u+6.$$
Zurück in der Binomialbasis ergibt sich
$$F_3(u)=6\binom{u}{0}+14\binom{u}{1}+8\binom{u}{2}.$$
Folglich
$$p(7)=F_3(0)=6,$$
genau der bekannte Wert und zugleich der Kontrollwert der Implementierung.
Die C++-, Python- und Java-Implementierungen berechnen alle dieselbe Ziffern-DP. Die C++- und Java-Implementierungen wandeln \(n\) zunächst in seine Binärziffern in aufsteigender Stellenreihenfolge um. Anschließend werden Potenzen von \(2\) modulo \(10^9+7\), Pascalsche Koeffizienten modulo \(10^9+7\) sowie zwei untere Dreieckstabellen für die Übergänge bei einem aktuellen Bit \(0\) beziehungsweise \(1\) vorab berechnet.
Der laufende Zustand ist die Koeffizientenliste von \(F_k(c)\) in der Basis \(\binom{c}{j}\). Für jedes neue Bit führt die Implementierung zuerst den Pascal-Schritt \(B_r=A_r+A_{r-1}\) aus und berechnet danach die passende Faltung mit dem vorberechneten Kern. Die C++-Implementierung kann den äußeren Koeffizientenbereich auf mehrere Threads aufteilen; die Java-Implementierung führt dieselbe Rechnung seriell aus.
Die Python-Implementierung ist eine schlanke Ausführungsbrücke: Sie kompiliert und startet bei Bedarf den C++-Solver und liest anschließend das numerische Ergebnis aus. In allen drei Sprachen ist die veröffentlichte Antwort der erste Koeffizient nach der Verarbeitung des höchstwertigen Bits.
Sei \(L=\lfloor\log_2 n\rfloor+1\). Das Vorberechnen der Zweierpotenzen, der Pascalschen Koeffizienten und der beiden Dreieckskerne kostet \(O(L^2)\) Zeit und \(O(L^2)\) Speicher. In Stufe \(k\) betrachtet die Faltung \(\Theta(k^2)\) Koeffizientenpaare, also hat die gesamte dynamische Programmierung den Aufwand
$$\sum_{k=1}^{L-1}\Theta(k^2)=\Theta(L^3)$$
in der Zeit. Die optionale Parallelisierung in C++ verbessert die reale Laufzeit, ändert aber nicht die asymptotische Schranke.
\(p(n)\), \(n\) sayısını \(2\) kuvvetlerinin toplamı olarak yazma sayısı olsun; her \(2^k\) kuvveti istenildiği kadar tekrar kullanılabilir. Problem 890 şu değeri ister:
$$p\left(7^{777}\right)\pmod{10^9+7}.$$
Klasik üreteç fonksiyon
$$\prod_{j\ge 0}\frac{1}{1-x^{2^j}}=\sum_{n\ge 0}p(n)x^n$$
şeklindedir. Fakat \(7^{777}\) olağanüstü büyük olduğu için \(n\)'e kadar ilerleyen bir yöntem kullanılamaz. Bunun yerine çözüm, \(n\)'in ikili basamaklarını okuyup geçerli elde desenlerini sayar. Böylece maliyet \(n\)'in büyüklüğüne değil, yalnızca bit uzunluğuna bağlı olur.
Ana fikir, bir ikili bölünüşü bit bit okumaktır. Her bit konumunda yalnızca daha küçük kuvvetlerden kaç tanesinin eşleşip bir üst bite elde taşıdığını bilmek yeterlidir.
Şunu yazalım:
$$n=\sum_{k=0}^{L-1} b_k2^k,\qquad b_k\in\{0,1\}.$$
Eğer bir bölünüşte \(2^k\) teriminden \(x_k\) tane kullanılıyorsa, iki \(2^k\) terimini bir \(2^{k+1}\) terimine dönüştürdükten sonra şu denge elde edilir:
$$x_k+c_k=b_k+2c_{k+1},$$
burada \(c_k\), \(k\). bite giren elde; \(c_{k+1}\) ise çıkan eldedir. \(c_k\) ve \(c_{k+1}\) sabitken olası \(x_k\) değeri tektir:
$$x_k=b_k+2c_{k+1}-c_k.$$
Bunun geçerli olması için negatif olmaması gerekir; yani
$$c_k\le 2c_{k+1}+b_k.$$
Şimdi \(F_k(c)\), \(n\)'in en düşük \(k\) bitini doğru üretip \(k\). bite \(c\) elde ile ulaşan yol sayısı olsun. O zaman \(k\ge 1\) için
$$F_{k+1}(u)=\sum_{c=0}^{2u+b_k}F_k(c)$$
olur. En düşük bitten sonra, çıkış eldesi sabitlenince tam olarak bir seçim vardır; dolayısıyla
$$F_1(c)=1\qquad(c\ge 0).$$
Bu yüzden en düşük bit ayrıca özel işleme ihtiyaç duymaz: \(p(2m)\) ve \(p(2m+1)\) aynı başlangıç elde polinomundan başlar.
Bu özyineleme, \(2u+b_k\) noktasında değerlendirilen bir ön-ek toplamıdır. Başlangıç fonksiyonu sabit olduğu için her adım polinom derecesini en fazla \(1\) artırır. Böylece \(F_k(c)\) her zaman en çok \(k-1\) dereceli bir polinomdur.
Uygulama bu polinomu
$$\binom{c}{0},\binom{c}{1},\binom{c}{2},\dots$$
tabanında saklar:
$$F_k(c)=\sum_{j=0}^{k-1}A_{k,j}\binom{c}{j}.$$
Bu taban çok uygundur; çünkü hockey-stick özdeşliği
$$\sum_{c=0}^{M}\binom{c}{j}=\binom{M+1}{j+1}$$
hemen çalışır. Açılımı özyinelemeye yerleştirince
$$F_{k+1}(u)=\sum_{j=0}^{k-1}A_{k,j}\binom{2u+b_k+1}{j+1}$$
elde edilir. Yani artık sorun, \((A_{k,0},\dots,A_{k,k-1})\) katsayı vektöründen bir sonraki vektörü hızlı üretmektir.
Eğer güncel bit \(b_k=0\) ise
$$F_{k+1}(u)=\sum_{j=0}^{k-1}A_{k,j}\binom{2u+1}{j+1}.$$
Pascal özdeşliği
$$\binom{2u+1}{j+1}=\binom{2u}{j+1}+\binom{2u}{j}$$
kullanılırsa ve ara katsayılar
$$B_r=A_{k,r}+A_{k,r-1}$$
şeklinde tanımlanırsa, burada geçerli aralık dışındaki terimler \(0\) alınır, o zaman
$$F_{k+1}(u)=\sum_{r=0}^{k}B_r\binom{2u}{r}$$
olur. Şimdi \(\binom{2u}{r}\) ifadesini tekrar \(\binom{u}{j}\) tabanına dönüştürmek gerekir. Bunun için
$$\sum_{r\ge 0}\binom{2u}{r}t^r=(1+t)^{2u}=((1+t)^2)^u=(1+2t+t^2)^u$$
yazılır. Yeniden açarsak
$$ (1+2t+t^2)^u=\sum_{j\ge 0}\binom{u}{j}(2t+t^2)^j=\sum_{j\ge 0}\binom{u}{j}\sum_{m=0}^{j}\binom{j}{m}2^{j-m}t^{j+m}. $$
Böylece \(\binom{2u}{j+m}\) içindeki \(\binom{u}{j}\) katsayısı
$$w_j(m)=\binom{j}{m}2^{j-m}$$
olur. Sonraki katsayı vektörü de
$$A_{k+1,j}=\sum_{m\ge 0} B_{j+m}\,w_j(m)$$
şeklinde yazılır. Gerçek sonlu dizilerde toplamın üst sınırı
$$m_{\max}=\min(j,\;k-j)$$
olur.
Eğer güncel bit \(b_k=1\) ise
$$F_{k+1}(u)=\sum_{j=0}^{k-1}A_{k,j}\binom{2u+2}{j+1}.$$
Yine Pascal kullanılır:
$$\binom{2u+2}{j+1}=\binom{2u+1}{j+1}+\binom{2u+1}{j}.$$
Böylece aynı ara katsayılar \(B_r\) ile
$$F_{k+1}(u)=\sum_{r=0}^{k}B_r\binom{2u+1}{r}$$
elde edilir. Ayrıca
$$\binom{2u+1}{r}=\binom{2u}{r}+\binom{2u}{r-1}$$
olduğundan bit \(1\) için çekirdek, bit \(0\) çekirdeğinin komşu iki teriminin toplamıdır:
$$w^{(1)}_j(m)=w_j(m)+w_j(m-1),$$
burada \(w_j(m)\), \(m<0\) veya \(m>j\) olduğunda \(0\) kabul edilir. Dolayısıyla
$$A_{k+1,j}=\sum_{m\ge 0} B_{j+m}\,w^{(1)}_j(m)$$
olur. Uygulamadaki gerçek üst sınır ise
$$m_{\max}=\min(j+1,\;k-j)$$
şeklindedir.
Tüm \(L\) bit işlendiğinde en üst bitten sonraya elde taşınamaz. Bu yüzden istenen değer
$$p(n)=F_L(0)$$
olur. Binom tabanında bu çok basittir:
$$F_L(0)=\sum_{j=0}^{L-1}A_{L,j}\binom{0}{j}=A_{L,0},$$
çünkü \(\binom{0}{0}=1\) ve \(j>0\) için \(\binom{0}{j}=0\). Bu nedenle uygulama son durum vektörünün ilk katsayısını döndürür.
\(n=7=111_2\) olsun. Başlangıçta
$$F_1(c)=1$$
vardır. İkinci bit \(1\) olduğu için
$$F_2(u)=\sum_{c=0}^{2u+1}1=2u+2.$$
Binom tabanında bu
$$F_2(u)=2\binom{u}{0}+2\binom{u}{1}$$
demektir. Üçüncü bit yine \(1\) olduğundan
$$F_3(u)=\sum_{c=0}^{2u+1}(2c+2)=(2u+2)(2u+3)=4u^2+10u+6.$$
Bunu binom tabanına geri yazınca
$$F_3(u)=6\binom{u}{0}+14\binom{u}{1}+8\binom{u}{2}$$
elde edilir. Sonuç olarak
$$p(7)=F_3(0)=6,$$
ki bu hem bilinen değerle hem de uygulamadaki kontrol noktasıyla aynıdır.
C++, Python ve Java uygulamaları aynı bit-DP formülünü hedefler. C++ ve Java uygulamaları önce \(n\)'i en düşük bitten en yüksek bite doğru ikili basamaklara ayırır. Ardından \(10^9+7\) modunda \(2\) kuvvetleri, Pascal katsayıları ve güncel bitin \(0\) ya da \(1\) olmasına göre iki alt üçgensel geçiş tablosu önceden hesaplanır.
Çalışan durum, \(F_k(c)\)'nin \(\binom{c}{j}\) tabanındaki katsayı listesidir. Her yeni bitte uygulama önce \(B_r=A_r+A_{r-1}\) Pascal adımını uygular, sonra uygun çekirdekle konvolüsyon yapar. C++ uygulaması dış katsayı aralığını birden fazla iş parçacığına bölerek hızlanabilir; Java uygulaması aynı aritmetiği tek iş parçacığında yürütür.
Python uygulaması ise ince bir çalıştırma köprüsüdür: gerektiğinde C++ çözücüsünü derler, çalıştırır ve standart çıktıdan sayısal cevabı ayıklar. Üç dilde de yayımlanan sonuç, en yüksek bit işlendiğinde elde edilen ilk katsayıdır.
\(L=\lfloor\log_2 n\rfloor+1\) olsun. \(2\) kuvvetlerini, Pascal katsayılarını ve iki üçgensel geçiş tablosunu hazırlamak \(O(L^2)\) zaman ve \(O(L^2)\) bellek gerektirir. \(k\). aşamada konvolüsyon \(\Theta(k^2)\) adet katsayı çifti inceler; dolayısıyla tüm dinamik programın zamanı
$$\sum_{k=1}^{L-1}\Theta(k^2)=\Theta(L^3)$$
olur. C++ tarafındaki isteğe bağlı paralelleştirme pratik süreyi azaltır ama asimptotik sınırı değiştirmez.
Sea \(p(n)\) el número de maneras de escribir \(n\) como suma de potencias de \(2\), permitiendo repetir cada potencia cuantas veces se quiera. El Problema 890 pide calcular
$$p\left(7^{777}\right)\pmod{10^9+7}.$$
La función generadora clásica es
$$\prod_{j\ge 0}\frac{1}{1-x^{2^j}}=\sum_{n\ge 0}p(n)x^n.$$
Como \(7^{777}\) es gigantesco, no sirve un método que recorra todos los valores hasta \(n\). La solución lee los bits de \(n\) y cuenta patrones de acarreo válidos. Así, el costo depende de la longitud binaria de \(n\), no de su magnitud numérica.
La observación central es que una partición binaria puede procesarse bit a bit. En cada posición solo importa cuántos términos de menor peso se emparejaron y produjeron un acarreo hacia la siguiente posición.
Escribamos
$$n=\sum_{k=0}^{L-1} b_k2^k,\qquad b_k\in\{0,1\}.$$
Si una partición usa \(x_k\) copias de \(2^k\), al reagrupar pares de términos \(2^k\) en un término \(2^{k+1}\) se obtiene
$$x_k+c_k=b_k+2c_{k+1},$$
donde \(c_k\) es el acarreo que entra al bit \(k\), y \(c_{k+1}\) el que sale. Fijados \(c_k\) y \(c_{k+1}\), solo hay un posible valor de \(x_k\):
$$x_k=b_k+2c_{k+1}-c_k.$$
Ese valor es válido exactamente cuando no es negativo, es decir, cuando
$$c_k\le 2c_{k+1}+b_k.$$
Definamos ahora \(F_k(c)\) como el número de formas de satisfacer los \(k\) bits menos significativos de \(n\) y terminar con acarreo \(c\) hacia el bit \(k\). Entonces, para \(k\ge 1\),
$$F_{k+1}(u)=\sum_{c=0}^{2u+b_k}F_k(c).$$
Después del bit menos significativo siempre hay exactamente una opción una vez fijado el acarreo saliente, por lo que
$$F_1(c)=1\qquad(c\ge 0).$$
Eso también explica por qué el bit menos significativo no necesita un tratamiento especial más adelante: tanto \(p(2m)\) como \(p(2m+1)\) parten del mismo polinomio inicial de acarreo.
La recurrencia es una suma prefija evaluada en \(2u+b_k\). Como se parte de la constante \(F_1(c)=1\), cada paso aumenta el grado a lo sumo en \(1\). Por tanto, \(F_k(c)\) siempre es un polinomio de grado a lo sumo \(k-1\).
La implementación almacena ese polinomio en la base
$$\binom{c}{0},\binom{c}{1},\binom{c}{2},\dots$$
de modo que
$$F_k(c)=\sum_{j=0}^{k-1}A_{k,j}\binom{c}{j}.$$
Esta base es especialmente conveniente por la identidad del palo de hockey:
$$\sum_{c=0}^{M}\binom{c}{j}=\binom{M+1}{j+1}.$$
Sustituyendo en la recurrencia se obtiene
$$F_{k+1}(u)=\sum_{j=0}^{k-1}A_{k,j}\binom{2u+b_k+1}{j+1}.$$
Así, el problema queda reducido a transformar eficientemente el vector de coeficientes \((A_{k,0},\dots,A_{k,k-1})\) en el siguiente.
Si \(b_k=0\), entonces
$$F_{k+1}(u)=\sum_{j=0}^{k-1}A_{k,j}\binom{2u+1}{j+1}.$$
Usando la identidad de Pascal,
$$\binom{2u+1}{j+1}=\binom{2u}{j+1}+\binom{2u}{j}.$$
Si definimos coeficientes intermedios por
$$B_r=A_{k,r}+A_{k,r-1},$$
tomando \(0\) fuera del rango válido, queda
$$F_{k+1}(u)=\sum_{r=0}^{k}B_r\binom{2u}{r}.$$
Ahora hay que volver a expandir \(\binom{2u}{r}\) en la base \(\binom{u}{j}\). Partimos de
$$\sum_{r\ge 0}\binom{2u}{r}t^r=(1+t)^{2u}=((1+t)^2)^u=(1+2t+t^2)^u.$$
Desarrollando otra vez,
$$ (1+2t+t^2)^u=\sum_{j\ge 0}\binom{u}{j}(2t+t^2)^j=\sum_{j\ge 0}\binom{u}{j}\sum_{m=0}^{j}\binom{j}{m}2^{j-m}t^{j+m}. $$
Por consiguiente, el coeficiente de \(\binom{u}{j}\) dentro de \(\binom{2u}{j+m}\) es
$$w_j(m)=\binom{j}{m}2^{j-m}.$$
La actualización queda entonces
$$A_{k+1,j}=\sum_{m\ge 0} B_{j+m}\,w_j(m).$$
En los arreglos finitos de la implementación, la suma termina en
$$m_{\max}=\min(j,\;k-j).$$
Si \(b_k=1\), tenemos
$$F_{k+1}(u)=\sum_{j=0}^{k-1}A_{k,j}\binom{2u+2}{j+1}.$$
Una vez más, por Pascal,
$$\binom{2u+2}{j+1}=\binom{2u+1}{j+1}+\binom{2u+1}{j},$$
de modo que reaparecen los mismos coeficientes intermedios \(B_r\) y
$$F_{k+1}(u)=\sum_{r=0}^{k}B_r\binom{2u+1}{r}.$$
Usamos ahora
$$\binom{2u+1}{r}=\binom{2u}{r}+\binom{2u}{r-1}.$$
Eso significa que el núcleo para bit \(1\) es la suma de dos núcleos vecinos del caso bit \(0\):
$$w^{(1)}_j(m)=w_j(m)+w_j(m-1),$$
donde \(w_j(m)=0\) cuando \(m<0\) o \(m>j\). Así,
$$A_{k+1,j}=\sum_{m\ge 0} B_{j+m}\,w^{(1)}_j(m).$$
En la implementación real, el límite superior es
$$m_{\max}=\min(j+1,\;k-j).$$
Después de procesar los \(L\) bits, no puede quedar ningún acarreo más allá del bit más significativo. Por lo tanto, la cantidad buscada es
$$p(n)=F_L(0).$$
En la base binomial esto es especialmente simple:
$$F_L(0)=\sum_{j=0}^{L-1}A_{L,j}\binom{0}{j}=A_{L,0},$$
porque \(\binom{0}{0}=1\) y \(\binom{0}{j}=0\) para todo \(j>0\). Por eso la implementación devuelve el primer coeficiente del último vector de estado.
Tomemos \(n=7=111_2\). Empezamos con
$$F_1(c)=1.$$
El segundo bit es \(1\), así que
$$F_2(u)=\sum_{c=0}^{2u+1}1=2u+2.$$
En base binomial,
$$F_2(u)=2\binom{u}{0}+2\binom{u}{1}.$$
El tercer bit también es \(1\), por lo tanto
$$F_3(u)=\sum_{c=0}^{2u+1}(2c+2)=(2u+2)(2u+3)=4u^2+10u+6.$$
Reexpresando en la base binomial se obtiene
$$F_3(u)=6\binom{u}{0}+14\binom{u}{1}+8\binom{u}{2}.$$
En consecuencia,
$$p(7)=F_3(0)=6,$$
que coincide con el valor conocido y con el punto de comprobación de la implementación.
Las implementaciones en C++, Python y Java siguen la misma DP sobre bits. Las versiones en C++ y Java convierten primero \(n\) en su representación binaria desde el bit menos significativo hasta el más significativo. Luego precalculan potencias de \(2\) módulo \(10^9+7\), coeficientes binomiales módulo \(10^9+7\) y dos tablas triangulares inferiores para las transiciones correspondientes a un bit actual igual a \(0\) o a \(1\).
El estado activo es la lista de coeficientes de \(F_k(c)\) en la base \(\binom{c}{j}\). Para cada nuevo bit, la implementación aplica primero el paso de Pascal \(B_r=A_r+A_{r-1}\) y después ejecuta la convolución adecuada con el núcleo precalculado. La implementación en C++ puede repartir el rango exterior de coeficientes entre varios hilos; la implementación en Java realiza la misma aritmética en serie.
La implementación en Python es un puente de ejecución: compila y ejecuta el solver en C++ cuando hace falta y luego extrae la salida numérica. En los tres lenguajes, la respuesta publicada es el primer coeficiente una vez procesado el bit más significativo.
Sea \(L=\lfloor\log_2 n\rfloor+1\). Precalcular las potencias de \(2\), los coeficientes de Pascal y las dos tablas triangulares de transición cuesta \(O(L^2)\) tiempo y \(O(L^2)\) memoria. En la etapa \(k\), la convolución visita \(\Theta(k^2)\) pares de coeficientes, de modo que la DP completa cuesta
$$\sum_{k=1}^{L-1}\Theta(k^2)=\Theta(L^3)$$
tiempo. El paralelismo opcional de la versión en C++ mejora el tiempo real de ejecución, pero no cambia la cota asintótica.
设 \(p(n)\) 表示把整数 \(n\) 写成若干个 \(2\) 的幂之和的方法数，并且每个 \(2^k\) 都可以重复使用任意次。第 890 题要求计算
$$p\left(7^{777}\right)\pmod{10^9+7}.$$
经典生成函数是
$$\prod_{j\ge 0}\frac{1}{1-x^{2^j}}=\sum_{n\ge 0}p(n)x^n.$$
由于 \(7^{777}\) 大到无法直接按数值大小做递推，程序并不是从 \(0\) 累加到 \(n\)。它真正做的是读取 \(n\) 的二进制表示，并在每一位上统计可能的进位模式。这样，算法规模只和 \(n\) 的二进制长度有关，而不和 \(n\) 本身的数值大小成正比。
核心思想是把“二进制拆分”理解成一个逐位处理的进位过程。每一位只需要知道：更低位的若干个小幂次项两两合并之后，向当前位一共送来了多少进位。
把 \(n\) 写成二进制：
$$n=\sum_{k=0}^{L-1} b_k2^k,\qquad b_k\in\{0,1\}.$$
设某个拆分中用了 \(x_k\) 个 \(2^k\)。把两个 \(2^k\) 合并成一个 \(2^{k+1}\) 之后，在第 \(k\) 位会出现下面的平衡关系：
$$x_k+c_k=b_k+2c_{k+1},$$
其中 \(c_k\) 是进入第 \(k\) 位的进位，\(c_{k+1}\) 是离开第 \(k\) 位、流向更高一位的进位。对固定的 \(c_k\) 和 \(c_{k+1}\)，\(x_k\) 没有自由度，只能取
$$x_k=b_k+2c_{k+1}-c_k.$$
因此它可行当且仅当非负，即
$$c_k\le 2c_{k+1}+b_k.$$
定义 \(F_k(c)\) 为“恰好处理完 \(n\) 的最低 \(k\) 个二进制位，并且向第 \(k\) 位留下进位 \(c\) 的方法数”。那么对于 \(k\ge 1\)，有
$$F_{k+1}(u)=\sum_{c=0}^{2u+b_k}F_k(c).$$
最低位处理完以后，只要输出进位固定，就总有且仅有一种选择，所以
$$F_1(c)=1\qquad(c\ge 0).$$
这也解释了为什么实现里不需要对最低位单独做复杂分支：\(p(2m)\) 与 \(p(2m+1)\) 都从同一个初始进位多项式开始。
上面的递推本质上是“前缀和之后，再在 \(2u+b_k\) 处求值”。从常数函数 \(F_1(c)=1\) 出发，每做一步，多项式次数最多增加 \(1\)。因此 \(F_k(c)\) 总是一个次数不超过 \(k-1\) 的多项式。
实现没有把它存在普通幂基底 \(1,c,c^2,\dots\) 中，而是存在更适合求和的二项式基底中：
$$\binom{c}{0},\binom{c}{1},\binom{c}{2},\dots$$
也就是说
$$F_k(c)=\sum_{j=0}^{k-1}A_{k,j}\binom{c}{j}.$$
之所以这样选，是因为这里恰好能直接使用 hockey-stick 恒等式：
$$\sum_{c=0}^{M}\binom{c}{j}=\binom{M+1}{j+1}.$$
把这个展开代回递推式，就得到
$$F_{k+1}(u)=\sum_{j=0}^{k-1}A_{k,j}\binom{2u+b_k+1}{j+1}.$$
于是问题变成了：给定当前系数向量 \((A_{k,0},\dots,A_{k,k-1})\)，如何快速求出下一层的系数向量。
若当前二进制位 \(b_k=0\)，则
$$F_{k+1}(u)=\sum_{j=0}^{k-1}A_{k,j}\binom{2u+1}{j+1}.$$
利用 Pascal 恒等式
$$\binom{2u+1}{j+1}=\binom{2u}{j+1}+\binom{2u}{j},$$
并定义中间系数
$$B_r=A_{k,r}+A_{k,r-1},$$
其中越界项按 \(0\) 处理，就可以写成
$$F_{k+1}(u)=\sum_{r=0}^{k}B_r\binom{2u}{r}.$$
接下来要把 \(\binom{2u}{r}\) 再写回 \(\binom{u}{j}\) 的基底。观察生成函数：
$$\sum_{r\ge 0}\binom{2u}{r}t^r=(1+t)^{2u}=((1+t)^2)^u=(1+2t+t^2)^u.$$
继续展开：
$$ (1+2t+t^2)^u=\sum_{j\ge 0}\binom{u}{j}(2t+t^2)^j=\sum_{j\ge 0}\binom{u}{j}\sum_{m=0}^{j}\binom{j}{m}2^{j-m}t^{j+m}. $$
因此，在 \(\binom{2u}{j+m}\) 中，\(\binom{u}{j}\) 的系数正是
$$w_j(m)=\binom{j}{m}2^{j-m}.$$
于是下一层系数满足
$$A_{k+1,j}=\sum_{m\ge 0} B_{j+m}\,w_j(m).$$
在实现所使用的有限数组里，求和实际上只需要做到
$$m_{\max}=\min(j,\;k-j).$$
若当前位 \(b_k=1\)，则
$$F_{k+1}(u)=\sum_{j=0}^{k-1}A_{k,j}\binom{2u+2}{j+1}.$$
再次使用 Pascal 恒等式：
$$\binom{2u+2}{j+1}=\binom{2u+1}{j+1}+\binom{2u+1}{j}.$$
所以仍然会出现同一组中间系数 \(B_r\)，并得到
$$F_{k+1}(u)=\sum_{r=0}^{k}B_r\binom{2u+1}{r}.$$
而
$$\binom{2u+1}{r}=\binom{2u}{r}+\binom{2u}{r-1}$$
说明：位 \(1\) 的转移核，只是位 \(0\) 的转移核与它左边一项的和，也就是
$$w^{(1)}_j(m)=w_j(m)+w_j(m-1),$$
其中 \(w_j(m)\) 在 \(m<0\) 或 \(m>j\) 时视为 \(0\)。因此
$$A_{k+1,j}=\sum_{m\ge 0} B_{j+m}\,w^{(1)}_j(m).$$
在实际数组中，上界变成
$$m_{\max}=\min(j+1,\;k-j).$$
当全部 \(L\) 位都处理完成后，最高位之上不能再有进位，因此目标值就是
$$p(n)=F_L(0).$$
在二项式基底中，这一步尤其简单：
$$F_L(0)=\sum_{j=0}^{L-1}A_{L,j}\binom{0}{j}=A_{L,0},$$
因为 \(\binom{0}{0}=1\)，而所有 \(j>0\) 时 \(\binom{0}{j}=0\)。这就是为什么实现最终只返回最后一个状态向量的首项。
取 \(n=7=111_2\)。初始时
$$F_1(c)=1.$$
第二位是 \(1\)，因此
$$F_2(u)=\sum_{c=0}^{2u+1}1=2u+2.$$
写成二项式基底就是
$$F_2(u)=2\binom{u}{0}+2\binom{u}{1}.$$
第三位仍然是 \(1\)，于是
$$F_3(u)=\sum_{c=0}^{2u+1}(2c+2)=(2u+2)(2u+3)=4u^2+10u+6.$$
再换回二项式基底，可得
$$F_3(u)=6\binom{u}{0}+14\binom{u}{1}+8\binom{u}{2}.$$
所以
$$p(7)=F_3(0)=6,$$
这与已知值一致，也与实现中的校验点一致。
C++、Python 和 Java 三种实现都围绕同一个按位动态规划。C++ 与 Java 实现会先把 \(n\) 转成从低位到高位的二进制数组，然后预先计算三类数据：模 \(10^9+7\) 的 \(2\) 的幂、模 \(10^9+7\) 的 Pascal 系数，以及分别对应当前位为 \(0\) 和 \(1\) 的两张下三角转移表。
运行中的状态就是 \(F_k(c)\) 在基底 \(\binom{c}{j}\) 下的系数向量。每处理一个新比特，程序先做一次 Pascal 型更新 \(B_r=A_r+A_{r-1}\)，再与对应的预计算转移核做卷积。C++ 实现可以把外层系数区间拆给多个线程并行处理；Java 实现使用同样的公式串行计算。
Python 实现本身并不重写这套数学，而是作为一个轻量桥接层：需要时编译并运行 C++ 求解器，再把标准输出里的数值答案提取出来。三种语言最终公开的结果，都是处理完最高位之后得到的首个系数。
设 \(L=\lfloor\log_2 n\rfloor+1\)。预计算 \(2\) 的幂、Pascal 系数和两张三角形转移表需要 \(O(L^2)\) 时间与 \(O(L^2)\) 空间。处理第 \(k\) 层时，卷积会访问 \(\Theta(k^2)\) 个系数组合，因此整个按位 DP 的总时间为
$$\sum_{k=1}^{L-1}\Theta(k^2)=\Theta(L^3).$$
C++ 版本的多线程只会改善实际运行时间，不会改变这个渐近复杂度。
Пусть \(p(n)\) обозначает число способов представить \(n\) в виде суммы степеней двойки, где каждую степень можно использовать неограниченно много раз. В задаче 890 требуется найти
$$p\left(7^{777}\right)\pmod{10^9+7}.$$
Классическая производящая функция имеет вид
$$\prod_{j\ge 0}\frac{1}{1-x^{2^j}}=\sum_{n\ge 0}p(n)x^n.$$
Поскольку число \(7^{777}\) колоссально, прямой перебор до \(n\) невозможен. Реальное решение читает двоичную запись \(n\) и считает допустимые схемы переносов между разрядами. Поэтому сложность зависит только от длины двоичной записи, а не от самого значения \(n\).
Главная идея состоит в том, чтобы рассматривать бинарное разбиение по битам. В каждом разряде важно знать только одно: сколько более мелких слагаемых попарно объединились и дали перенос в следующий разряд.
Пусть
$$n=\sum_{k=0}^{L-1} b_k2^k,\qquad b_k\in\{0,1\}.$$
Если в разбиении используется \(x_k\) копий числа \(2^k\), то после склеивания каждой пары \(2^k\) в одно \(2^{k+1}\) получаем баланс
$$x_k+c_k=b_k+2c_{k+1},$$
где \(c_k\) — перенос, входящий в бит \(k\), а \(c_{k+1}\) — перенос, выходящий из него. При фиксированных \(c_k\) и \(c_{k+1}\) значение \(x_k\) определяется однозначно:
$$x_k=b_k+2c_{k+1}-c_k.$$
Оно допустимо тогда и только тогда, когда неотрицательно, то есть
$$c_k\le 2c_{k+1}+b_k.$$
Теперь определим \(F_k(c)\) как число способов корректно обработать младшие \(k\) битов числа \(n\) и оставить перенос \(c\) в бит \(k\). Тогда при \(k\ge 1\)
$$F_{k+1}(u)=\sum_{c=0}^{2u+b_k}F_k(c).$$
После младшего бита для любого фиксированного выходного переноса существует ровно один вариант, поэтому
$$F_1(c)=1\qquad(c\ge 0).$$
Это же объясняет, почему младший бит не требует отдельной сложной обработки: и \(p(2m)\), и \(p(2m+1)\) стартуют с одного и того же начального полинома переносов.
Рекурсия выше — это префиксная сумма, вычисленная в точке \(2u+b_k\). Начиная с константы \(F_1(c)=1\), на каждом шаге степень увеличивается не более чем на \(1\). Значит, \(F_k(c)\) всегда является полиномом степени не выше \(k-1\).
В реализации этот полином хранится не в базисе \(1,c,c^2,\dots\), а в базисе
$$\binom{c}{0},\binom{c}{1},\binom{c}{2},\dots$$
то есть
$$F_k(c)=\sum_{j=0}^{k-1}A_{k,j}\binom{c}{j}.$$
Этот базис удобен благодаря тождеству hockey-stick:
$$\sum_{c=0}^{M}\binom{c}{j}=\binom{M+1}{j+1}.$$
Подстановка в рекурсию даёт
$$F_{k+1}(u)=\sum_{j=0}^{k-1}A_{k,j}\binom{2u+b_k+1}{j+1}.$$
Значит, задача сводится к эффективному переходу от вектора коэффициентов \((A_{k,0},\dots,A_{k,k-1})\) к следующему такому вектору.
Если текущий бит равен \(0\), то
$$F_{k+1}(u)=\sum_{j=0}^{k-1}A_{k,j}\binom{2u+1}{j+1}.$$
По формуле Паскаля
$$\binom{2u+1}{j+1}=\binom{2u}{j+1}+\binom{2u}{j}.$$
Если ввести промежуточные коэффициенты
$$B_r=A_{k,r}+A_{k,r-1},$$
с нулём вне допустимого диапазона, то получим
$$F_{k+1}(u)=\sum_{r=0}^{k}B_r\binom{2u}{r}.$$
Теперь нужно снова разложить \(\binom{2u}{r}\) по базису \(\binom{u}{j}\). Рассмотрим производящую функцию:
$$\sum_{r\ge 0}\binom{2u}{r}t^r=(1+t)^{2u}=((1+t)^2)^u=(1+2t+t^2)^u.$$
Раскрывая скобки ещё раз, получаем
$$ (1+2t+t^2)^u=\sum_{j\ge 0}\binom{u}{j}(2t+t^2)^j=\sum_{j\ge 0}\binom{u}{j}\sum_{m=0}^{j}\binom{j}{m}2^{j-m}t^{j+m}. $$
Следовательно, коэффициент при \(\binom{u}{j}\) внутри \(\binom{2u}{j+m}\) равен
$$w_j(m)=\binom{j}{m}2^{j-m}.$$
Отсюда получаем переход
$$A_{k+1,j}=\sum_{m\ge 0} B_{j+m}\,w_j(m).$$
В конечных массивах реализации верхний предел суммы равен
$$m_{\max}=\min(j,\;k-j).$$
Если текущий бит равен \(1\), то
$$F_{k+1}(u)=\sum_{j=0}^{k-1}A_{k,j}\binom{2u+2}{j+1}.$$
Снова используем формулу Паскаля:
$$\binom{2u+2}{j+1}=\binom{2u+1}{j+1}+\binom{2u+1}{j}.$$
Тогда появляются те же промежуточные коэффициенты \(B_r\), и
$$F_{k+1}(u)=\sum_{r=0}^{k}B_r\binom{2u+1}{r}.$$
Но
$$\binom{2u+1}{r}=\binom{2u}{r}+\binom{2u}{r-1},$$
поэтому ядро для бита \(1\) — это сумма двух соседних ядер случая бита \(0\):
$$w^{(1)}_j(m)=w_j(m)+w_j(m-1),$$
где \(w_j(m)=0\) при \(m<0\) или \(m>j\). Следовательно,
$$A_{k+1,j}=\sum_{m\ge 0} B_{j+m}\,w^{(1)}_j(m).$$
В реальных массивах верхняя граница становится
$$m_{\max}=\min(j+1,\;k-j).$$
После обработки всех \(L\) битов переносов выше старшего бита быть не должно. Значит, искомое число равно
$$p(n)=F_L(0).$$
В биномиальном базисе это особенно просто:
$$F_L(0)=\sum_{j=0}^{L-1}A_{L,j}\binom{0}{j}=A_{L,0},$$
так как \(\binom{0}{0}=1\), а \(\binom{0}{j}=0\) для всех \(j>0\). Именно поэтому реализация возвращает первый коэффициент последнего вектора состояния.
Возьмём \(n=7=111_2\). Начинаем с
$$F_1(c)=1.$$
Второй бит равен \(1\), следовательно
$$F_2(u)=\sum_{c=0}^{2u+1}1=2u+2.$$
В биномиальном базисе это
$$F_2(u)=2\binom{u}{0}+2\binom{u}{1}.$$
Третий бит тоже равен \(1\), поэтому
$$F_3(u)=\sum_{c=0}^{2u+1}(2c+2)=(2u+2)(2u+3)=4u^2+10u+6.$$
Переходя обратно к биномиальному базису, получаем
$$F_3(u)=6\binom{u}{0}+14\binom{u}{1}+8\binom{u}{2}.$$
Следовательно,
$$p(7)=F_3(0)=6,$$
что совпадает и с известным значением, и с контрольной проверкой реализации.
Реализации на C++, Python и Java используют одну и ту же побитовую динамику. Реализации на C++ и Java сначала переводят \(n\) в двоичный вид от младшего бита к старшему. Затем заранее вычисляются степени двойки по модулю \(10^9+7\), биномиальные коэффициенты по модулю \(10^9+7\) и две нижнетреугольные таблицы переходов для случая, когда текущий бит равен \(0\) или \(1\).
Текущее состояние — это вектор коэффициентов полинома \(F_k(c)\) в базисе \(\binom{c}{j}\). Для каждого нового бита реализация сначала выполняет шаг Паскаля \(B_r=A_r+A_{r-1}\), а затем свёртку с нужным заранее подготовленным ядром. В версии на C++ внешний диапазон коэффициентов можно разделить между несколькими потоками, тогда как версия на Java выполняет те же вычисления последовательно.
Реализация на Python является тонким мостом запуска: при необходимости она компилирует и запускает решатель на C++, а затем извлекает числовой ответ из стандартного вывода. Во всех трёх случаях публикуемый результат — это первый коэффициент после обработки старшего бита.
Пусть \(L=\lfloor\log_2 n\rfloor+1\). Предварительное вычисление степеней двойки, коэффициентов Паскаля и двух треугольных таблиц переходов требует \(O(L^2)\) времени и \(O(L^2)\) памяти. На шаге \(k\) свёртка рассматривает \(\Theta(k^2)\) пар коэффициентов, поэтому вся динамика требует
$$\sum_{k=1}^{L-1}\Theta(k^2)=\Theta(L^3)$$
времени. Параллелизм в версии на C++ ускоряет практическое выполнение, но не меняет асимптотическую оценку.
لنرمز بـ \(p(n)\) إلى عدد الطرق التي يمكن بها كتابة \(n\) على صورة مجموع لقوى العدد \(2\)، مع السماح بتكرار كل قوة عددًا غير محدود من المرات. المطلوب في المسألة 890 هو حساب
$$p\left(7^{777}\right)\pmod{10^9+7}.$$
دالة التوليد الكلاسيكية هي
$$\prod_{j\ge 0}\frac{1}{1-x^{2^j}}=\sum_{n\ge 0}p(n)x^n.$$
وبما أن \(7^{777}\) عدد هائل جدًا، فلا يمكن بناء الحل عبر التدرج العددي حتى \(n\). ما تفعله الخوارزمية فعليًا هو قراءة التمثيل الثنائي للعدد \(n\) وحساب أنماط الحمل الممكنة بين البتات. لذلك فإن حجم العمل يعتمد على عدد البتات فقط، لا على القيمة العددية نفسها.
الفكرة الأساسية هي النظر إلى التقسيمات الثنائية بتةً بتة. في كل موضع ثنائي لا نحتاج إلا إلى معرفة عدد الحدود الأصغر التي تجمعت في أزواج وولدت حملًا إلى الموضع التالي.
نكتب
$$n=\sum_{k=0}^{L-1} b_k2^k,\qquad b_k\in\{0,1\}.$$
إذا استُخدم \(x_k\) مرة من الحد \(2^k\) في أحد التقسيمات، فإن جمع كل زوج من حدود \(2^k\) في حد واحد من نوع \(2^{k+1}\) يعطي معادلة التوازن
$$x_k+c_k=b_k+2c_{k+1},$$
حيث \(c_k\) هو الحمل الداخل إلى البت \(k\)، و\(c_{k+1}\) هو الحمل الخارج منها. وعند تثبيت \(c_k\) و\(c_{k+1}\) لا يبقى أمام \(x_k\) إلا قيمة واحدة هي
$$x_k=b_k+2c_{k+1}-c_k.$$
وتكون هذه القيمة صالحة إذا وفقط إذا كانت غير سالبة، أي إذا تحقق
$$c_k\le 2c_{k+1}+b_k.$$
الآن نعرّف \(F_k(c)\) بأنه عدد الطرق التي تحقق أقل \(k\) بتات من \(n\) وتنتهي بحمل مقداره \(c\) داخل البت \(k\). عندئذٍ، لكل \(k\ge 1\)،
$$F_{k+1}(u)=\sum_{c=0}^{2u+b_k}F_k(c).$$
بعد معالجة أقل بت، يوجد دائمًا اختيار واحد فقط متى ثبت الحمل الخارج، ولذلك
$$F_1(c)=1\qquad(c\ge 0).$$
وهذا يفسر أيضًا لماذا لا تحتاج الخوارزمية إلى معالجة خاصة للبت الأقل وزنًا: فكل من \(p(2m)\) و\(p(2m+1)\) يبدأ من متعدد الحدود الابتدائي نفسه للحمل.
العلاقة السابقة هي مجموع تراكمي يُقيَّم عند \(2u+b_k\). وبما أننا نبدأ من الدالة الثابتة \(F_1(c)=1\)، فإن درجة كثير الحدود تزداد بمقدار لا يتجاوز \(1\) في كل خطوة. لذا فإن \(F_k(c)\) يكون دائمًا كثير حدود من درجة لا تتجاوز \(k-1\).
التنفيذ لا يخزن هذا الكثير في الأساس المعتاد \(1,c,c^2,\dots\)، بل في الأساس
$$\binom{c}{0},\binom{c}{1},\binom{c}{2},\dots$$
أي على الصورة
$$F_k(c)=\sum_{j=0}^{k-1}A_{k,j}\binom{c}{j}.$$
هذا الاختيار مناسب جدًا لأن هوية hockey-stick تعطي مباشرة
$$\sum_{c=0}^{M}\binom{c}{j}=\binom{M+1}{j+1}.$$
وبالتعويض في العلاقة التكرارية نحصل على
$$F_{k+1}(u)=\sum_{j=0}^{k-1}A_{k,j}\binom{2u+b_k+1}{j+1}.$$
وهكذا تصبح المسألة هي: كيف نحول متجه المعاملات \((A_{k,0},\dots,A_{k,k-1})\) بسرعة إلى متجه المعاملات التالي.
إذا كانت \(b_k=0\)، فلدينا
$$F_{k+1}(u)=\sum_{j=0}^{k-1}A_{k,j}\binom{2u+1}{j+1}.$$
وباستخدام هوية باسكال
$$\binom{2u+1}{j+1}=\binom{2u}{j+1}+\binom{2u}{j},$$
ثم تعريف معاملات وسيطة بالشكل
$$B_r=A_{k,r}+A_{k,r-1},$$
مع اعتبار القيم خارج المجال المسموح مساوية للصفر، نحصل على
$$F_{k+1}(u)=\sum_{r=0}^{k}B_r\binom{2u}{r}.$$
يبقى الآن أن نعيد كتابة \(\binom{2u}{r}\) في الأساس \(\binom{u}{j}\). نبدأ من
$$\sum_{r\ge 0}\binom{2u}{r}t^r=(1+t)^{2u}=((1+t)^2)^u=(1+2t+t^2)^u.$$
وبتوسيع الطرف الأخير مرة أخرى نحصل على
$$ (1+2t+t^2)^u=\sum_{j\ge 0}\binom{u}{j}(2t+t^2)^j=\sum_{j\ge 0}\binom{u}{j}\sum_{m=0}^{j}\binom{j}{m}2^{j-m}t^{j+m}. $$
إذًا فإن معامل \(\binom{u}{j}\) داخل \(\binom{2u}{j+m}\) يساوي
$$w_j(m)=\binom{j}{m}2^{j-m}.$$
ومن ثم يصبح التحديث
$$A_{k+1,j}=\sum_{m\ge 0} B_{j+m}\,w_j(m).$$
وفي المصفوفات المحدودة التي يستخدمها التنفيذ، يتوقف الجمع عند
$$m_{\max}=\min(j,\;k-j).$$
إذا كانت \(b_k=1\)، فإن
$$F_{k+1}(u)=\sum_{j=0}^{k-1}A_{k,j}\binom{2u+2}{j+1}.$$
وباستخدام باسكال مرة أخرى،
$$\binom{2u+2}{j+1}=\binom{2u+1}{j+1}+\binom{2u+1}{j}.$$
فتظهر معاملات \(B_r\) نفسها، ويصبح
$$F_{k+1}(u)=\sum_{r=0}^{k}B_r\binom{2u+1}{r}.$$
لكن
$$\binom{2u+1}{r}=\binom{2u}{r}+\binom{2u}{r-1},$$
وهذا يعني أن نواة الانتقال للبت \(1\) ليست إلا مجموع نواتين متجاورتين من حالة البت \(0\):
$$w^{(1)}_j(m)=w_j(m)+w_j(m-1),$$
مع اعتبار \(w_j(m)=0\) إذا كان \(m<0\) أو \(m>j\). لذلك
$$A_{k+1,j}=\sum_{m\ge 0} B_{j+m}\,w^{(1)}_j(m).$$
وفي التنفيذ الفعلي يصبح الحد الأعلى
$$m_{\max}=\min(j+1,\;k-j).$$
بعد الانتهاء من معالجة جميع \(L\) بتات، لا يجوز أن يبقى حمل بعد البت الأعلى. لذلك تكون القيمة المطلوبة هي
$$p(n)=F_L(0).$$
وفي الأساس ذي الحدود الثنائية يصبح هذا مباشرًا جدًا:
$$F_L(0)=\sum_{j=0}^{L-1}A_{L,j}\binom{0}{j}=A_{L,0},$$
لأن \(\binom{0}{0}=1\) بينما \(\binom{0}{j}=0\) لكل \(j>0\). ولهذا تعيد الخوارزمية أول معامل في آخر متجه حالة.
لنأخذ \(n=7=111_2\). نبدأ من
$$F_1(c)=1.$$
البِت الثانية تساوي \(1\)، ومن ثم
$$F_2(u)=\sum_{c=0}^{2u+1}1=2u+2.$$
وفي الأساس الثنائي الحدين نكتب ذلك بالشكل
$$F_2(u)=2\binom{u}{0}+2\binom{u}{1}.$$
والبت الثالثة أيضًا تساوي \(1\)، لذا
$$F_3(u)=\sum_{c=0}^{2u+1}(2c+2)=(2u+2)(2u+3)=4u^2+10u+6.$$
وبإعادته إلى الأساس نفسه نحصل على
$$F_3(u)=6\binom{u}{0}+14\binom{u}{1}+8\binom{u}{2}.$$
إذًا
$$p(7)=F_3(0)=6,$$
وهو تمامًا القيمة المعروفة، كما أنه يطابق نقطة التحقق المستخدمة في التنفيذ.
تستخدم تطبيقات C++ وPython وJava الصيغة نفسها للديناميكية على مستوى البتات. تنفذ نسختا C++ وJava أولًا تحويل \(n\) إلى قائمة من البتات من الأقل وزنًا إلى الأعلى، ثم تجهزان مسبقًا ثلاث مجموعات من البيانات: قوى \(2\) بترديد \(10^9+7\)، ومعاملات باسكال بالترديد نفسه، وجدولين مثلثيين سفليين للانتقال في حال كانت البت الحالية \(0\) أو \(1\).
الحالة الجارية هي متجه معاملات كثير الحدود \(F_k(c)\) في الأساس \(\binom{c}{j}\). عند كل بت جديدة، يطبّق التنفيذ أولًا خطوة باسكال \(B_r=A_r+A_{r-1}\)، ثم يجري التفافًا مع النواة المناسبة التي حُسبت مسبقًا. ويمكن لنسخة C++ أن تقسّم المجال الخارجي للمعاملات على عدة خيوط، بينما تنفذ نسخة Java الحساب نفسه بشكل تسلسلي.
أما تطبيق Python فهو مجرد جسر تشغيل خفيف: عند الحاجة يقوم ببناء مشغّل C++ وتنفيذه، ثم يستخرج الجواب العددي من المخرجات القياسية. وفي جميع اللغات تكون النتيجة المنشورة هي أول معامل بعد إنهاء معالجة البت الأعلى.
إذا كان \(L=\lfloor\log_2 n\rfloor+1\)، فإن التحضير المسبق لقوى \(2\) ومعاملات باسكال وجدولي الانتقال المثلثيين يحتاج إلى \(O(L^2)\) زمنًا و\(O(L^2)\) ذاكرة. وفي المرحلة \(k\)، يزور الالتفاف \(\Theta(k^2)\) أزواجًا من المعاملات، لذلك يكون الزمن الكلي للديناميكية
$$\sum_{k=1}^{L-1}\Theta(k^2)=\Theta(L^3).$$
التنفيذ المتوازي الاختياري في نسخة C++ يحسن الزمن العملي، لكنه لا يغير الحدّ الأسيمي.