A partition of \(n\) is called special when every part is distinct and every even part is divisible by \(4\). Equivalently, the allowed part sizes are all odd numbers together with multiples of \(4\), while numbers congruent to \(2 \pmod 4\) are forbidden. If \(P(n)\) denotes the number of such partitions, the task is to compute
$$S(10^7)=\sum_{n=1}^{10^7} P(n)\pmod{10^9+7}.$$
A direct dynamic program over all allowed parts works for small checks but is too slow for \(10^7\). The implemented solution rewrites the generating function into a product whose coefficients can be obtained from a square-based recurrence and a prefix count of generalized hexagonal numbers.
Let \(M=10^9+7\). The key is to express the special-partition generating function in a form where one factor advances in steps of \(4\), and the other factor is just a sparse indicator series.
Because parts are distinct, each allowed size \(m\) contributes a factor \(1+q^m\). Since the allowed parts are \(4r-3\), \(4r-1\), and \(4r\), we get
$$F(q)=\sum_{n\ge 0} P(n) q^n=\prod_{r\ge 1}(1+q^{4r-3})(1+q^{4r-1})(1+q^{4r}).$$
This already encodes the whole problem, but extracting all coefficients up to \(10^7\) directly is still expensive.
Jacobi's triple product gives the identity
$$\sum_{t\in\mathbb Z} q^{t(2t-1)}=\prod_{r\ge 1}(1-q^{4r})(1+q^{4r-1})(1+q^{4r-3}).$$
The exponents \(t(2t-1)\) are the generalized hexagonal numbers:
$$\mathcal H=\{t(2t-1): t\in\mathbb Z\}=\{0,1,3,6,10,15,21,\dots\}.$$
Dividing the original product by the factor \(\prod_{r\ge 1}(1-q^{4r})\) isolates the remaining contribution of the multiples of \(4\):
$$F(q)=\left(\prod_{r\ge 1}\frac{1+q^{4r}}{1-q^{4r}}\right)\left(\sum_{t\in\mathbb Z} q^{t(2t-1)}\right).$$
Now define
$$A(x)=\prod_{r\ge 1}\frac{1+x^r}{1-x^r}=\sum_{k\ge 0} a_k x^k.$$
Then the special-partition series becomes
$$F(q)=\left(\sum_{k\ge 0} a_k q^{4k}\right)\left(\sum_{t\in\mathbb Z} q^{t(2t-1)}\right).$$
The reciprocal Jacobi theta identity says
$$1+2\sum_{m\ge 1}(-1)^m x^{m^2}=\prod_{r\ge 1}(1-x^{2r})(1-x^{2r-1})^2.$$
On the other hand, for each \(r\),
$$\frac{1+x^r}{1-x^r}=\frac{1-x^{2r}}{(1-x^r)^2}.$$
Multiplying over all \(r\) shows that
$$A(x)=\frac{1}{1+2\sum_{m\ge 1}(-1)^m x^{m^2}}.$$
Therefore
$$A(x)\left(1+2\sum_{m\ge 1}(-1)^m x^{m^2}\right)=1.$$
Comparing coefficients of \(x^n\) yields
$$a_0=1,$$
$$a_n+2\sum_{m^2\le n}(-1)^m a_{n-m^2}=0 \qquad (n\ge 1),$$
so
$$a_n=2\sum_{m^2\le n}(-1)^{m+1} a_{n-m^2}\pmod M.$$
This is exactly the recurrence used by the implementation.
Let
$$H(T)=\#\{h\in\mathcal H: h\le T\}.$$
Since
$$F(q)=\left(\sum_{k\ge 0} a_k q^{4k}\right)\left(\sum_{h\in\mathcal H} q^h\right),$$
the coefficient of \(q^n\) is
$$P(n)=\sum_{\substack{k\ge 0,\ h\in\mathcal H\\ 4k+h=n}} a_k.$$
Summing this for \(0\le n\le N\) gives
$$\sum_{n=0}^{N} P(n)=\sum_{k=0}^{\lfloor N/4\rfloor} a_k\,H(N-4k).$$
The term \(P(0)=1\) is the empty partition, which must be excluded because the problem starts at \(1\). Hence
$$\boxed{S(N)=\sum_{k=0}^{\lfloor N/4\rfloor} a_k\,H(N-4k)-1 \pmod M.}$$
The generalized hexagonal numbers up to \(10\) are
$$\mathcal H\cap[0,10]=\{0,1,3,6,10\},$$
so \(H(10)=5\), \(H(6)=4\), and \(H(2)=2\).
From the recurrence,
$$a_0=1,\qquad a_1=2,\qquad a_2=4.$$
Therefore
$$S(10)=a_0H(10)+a_1H(6)+a_2H(2)-1=1\cdot 5+2\cdot 4+4\cdot 2-1=20.$$
Indeed, the first ten values are
$$\bigl(P(1),P(2),\dots,P(10)\bigr)=(1,0,1,2,2,1,2,4,4,3),$$
and their sum is \(20\).
The C++, Python, and Java implementations all follow the same mathematical pipeline. First they compute the coefficient table \(a_k\) up to \(\lfloor N/4\rfloor\). To do that efficiently, they precompute all squares \(m^2\le \lfloor N/4\rfloor\) and apply the alternating recurrence above.
Next they mark every generalized hexagonal number \(t(2t-1)\le N\), which is the same as marking both \(n(2n-1)\) and \(n(2n+1)\) for positive \(n\), together with \(0\). A prefix-sum array then turns each query \(H(T)\) into \(O(1)\) time.
Finally they evaluate
$$\sum_{k=0}^{\lfloor N/4\rfloor} a_k\,H(N-4k)-1 \pmod M$$
in one pass. No large two-dimensional partition table is needed; all heavy work is compressed into a one-dimensional recurrence plus a sparse counting array.
Let \(K=\lfloor N/4\rfloor\). Building the coefficient table requires, for each \(n\le K\), iterating over all squares up to \(n\), so the time cost is
$$O\!\left(\sum_{n=1}^{K}\sqrt{n}\right)=O(K\sqrt{K}).$$
Marking generalized hexagonal numbers takes \(O(\sqrt{N})\) updates, building the prefix array takes \(O(N)\), and the final accumulation takes \(O(K)\). Thus the total running time is dominated by \(O(K\sqrt{K})=O(N^{3/2})\), while memory usage is \(O(N)\) because the prefix array over \(0,\dots,N\) is the largest structure.
Eine Partition von \(n\) heißt speziell, wenn alle Teile verschieden sind und jeder gerade Teil durch \(4\) teilbar ist. Erlaubt sind also alle ungeraden Zahlen sowie Vielfache von \(4\), während Zahlen der Form \(4k+2\) ausgeschlossen sind. Mit \(P(n)\) als Anzahl solcher Partitionen ist gesucht:
$$S(10^7)=\sum_{n=1}^{10^7} P(n)\pmod{10^9+7}.$$
Ein direktes dynamisches Programm genügt für kleine Tests, ist aber für \(10^7\) zu langsam. Die implementierte Methode zerlegt deshalb die erzeugende Funktion in einen Faktor mit Schrittweite \(4\) und in eine dünne Reihe über verallgemeinerte hexagonale Zahlen.
Sei \(M=10^9+7\). Ziel ist eine Darstellung, bei der die Koeffizienten durch eine Rekursion über Quadratzahlen und eine Präfixzählung berechnet werden können.
Da jeder erlaubte Teil wegen der Verschiedenheit entweder vorkommt oder nicht vorkommt, liefert jede erlaubte Zahl \(m\) den Faktor \(1+q^m\). Mit den erlaubten Klassen \(4r-3\), \(4r-1\) und \(4r\) folgt
$$F(q)=\sum_{n\ge 0} P(n) q^n=\prod_{r\ge 1}(1+q^{4r-3})(1+q^{4r-1})(1+q^{4r}).$$
Diese Formel ist korrekt, aber zum direkten Auslesen aller Koeffizienten bis \(10^7\) noch unhandlich.
Das Jacobi-Dreifachprodukt liefert die Identität
$$\sum_{t\in\mathbb Z} q^{t(2t-1)}=\prod_{r\ge 1}(1-q^{4r})(1+q^{4r-1})(1+q^{4r-3}).$$
Die Exponenten \(t(2t-1)\) sind die verallgemeinerten hexagonalen Zahlen:
$$\mathcal H=\{t(2t-1): t\in\mathbb Z\}=\{0,1,3,6,10,15,21,\dots\}.$$
Damit lässt sich die ursprüngliche Produktform umschreiben zu
$$F(q)=\left(\prod_{r\ge 1}\frac{1+q^{4r}}{1-q^{4r}}\right)\left(\sum_{t\in\mathbb Z} q^{t(2t-1)}\right).$$
Wir definieren
$$A(x)=\prod_{r\ge 1}\frac{1+x^r}{1-x^r}=\sum_{k\ge 0} a_k x^k.$$
Dann gilt
$$F(q)=\left(\sum_{k\ge 0} a_k q^{4k}\right)\left(\sum_{t\in\mathbb Z} q^{t(2t-1)}\right).$$
Die reziproke Theta-Identität lautet
$$1+2\sum_{m\ge 1}(-1)^m x^{m^2}=\prod_{r\ge 1}(1-x^{2r})(1-x^{2r-1})^2.$$
Außerdem gilt für jedes \(r\)
$$\frac{1+x^r}{1-x^r}=\frac{1-x^{2r}}{(1-x^r)^2}.$$
Nach dem Produkt über alle \(r\) folgt daher
$$A(x)=\frac{1}{1+2\sum_{m\ge 1}(-1)^m x^{m^2}}.$$
Also
$$A(x)\left(1+2\sum_{m\ge 1}(-1)^m x^{m^2}\right)=1.$$
Durch Koeffizientenvergleich erhält man
$$a_0=1,$$
$$a_n+2\sum_{m^2\le n}(-1)^m a_{n-m^2}=0 \qquad (n\ge 1),$$
also
$$a_n=2\sum_{m^2\le n}(-1)^{m+1} a_{n-m^2}\pmod M.$$
Genau diese Rekursion verwenden die Implementierungen.
Setze
$$H(T)=\#\{h\in\mathcal H: h\le T\}.$$
Aus
$$F(q)=\left(\sum_{k\ge 0} a_k q^{4k}\right)\left(\sum_{h\in\mathcal H} q^h\right)$$
folgt für den Koeffizienten von \(q^n\)
$$P(n)=\sum_{\substack{k\ge 0,\ h\in\mathcal H\\ 4k+h=n}} a_k.$$
Summiert man über \(0\le n\le N\), so ergibt sich
$$\sum_{n=0}^{N} P(n)=\sum_{k=0}^{\lfloor N/4\rfloor} a_k\,H(N-4k).$$
Da \(P(0)=1\) die leere Partition zählt, muss sie am Ende entfernt werden. Somit
$$\boxed{S(N)=\sum_{k=0}^{\lfloor N/4\rfloor} a_k\,H(N-4k)-1 \pmod M.}$$
Bis \(10\) sind die verallgemeinerten hexagonalen Zahlen
$$\mathcal H\cap[0,10]=\{0,1,3,6,10\},$$
also \(H(10)=5\), \(H(6)=4\) und \(H(2)=2\).
Aus der Rekursion folgen
$$a_0=1,\qquad a_1=2,\qquad a_2=4.$$
Daher ist
$$S(10)=a_0H(10)+a_1H(6)+a_2H(2)-1=1\cdot 5+2\cdot 4+4\cdot 2-1=20.$$
Tatsächlich lauten die ersten zehn Werte
$$\bigl(P(1),P(2),\dots,P(10)\bigr)=(1,0,1,2,2,1,2,4,4,3),$$
und ihre Summe ist \(20\).
Die C++-, Python- und Java-Implementierungen folgen demselben Rechengang. Zuerst wird die Tabelle der Koeffizienten \(a_k\) bis \(\lfloor N/4\rfloor\) aufgebaut. Dazu werden alle Quadratzahlen \(m^2\le \lfloor N/4\rfloor\) vorab gespeichert und in der alternierenden Rekursion verwendet.
Anschließend werden alle verallgemeinerten hexagonalen Zahlen \(t(2t-1)\le N\) markiert, also äquivalent \(n(2n-1)\) und \(n(2n+1)\) für positive \(n\) sowie \(0\). Eine Präfixsumme über dieses Markierungsarray liefert danach jeden Wert \(H(T)\) in konstanter Zeit.
Zum Schluss wird
$$\sum_{k=0}^{\lfloor N/4\rfloor} a_k\,H(N-4k)-1 \pmod M$$
in einem einzigen Durchlauf akkumuliert. Eine große zweidimensionale Partitionstabelle ist dadurch nicht nötig.
Mit \(K=\lfloor N/4\rfloor\) kostet der Aufbau der Koeffiziententabelle
$$O\!\left(\sum_{n=1}^{K}\sqrt{n}\right)=O(K\sqrt{K})$$
Zeit, weil für jedes \(n\) alle Quadrate bis \(n\) betrachtet werden. Das Markieren der verallgemeinerten hexagonalen Zahlen benötigt \(O(\sqrt{N})\) Aktualisierungen, die Präfixsumme \(O(N)\) und die Endsumme \(O(K)\). Insgesamt dominiert also \(O(K\sqrt{K})=O(N^{3/2})\), während der Speicherverbrauch \(O(N)\) ist, da das Präfixarray über \(0,\dots,N\) die größte Struktur darstellt.
Bir \(n\) partition'ı, tüm parçalar birbirinden farklıysa ve her çift parça \(4\)'e bölünebiliyorsa özeldir. Başka bir deyişle, izin verilen parça boyları tüm tek sayılar ile \(4\)'ün katlarıdır; \(4k+2\) biçimindeki sayılar yasaktır. \(P(n)\) bu tür partition sayısı olmak üzere istenen değer
$$S(10^7)=\sum_{n=1}^{10^7} P(n)\pmod{10^9+7}.$$
Küçük sınırlar için doğrudan dinamik programlama yapılabilir, fakat \(10^7\) için yavaştır. Uygulanan yöntem bu nedenle üretici fonksiyonu, biri \(4\) adımlı bir seri, diğeri de seyrek bir genelleştirilmiş altıgensel sayı serisi olacak şekilde ayırır.
\(M=10^9+7\) olsun. Amaç, katsayıları kare tabanlı bir özyineleme ve bir prefix sayımı ile çıkarılabilecek bir ayrışım elde etmektir.
Parçalar farklı olmak zorunda olduğundan, izin verilen her \(m\) boyu için katkı \(1+q^m\) olur. İzin verilen sınıflar \(4r-3\), \(4r-1\) ve \(4r\) olduğundan
$$F(q)=\sum_{n\ge 0} P(n) q^n=\prod_{r\ge 1}(1+q^{4r-3})(1+q^{4r-1})(1+q^{4r}).$$
Bu formül problemi tam olarak ifade eder; ancak \(10^7\)'ye kadar bütün katsayıları doğrudan çıkarmak pratik değildir.
Jacobi üçlü çarpımı şu özdeşliği verir:
$$\sum_{t\in\mathbb Z} q^{t(2t-1)}=\prod_{r\ge 1}(1-q^{4r})(1+q^{4r-1})(1+q^{4r-3}).$$
\(t(2t-1)\) üsleri genelleştirilmiş altıgensel sayılardır:
$$\mathcal H=\{t(2t-1): t\in\mathbb Z\}=\{0,1,3,6,10,15,21,\dots\}.$$
Böylece başlangıçtaki çarpım
$$F(q)=\left(\prod_{r\ge 1}\frac{1+q^{4r}}{1-q^{4r}}\right)\left(\sum_{t\in\mathbb Z} q^{t(2t-1)}\right)$$
şeklinde yazılır. Şimdi
$$A(x)=\prod_{r\ge 1}\frac{1+x^r}{1-x^r}=\sum_{k\ge 0} a_k x^k$$
tanımını yaparsak
$$F(q)=\left(\sum_{k\ge 0} a_k q^{4k}\right)\left(\sum_{t\in\mathbb Z} q^{t(2t-1)}\right)$$
elde edilir.
Karşılıklı theta özdeşliği şudur:
$$1+2\sum_{m\ge 1}(-1)^m x^{m^2}=\prod_{r\ge 1}(1-x^{2r})(1-x^{2r-1})^2.$$
Ayrıca her \(r\) için
$$\frac{1+x^r}{1-x^r}=\frac{1-x^{2r}}{(1-x^r)^2}$$
olduğundan, tüm \(r\)'ler üzerinde çarpınca
$$A(x)=\frac{1}{1+2\sum_{m\ge 1}(-1)^m x^{m^2}}$$
sonucuna ulaşılır. Dolayısıyla
$$A(x)\left(1+2\sum_{m\ge 1}(-1)^m x^{m^2}\right)=1.$$
Katsayıları karşılaştırırsak
$$a_0=1,$$
$$a_n+2\sum_{m^2\le n}(-1)^m a_{n-m^2}=0 \qquad (n\ge 1),$$
yani
$$a_n=2\sum_{m^2\le n}(-1)^{m+1} a_{n-m^2}\pmod M.$$
Uygulama tam olarak bu özyinelemeyi kullanır.
Şunu tanımlayalım:
$$H(T)=\#\{h\in\mathcal H: h\le T\}.$$
Çünkü
$$F(q)=\left(\sum_{k\ge 0} a_k q^{4k}\right)\left(\sum_{h\in\mathcal H} q^h\right),$$
\(q^n\)'in katsayısı
$$P(n)=\sum_{\substack{k\ge 0,\ h\in\mathcal H\\ 4k+h=n}} a_k$$
olur. Bunu \(0\le n\le N\) için toplarsak
$$\sum_{n=0}^{N} P(n)=\sum_{k=0}^{\lfloor N/4\rfloor} a_k\,H(N-4k)$$
elde edilir. Buradaki \(P(0)=1\) boş partition'ı temsil eder; problem \(1\)'den başladığı için çıkarmalıyız:
$$\boxed{S(N)=\sum_{k=0}^{\lfloor N/4\rfloor} a_k\,H(N-4k)-1 \pmod M.}$$
\(10\)'a kadar olan genelleştirilmiş altıgensel sayılar
$$\mathcal H\cap[0,10]=\{0,1,3,6,10\}$$
olduğundan \(H(10)=5\), \(H(6)=4\) ve \(H(2)=2\) olur.
Özyinelemeden
$$a_0=1,\qquad a_1=2,\qquad a_2=4$$
bulunur. Bu durumda
$$S(10)=a_0H(10)+a_1H(6)+a_2H(2)-1=1\cdot 5+2\cdot 4+4\cdot 2-1=20.$$
Gerçekten de ilk on değer
$$\bigl(P(1),P(2),\dots,P(10)\bigr)=(1,0,1,2,2,1,2,4,4,3)$$
olup toplamları \(20\)'dir.
C++, Python ve Java implementasyonları aynı matematiksel akışı izler. Önce \(a_k\) katsayıları \(\lfloor N/4\rfloor\)'e kadar hesaplanır. Bunun için tüm kareler \(m^2\le \lfloor N/4\rfloor\) önceden hazırlanır ve yukarıdaki işaret değiştiren özyineleme uygulanır.
Daha sonra \(t(2t-1)\le N\) olan tüm genelleştirilmiş altıgensel sayılar işaretlenir; bu, pozitif \(n\) için \(n(2n-1)\) ve \(n(2n+1)\) değerlerini ve ayrıca \(0\)'ı işaretlemekle aynıdır. Bu işaret dizisinin prefix toplamı alındığında her \(H(T)\) sorgusu \(O(1)\) zamana iner.
Son aşamada
$$\sum_{k=0}^{\lfloor N/4\rfloor} a_k\,H(N-4k)-1 \pmod M$$
tek geçişte toplanır. Böylece büyük bir iki boyutlu partition tablosuna gerek kalmaz.
\(K=\lfloor N/4\rfloor\) olmak üzere katsayı tablosunu kurmak
$$O\!\left(\sum_{n=1}^{K}\sqrt{n}\right)=O(K\sqrt{K})$$
zaman alır; çünkü her \(n\) için \(n\)'den küçük eşit tüm kareler dolaşılır. Genelleştirilmiş altıgensel sayıların işaretlenmesi \(O(\sqrt{N})\), prefix dizisi \(O(N)\), son toplama da \(O(K)\) tutar. Toplam zaman maliyeti baskın olarak \(O(K\sqrt{K})=O(N^{3/2})\), bellek kullanımı ise \(0\) ile \(N\) arasındaki prefix dizisi nedeniyle \(O(N)\)'dir.
Una partición de \(n\) es especial si todas sus partes son distintas y toda parte par es divisible por \(4\). En otras palabras, se permiten todos los impares y los múltiplos de \(4\), mientras que los números congruentes con \(2 \pmod 4\) están prohibidos. Si \(P(n)\) denota la cantidad de estas particiones, hay que calcular
$$S(10^7)=\sum_{n=1}^{10^7} P(n)\pmod{10^9+7}.$$
Un programa dinámico directo sirve para verificaciones pequeñas, pero no para \(10^7\). La solución implementada reescribe la función generadora como el producto de una serie en pasos de \(4\) y una serie dispersa sobre números hexagonales generalizados.
Sea \(M=10^9+7\). La idea central es transformar la función generadora en una forma cuyos coeficientes puedan obtenerse mediante una recurrencia sobre cuadrados y un conteo prefijo.
Como las partes deben ser distintas, cada tamaño permitido \(m\) aporta un factor \(1+q^m\). Dado que las clases permitidas son \(4r-3\), \(4r-1\) y \(4r\), obtenemos
$$F(q)=\sum_{n\ge 0} P(n) q^n=\prod_{r\ge 1}(1+q^{4r-3})(1+q^{4r-1})(1+q^{4r}).$$
Esta expresión ya codifica el problema completo, pero sigue siendo costoso extraer todos los coeficientes hasta \(10^7\).
El triple producto de Jacobi da la identidad
$$\sum_{t\in\mathbb Z} q^{t(2t-1)}=\prod_{r\ge 1}(1-q^{4r})(1+q^{4r-1})(1+q^{4r-3}).$$
Los exponentes \(t(2t-1)\) son los números hexagonales generalizados:
$$\mathcal H=\{t(2t-1): t\in\mathbb Z\}=\{0,1,3,6,10,15,21,\dots\}.$$
Por lo tanto, la función generadora original puede escribirse como
$$F(q)=\left(\prod_{r\ge 1}\frac{1+q^{4r}}{1-q^{4r}}\right)\left(\sum_{t\in\mathbb Z} q^{t(2t-1)}\right).$$
Definimos ahora
$$A(x)=\prod_{r\ge 1}\frac{1+x^r}{1-x^r}=\sum_{k\ge 0} a_k x^k.$$
Entonces
$$F(q)=\left(\sum_{k\ge 0} a_k q^{4k}\right)\left(\sum_{t\in\mathbb Z} q^{t(2t-1)}\right).$$
La identidad theta recíproca dice
$$1+2\sum_{m\ge 1}(-1)^m x^{m^2}=\prod_{r\ge 1}(1-x^{2r})(1-x^{2r-1})^2.$$
Además, para cada \(r\),
$$\frac{1+x^r}{1-x^r}=\frac{1-x^{2r}}{(1-x^r)^2}.$$
Al multiplicar sobre todos los \(r\), se obtiene
$$A(x)=\frac{1}{1+2\sum_{m\ge 1}(-1)^m x^{m^2}}.$$
Por consiguiente,
$$A(x)\left(1+2\sum_{m\ge 1}(-1)^m x^{m^2}\right)=1.$$
Comparando coeficientes,
$$a_0=1,$$
$$a_n+2\sum_{m^2\le n}(-1)^m a_{n-m^2}=0 \qquad (n\ge 1),$$
y por tanto
$$a_n=2\sum_{m^2\le n}(-1)^{m+1} a_{n-m^2}\pmod M.$$
Esa es exactamente la recurrencia que usa la implementación.
Definimos
$$H(T)=\#\{h\in\mathcal H: h\le T\}.$$
Como
$$F(q)=\left(\sum_{k\ge 0} a_k q^{4k}\right)\left(\sum_{h\in\mathcal H} q^h\right),$$
el coeficiente de \(q^n\) es
$$P(n)=\sum_{\substack{k\ge 0,\ h\in\mathcal H\\ 4k+h=n}} a_k.$$
Si sumamos para \(0\le n\le N\), resulta
$$\sum_{n=0}^{N} P(n)=\sum_{k=0}^{\lfloor N/4\rfloor} a_k\,H(N-4k).$$
Aquí \(P(0)=1\) cuenta la partición vacía, que debe eliminarse porque el problema empieza en \(1\). Así,
$$\boxed{S(N)=\sum_{k=0}^{\lfloor N/4\rfloor} a_k\,H(N-4k)-1 \pmod M.}$$
Los números hexagonales generalizados no mayores que \(10\) son
$$\mathcal H\cap[0,10]=\{0,1,3,6,10\},$$
de modo que \(H(10)=5\), \(H(6)=4\) y \(H(2)=2\).
La recurrencia da
$$a_0=1,\qquad a_1=2,\qquad a_2=4.$$
Por tanto,
$$S(10)=a_0H(10)+a_1H(6)+a_2H(2)-1=1\cdot 5+2\cdot 4+4\cdot 2-1=20.$$
En efecto, los diez primeros valores son
$$\bigl(P(1),P(2),\dots,P(10)\bigr)=(1,0,1,2,2,1,2,4,4,3),$$
y su suma es \(20\).
Las implementaciones en C++, Python y Java siguen exactamente el mismo esquema matemático. Primero calculan la tabla de coeficientes \(a_k\) hasta \(\lfloor N/4\rfloor\). Para ello, precomputan todos los cuadrados \(m^2\le \lfloor N/4\rfloor\) y aplican la recurrencia alternante.
Después marcan cada número hexagonal generalizado \(t(2t-1)\le N\), lo que equivale a marcar \(n(2n-1)\) y \(n(2n+1)\) para \(n\ge 1\), además de \(0\). Un arreglo de prefijos convierte cada consulta \(H(T)\) en tiempo constante.
Finalmente evalúan
$$\sum_{k=0}^{\lfloor N/4\rfloor} a_k\,H(N-4k)-1 \pmod M$$
en una sola pasada. La ventaja es que no hace falta una tabla bidimensional de particiones.
Sea \(K=\lfloor N/4\rfloor\). Construir la tabla de coeficientes cuesta
$$O\!\left(\sum_{n=1}^{K}\sqrt{n}\right)=O(K\sqrt{K}),$$
porque para cada \(n\) se recorren todos los cuadrados no mayores que \(n\). Marcar los números hexagonales generalizados necesita \(O(\sqrt{N})\) actualizaciones, el arreglo de prefijos cuesta \(O(N)\), y la suma final cuesta \(O(K)\). En consecuencia, domina \(O(K\sqrt{K})=O(N^{3/2})\), mientras que la memoria es \(O(N)\) porque el arreglo prefijo sobre \(0,\dots,N\) es la estructura más grande.
如果一个 \(n\) 的拆分满足两条条件，就称为特殊拆分：第一，所有部件互不相同；第二，所有偶数部件都必须被 \(4\) 整除。也就是说，允许出现的部件只有所有奇数以及 \(4\) 的倍数，而形如 \(4k+2\) 的数全部禁止。记 \(P(n)\) 为 \(n\) 的特殊拆分个数，目标是计算
$$S(10^7)=\sum_{n=1}^{10^7} P(n)\pmod{10^9+7}.$$
如果直接做拆分型动态规划，小规模验证没有问题，但在 \(10^7\) 这个范围上会过慢。实现采用的真正思路是先把生成函数拆成两个因子：一个因子只在 \(4\) 的步长上出现系数，另一个因子则是广义六角数位置上的稀疏指示级数。
设模数 \(M=10^9+7\)。核心目标不是直接展开原始乘积，而是把它改写成“平方递推 + 前缀计数”都能处理的形式。
因为部件必须互异，所以每一个允许的部件大小 \(m\) 只会“选或不选”，对应因子 \(1+q^m\)。允许的三类部件正好是 \(4r-3\)、\(4r-1\) 和 \(4r\)，因此
$$F(q)=\sum_{n\ge 0} P(n) q^n=\prod_{r\ge 1}(1+q^{4r-3})(1+q^{4r-1})(1+q^{4r}).$$
这个公式已经完整描述了问题，但如果直接从它提取所有 \(n\le 10^7\) 的系数，成本仍然太高。
Jacobi 三重积给出恒等式
$$\sum_{t\in\mathbb Z} q^{t(2t-1)}=\prod_{r\ge 1}(1-q^{4r})(1+q^{4r-1})(1+q^{4r-3}).$$
这里的指数 \(t(2t-1)\) 正是广义六角数：
$$\mathcal H=\{t(2t-1): t\in\mathbb Z\}=\{0,1,3,6,10,15,21,\dots\}.$$
把这个恒等式代回去，原始生成函数就可以改写为
$$F(q)=\left(\prod_{r\ge 1}\frac{1+q^{4r}}{1-q^{4r}}\right)\left(\sum_{t\in\mathbb Z} q^{t(2t-1)}\right).$$
现在定义
$$A(x)=\prod_{r\ge 1}\frac{1+x^r}{1-x^r}=\sum_{k\ge 0} a_k x^k,$$
于是就得到
$$F(q)=\left(\sum_{k\ge 0} a_k q^{4k}\right)\left(\sum_{t\in\mathbb Z} q^{t(2t-1)}\right).$$
这一步非常重要，因为第二个因子变成了一个非常稀疏的级数，而第一个因子可以继续化成递推。
Jacobi theta 级数满足
$$1+2\sum_{m\ge 1}(-1)^m x^{m^2}=\prod_{r\ge 1}(1-x^{2r})(1-x^{2r-1})^2.$$
另一方面，对每个 \(r\) 都有
$$\frac{1+x^r}{1-x^r}=\frac{1-x^{2r}}{(1-x^r)^2}.$$
把它们对所有 \(r\) 相乘，就得到
$$A(x)=\frac{1}{1+2\sum_{m\ge 1}(-1)^m x^{m^2}}.$$
等价地，
$$A(x)\left(1+2\sum_{m\ge 1}(-1)^m x^{m^2}\right)=1.$$
对 \(x^n\) 比较系数可得
$$a_0=1,$$
$$a_n+2\sum_{m^2\le n}(-1)^m a_{n-m^2}=0 \qquad (n\ge 1),$$
因此
$$a_n=2\sum_{m^2\le n}(-1)^{m+1} a_{n-m^2}\pmod M.$$
实现中构造的系数表正是按这个递推式计算出来的。它只依赖于平方数，所以比直接处理全部部件要规整得多。
定义
$$H(T)=\#\{h\in\mathcal H: h\le T\}.$$
由于
$$F(q)=\left(\sum_{k\ge 0} a_k q^{4k}\right)\left(\sum_{h\in\mathcal H} q^h\right),$$
\(q^n\) 的系数就是
$$P(n)=\sum_{\substack{k\ge 0,\ h\in\mathcal H\\ 4k+h=n}} a_k.$$
把它对 \(0\le n\le N\) 求和，可以交换求和顺序，得到
$$\sum_{n=0}^{N} P(n)=\sum_{k=0}^{\lfloor N/4\rfloor} a_k\,H(N-4k).$$
这里包含了 \(P(0)=1\)，也就是空拆分。题目要的是从 \(1\) 到 \(N\) 的总和，所以最后还要减去这一项：
$$\boxed{S(N)=\sum_{k=0}^{\lfloor N/4\rfloor} a_k\,H(N-4k)-1 \pmod M.}$$
这就是实现最后执行的一维卷积公式。
不超过 \(10\) 的广义六角数是
$$\mathcal H\cap[0,10]=\{0,1,3,6,10\},$$
所以 \(H(10)=5\)、\(H(6)=4\)、\(H(2)=2\)。
递推的前几个值为
$$a_0=1,\qquad a_1=2,\qquad a_2=4.$$
于是
$$S(10)=a_0H(10)+a_1H(6)+a_2H(2)-1=1\cdot 5+2\cdot 4+4\cdot 2-1=20.$$
直接枚举时，前十项的特殊拆分个数确实为
$$\bigl(P(1),P(2),\dots,P(10)\bigr)=(1,0,1,2,2,1,2,4,4,3),$$
总和正好也是 \(20\)。这个例子说明公式与实际计数完全一致。
C++、Python 和 Java 实现遵循完全相同的数学流程。第一步是计算到 \(\lfloor N/4\rfloor\) 为止的系数表 \(a_k\)。为此，程序先预处理所有不超过 \(\lfloor N/4\rfloor\) 的平方数，然后按照上面的交替符号递推式逐项生成系数。
第二步是标记所有不超过 \(N\) 的广义六角数 \(t(2t-1)\)。在正整数参数下，这等价于同时标记 \(n(2n-1)\)、\(n(2n+1)\) 以及 \(0\)。接着对标记数组做一次前缀和，这样任意 \(H(T)\) 都能在 \(O(1)\) 时间内得到。
最后，程序只需要按顺序累加
$$\sum_{k=0}^{\lfloor N/4\rfloor} a_k\,H(N-4k)-1 \pmod M$$
即可。整个过程不再需要传统拆分问题中常见的二维状态表，内存和结构都更紧凑。
记 \(K=\lfloor N/4\rfloor\)。构造系数表时，对每个 \(n\le K\) 都要遍历不超过 \(n\) 的平方数，因此时间复杂度为
$$O\!\left(\sum_{n=1}^{K}\sqrt{n}\right)=O(K\sqrt{K}).$$
标记广义六角数只需要 \(O(\sqrt{N})\) 次更新，构造前缀和需要 \(O(N)\)，最终卷积求和需要 \(O(K)\)。所以总时间由 \(O(K\sqrt{K})=O(N^{3/2})\) 主导。空间方面，最大的结构是长度为 \(N+1\) 的前缀数组，因此空间复杂度为 \(O(N)\)。
Разбиение числа \(n\) называется специальным, если все части различны и каждая чётная часть делится на \(4\). Иначе говоря, разрешены все нечётные числа и кратные \(4\), а числа вида \(4k+2\) запрещены. Пусть \(P(n)\) обозначает число таких разбиений. Требуется вычислить
$$S(10^7)=\sum_{n=1}^{10^7} P(n)\pmod{10^9+7}.$$
Прямое динамическое программирование по допустимым частям годится лишь для маленьких проверок. Для \(10^7\) реализация использует другую идею: разлагает порождающую функцию на произведение ряда с шагом \(4\) и редкого ряда по обобщённым шестиугольным числам.
Обозначим \(M=10^9+7\). Нужно привести порождающую функцию к виду, где одна часть вычисляется через рекурсию по квадратам, а другая через префиксный подсчёт.
Так как части должны быть различны, каждый допустимый размер \(m\) даёт множитель \(1+q^m\). Допустимые классы равны \(4r-3\), \(4r-1\) и \(4r\), поэтому
$$F(q)=\sum_{n\ge 0} P(n) q^n=\prod_{r\ge 1}(1+q^{4r-3})(1+q^{4r-1})(1+q^{4r}).$$
Эта формула уже точна, но напрямую извлекать из неё все коэффициенты до \(10^7\) слишком дорого.
Тройное произведение Якоби даёт тождество
$$\sum_{t\in\mathbb Z} q^{t(2t-1)}=\prod_{r\ge 1}(1-q^{4r})(1+q^{4r-1})(1+q^{4r-3}).$$
Показатели \(t(2t-1)\) образуют множество обобщённых шестиугольных чисел:
$$\mathcal H=\{t(2t-1): t\in\mathbb Z\}=\{0,1,3,6,10,15,21,\dots\}.$$
Следовательно, исходную функцию можно переписать так:
$$F(q)=\left(\prod_{r\ge 1}\frac{1+q^{4r}}{1-q^{4r}}\right)\left(\sum_{t\in\mathbb Z} q^{t(2t-1)}\right).$$
Введём обозначение
$$A(x)=\prod_{r\ge 1}\frac{1+x^r}{1-x^r}=\sum_{k\ge 0} a_k x^k.$$
Тогда получаем
$$F(q)=\left(\sum_{k\ge 0} a_k q^{4k}\right)\left(\sum_{t\in\mathbb Z} q^{t(2t-1)}\right).$$
Для theta-ряда верно тождество
$$1+2\sum_{m\ge 1}(-1)^m x^{m^2}=\prod_{r\ge 1}(1-x^{2r})(1-x^{2r-1})^2.$$
Кроме того, для любого \(r\)
$$\frac{1+x^r}{1-x^r}=\frac{1-x^{2r}}{(1-x^r)^2}.$$
Перемножая по всем \(r\), получаем
$$A(x)=\frac{1}{1+2\sum_{m\ge 1}(-1)^m x^{m^2}}.$$
То есть
$$A(x)\left(1+2\sum_{m\ge 1}(-1)^m x^{m^2}\right)=1.$$
Сравнение коэффициентов даёт
$$a_0=1,$$
$$a_n+2\sum_{m^2\le n}(-1)^m a_{n-m^2}=0 \qquad (n\ge 1),$$
а значит
$$a_n=2\sum_{m^2\le n}(-1)^{m+1} a_{n-m^2}\pmod M.$$
Именно эта рекурсия используется в реализации для построения коэффициентов.
Определим
$$H(T)=\#\{h\in\mathcal H: h\le T\}.$$
Так как
$$F(q)=\left(\sum_{k\ge 0} a_k q^{4k}\right)\left(\sum_{h\in\mathcal H} q^h\right),$$
коэффициент при \(q^n\) равен
$$P(n)=\sum_{\substack{k\ge 0,\ h\in\mathcal H\\ 4k+h=n}} a_k.$$
Если просуммировать по всем \(0\le n\le N\), получится
$$\sum_{n=0}^{N} P(n)=\sum_{k=0}^{\lfloor N/4\rfloor} a_k\,H(N-4k).$$
Здесь присутствует \(P(0)=1\), то есть пустое разбиение. По условию его нужно исключить, поэтому
$$\boxed{S(N)=\sum_{k=0}^{\lfloor N/4\rfloor} a_k\,H(N-4k)-1 \pmod M.}$$
Обобщённые шестиугольные числа, не превосходящие \(10\), таковы:
$$\mathcal H\cap[0,10]=\{0,1,3,6,10\},$$
поэтому \(H(10)=5\), \(H(6)=4\) и \(H(2)=2\).
Из рекурсии получаем
$$a_0=1,\qquad a_1=2,\qquad a_2=4.$$
Тогда
$$S(10)=a_0H(10)+a_1H(6)+a_2H(2)-1=1\cdot 5+2\cdot 4+4\cdot 2-1=20.$$
Прямой подсчёт даёт первые десять значений
$$\bigl(P(1),P(2),\dots,P(10)\bigr)=(1,0,1,2,2,1,2,4,4,3),$$
и их сумма действительно равна \(20\).
Реализации на C++, Python и Java используют один и тот же вычислительный конвейер. Сначала строится таблица коэффициентов \(a_k\) до \(\lfloor N/4\rfloor\). Для этого заранее перечисляются все квадраты \(m^2\le \lfloor N/4\rfloor\), после чего применяется чередующаяся рекурсия.
Затем отмечаются все обобщённые шестиугольные числа \(t(2t-1)\le N\), что эквивалентно отметке значений \(n(2n-1)\), \(n(2n+1)\) и числа \(0\). По массиву отметок строится префиксная сумма, благодаря чему любой запрос \(H(T)\) обрабатывается за \(O(1)\).
После этого остаётся в один проход вычислить
$$\sum_{k=0}^{\lfloor N/4\rfloor} a_k\,H(N-4k)-1 \pmod M.$$
Большая двумерная таблица разбиений не нужна: вся тяжёлая работа сведена к одномерной рекурсии и редкому массиву отметок.
Пусть \(K=\lfloor N/4\rfloor\). Построение таблицы коэффициентов требует
$$O\!\left(\sum_{n=1}^{K}\sqrt{n}\right)=O(K\sqrt{K}),$$
поскольку для каждого \(n\) перебираются все квадраты, не превосходящие \(n\). Отметка обобщённых шестиугольных чисел занимает \(O(\sqrt{N})\) обновлений, построение префиксного массива занимает \(O(N)\), а финальное суммирование требует \(O(K)\). Следовательно, итоговое время доминируется членом \(O(K\sqrt{K})=O(N^{3/2})\), а память равна \(O(N)\), потому что самый большой объект — префиксный массив длины \(N+1\).
يُسمَّى تقسيم العدد \(n\) تقسيمًا خاصًا إذا كانت جميع الأجزاء مختلفة، وكان كل جزء زوجي قابلًا للقسمة على \(4\). وهذا يعني أن الأجزاء المسموح بها هي جميع الأعداد الفردية مع مضاعفات \(4\)، بينما تُمنع الأعداد من الشكل \(4k+2\). إذا رمزنا بعدد هذه التقسيمات بـ \(P(n)\)، فالمطلوب هو حساب
$$S(10^7)=\sum_{n=1}^{10^7} P(n)\pmod{10^9+7}.$$
يمكن استعمال برمجة ديناميكية مباشرة من أجل اختبارات صغيرة، لكنها تصبح بطيئة جدًا عند \(10^7\). لذلك تعيد الطريقة المطبقة كتابة دالة التوليد على صورة حاصل ضرب عاملين: عامل تظهر معاملاته كل \(4\) درجات، وعامل متفرق تدعمه الأعداد السداسية المعممة.
لنكتب \(M=10^9+7\). الفكرة الأساسية هي تحويل دالة التوليد إلى صيغة يمكن التعامل معها بواسطة علاقة عودية تعتمد على المربعات، مع عدٍّ تراكمي لمواضع متناثرة.
بما أن الأجزاء يجب أن تكون مميزة، فإن كل حجم مسموح \(m\) يساهم بالعامل \(1+q^m\). والأحجام المسموح بها تقع في الأصناف \(4r-3\) و\(4r-1\) و\(4r\)، لذلك نحصل على
$$F(q)=\sum_{n\ge 0} P(n) q^n=\prod_{r\ge 1}(1+q^{4r-3})(1+q^{4r-1})(1+q^{4r}).$$
هذه الصيغة تصف المسألة بالكامل، لكن استخراج جميع المعاملات حتى \(10^7\) مباشرةً يظل مكلفًا.
يعطي حاصل الضرب الثلاثي لجاكوبي الهوية
$$\sum_{t\in\mathbb Z} q^{t(2t-1)}=\prod_{r\ge 1}(1-q^{4r})(1+q^{4r-1})(1+q^{4r-3}).$$
الأسس \(t(2t-1)\) هي الأعداد السداسية المعممة:
$$\mathcal H=\{t(2t-1): t\in\mathbb Z\}=\{0,1,3,6,10,15,21,\dots\}.$$
ومن ثم يمكن إعادة كتابة دالة التوليد الأصلية بالشكل
$$F(q)=\left(\prod_{r\ge 1}\frac{1+q^{4r}}{1-q^{4r}}\right)\left(\sum_{t\in\mathbb Z} q^{t(2t-1)}\right).$$
نعرّف الآن
$$A(x)=\prod_{r\ge 1}\frac{1+x^r}{1-x^r}=\sum_{k\ge 0} a_k x^k.$$
وعندها تصبح
$$F(q)=\left(\sum_{k\ge 0} a_k q^{4k}\right)\left(\sum_{t\in\mathbb Z} q^{t(2t-1)}\right).$$
هذا التفكيك هو نقطة التحول الأساسية، لأن العامل الثاني يصبح متفرقًا جدًا، بينما العامل الأول يمكن حسابه بعلاقة عودية منتظمة.
لدينا هوية ثيتا التالية:
$$1+2\sum_{m\ge 1}(-1)^m x^{m^2}=\prod_{r\ge 1}(1-x^{2r})(1-x^{2r-1})^2.$$
ومن جهة أخرى، لكل \(r\) نجد أن
$$\frac{1+x^r}{1-x^r}=\frac{1-x^{2r}}{(1-x^r)^2}.$$
وبضرب هذه العلاقات على جميع القيم \(r\)، نحصل على
$$A(x)=\frac{1}{1+2\sum_{m\ge 1}(-1)^m x^{m^2}}.$$
أي إن
$$A(x)\left(1+2\sum_{m\ge 1}(-1)^m x^{m^2}\right)=1.$$
بمقارنة معاملات \(x^n\) نحصل على
$$a_0=1,$$
$$a_n+2\sum_{m^2\le n}(-1)^m a_{n-m^2}=0 \qquad (n\ge 1),$$
ومن ثم
$$a_n=2\sum_{m^2\le n}(-1)^{m+1} a_{n-m^2}\pmod M.$$
هذه بالضبط هي العلاقة العودية التي تعتمد عليها عملية البناء في التنفيذ.
لنعرّف
$$H(T)=\#\{h\in\mathcal H: h\le T\}.$$
وبما أن
$$F(q)=\left(\sum_{k\ge 0} a_k q^{4k}\right)\left(\sum_{h\in\mathcal H} q^h\right),$$
فإن معامل \(q^n\) يساوي
$$P(n)=\sum_{\substack{k\ge 0,\ h\in\mathcal H\\ 4k+h=n}} a_k.$$
وعند جمع هذه القيم من \(0\) حتى \(N\)، نحصل على
$$\sum_{n=0}^{N} P(n)=\sum_{k=0}^{\lfloor N/4\rfloor} a_k\,H(N-4k).$$
لكن \(P(0)=1\) يمثل التقسيم الفارغ، وهو غير مطلوب لأن السؤال يبدأ من \(1\). لذلك تكون الصيغة النهائية
$$\boxed{S(N)=\sum_{k=0}^{\lfloor N/4\rfloor} a_k\,H(N-4k)-1 \pmod M.}$$
الأعداد السداسية المعممة التي لا تتجاوز \(10\) هي
$$\mathcal H\cap[0,10]=\{0,1,3,6,10\},$$
وبالتالي \(H(10)=5\) و\(H(6)=4\) و\(H(2)=2\).
ومن العلاقة العودية نجد
$$a_0=1,\qquad a_1=2,\qquad a_2=4.$$
إذن
$$S(10)=a_0H(10)+a_1H(6)+a_2H(2)-1=1\cdot 5+2\cdot 4+4\cdot 2-1=20.$$
وبالعد المباشر تكون القيم العشر الأولى
$$\bigl(P(1),P(2),\dots,P(10)\bigr)=(1,0,1,2,2,1,2,4,4,3),$$
ومجموعها فعلًا هو \(20\).
تتبع تطبيقات C++ وPython وJava المسار الرياضي نفسه. في البداية تُبنى معاملات \(a_k\) حتى \(\lfloor N/4\rfloor\). ولتنفيذ ذلك بكفاءة، تُحضَّر جميع المربعات \(m^2\le \lfloor N/4\rfloor\) مسبقًا، ثم تُطبَّق العلاقة العودية ذات الإشارات المتناوبة.
بعد ذلك تُعلَّم كل قيمة من الشكل \(t(2t-1)\le N\)، وهو ما يكافئ تعليم القيم \(n(2n-1)\) و\(n(2n+1)\) للأعداد الصحيحة الموجبة، مع تعليم \(0\) أيضًا. وبعد بناء مصفوفة سوابق تراكمية لهذه العلامات، يصبح الحصول على أي قيمة \(H(T)\) ممكنًا في زمن ثابت.
أخيرًا يُحسب المقدار
$$\sum_{k=0}^{\lfloor N/4\rfloor} a_k\,H(N-4k)-1 \pmod M$$
في مرور واحد فقط. وبهذا لا حاجة إلى جدول ثنائي الأبعاد كبير كما في الكثير من مسائل التقسيم التقليدية.
إذا وضعنا \(K=\lfloor N/4\rfloor\)، فإن بناء جدول المعاملات يحتاج إلى
$$O\!\left(\sum_{n=1}^{K}\sqrt{n}\right)=O(K\sqrt{K}),$$
لأن كل \(n\) يمر على جميع المربعات التي لا تتجاوزه. أما تعليم الأعداد السداسية المعممة فيحتاج إلى \(O(\sqrt{N})\) تحديثات، وبناء مصفوفة السوابق يحتاج إلى \(O(N)\)، والجمع النهائي يحتاج إلى \(O(K)\). لذلك يهيمن الحد \(O(K\sqrt{K})=O(N^{3/2})\) على زمن التنفيذ الكلي، بينما يساوي استهلاك الذاكرة \(O(N)\) لأن أكبر بنية هي مصفوفة السوابق ذات الطول \(N+1\).