Let \(\zeta_n=e^{2\pi i/n}\). The quantity \(f(n,m)\) counts the \(m\)-element subsets \(A\subseteq\{0,1,\dots,n-1\}\) for which
$$\sum_{j\in A}\zeta_n^j=0.$$
Geometrically, we choose \(m\) equally weighted points among the \(n\) equally spaced directions on the unit circle and ask when their vector sum is exactly zero. Directly testing all \(\binom{n}{m}\) subsets is hopeless for the real target, so the implementations reorganize the problem into a smaller primitive cycle and then rebuild the full answer from a generating function.
Write
$$S=\operatorname{rad}(n),\qquad G=\frac{n}{S},$$
where \(\operatorname{rad}(n)\) is the product of the distinct prime divisors of \(n\). The core fact used by the implementations is that all repeated prime powers can be separated cleanly, so the hard combinatorics happens only on the square-free part \(S\).
For a subset \(A\subseteq\{0,\dots,n-1\}\), define the indicator polynomial
$$F_A(x)=\sum_{j=0}^{n-1}\varepsilon_j x^j,\qquad \varepsilon_j\in\{0,1\},$$
with \(\varepsilon_j=1\) exactly when \(j\in A\). Then \(|A|=\sum \varepsilon_j\), and the zero-sum condition is simply
$$F_A(\zeta_n)=0.$$
So the problem is not about floating-point geometry at all; it is about deciding when a \(0/1\)-polynomial vanishes at a primitive \(n\)-th root of unity.
Group exponents by their residue modulo \(G\):
$$F_A(x)=\sum_{r=0}^{G-1}x^r B_r(x^G),$$
where
$$B_r(y)=\sum_{q=0}^{S-1}\varepsilon_{r+qG}y^q.$$
Because \(\zeta_n^G=\zeta_S\), evaluation at \(\zeta_n\) gives
$$F_A(\zeta_n)=\sum_{r=0}^{G-1}\zeta_n^r B_r(\zeta_S).$$
Now \(n\) and \(S\) have the same prime divisors, so
$$[\mathbb{Q}(\zeta_n):\mathbb{Q}(\zeta_S)]=\frac{\varphi(n)}{\varphi(S)}=\frac{n}{S}=G.$$
Therefore \(1,\zeta_n,\zeta_n^2,\dots,\zeta_n^{G-1}\) are linearly independent over \(\mathbb{Q}(\zeta_S)\). The sum above is zero if and only if every block vanishes separately:
$$F_A(\zeta_n)=0\iff B_r(\zeta_S)=0\quad\text{for all }r=0,\dots,G-1.$$
Each residue class modulo \(G\) is thus an independent rotated copy of an \(S\)-cycle. This is the decisive reduction used by the code.
Let \(c_k\) be the number of \(k\)-element subsets of \(\{0,\dots,S-1\}\) whose \(S\)-th roots sum to zero. For one such subset \(T\), define
$$F_T(x)=\sum_{q\in T}x^q.$$
Since \(\zeta_S\) is a primitive \(S\)-th root of unity, its minimal polynomial over \(\mathbb{Q}\) is \(\Phi_S(x)\). Hence
$$F_T(\zeta_S)=0\iff \Phi_S(x)\mid F_T(x).$$
So the problem becomes: among all \(0/1\)-polynomials of degree \(\lt S\), count how many become the zero element in the quotient ring
$$\mathbb{Z}[x]/(\Phi_S(x)).$$
The implementations represent each power \(x^q\) by its coefficient vector modulo \(\Phi_S(x)\), whose dimension is \(\varphi(S)\). A subset is valid exactly when those vectors add up to the zero vector.
The \(S\) exponents are split into two halves. For each left-half subset, the implementation computes its vector sum in \(\mathbb{Z}[x]/(\Phi_S(x))\), records its size, and stores how many times that vector occurs. Then it enumerates right-half subsets, negates their vector sum, and looks up matches from the left side. If a left subset of size \(a\) and a right subset of size \(b\) have opposite vectors, their union is a zero-sum subset of size \(a+b\).
One meet-in-the-middle pass therefore produces every \(c_k\) for \(0\le k\le m\), not just one cardinality. This is why the later polynomial stage can be exact and inexpensive.
For one primitive block define the ordinary generating polynomial
$$P_S(t)=\sum_{k=0}^{S}c_k t^k.$$
Because the \(G\) residue classes are independent, choosing a valid subset from the full \(n\)-cycle is the same as choosing, for each block, a zero-sum subset on the \(S\)-cycle. Sizes add, so the global generating function is
$$P_S(t)^G.$$
Therefore
$$\boxed{f(n,m)=\left[t^m\right]P_S(t)^G.}$$
This boxed formula is exactly what the C++, Python, and Java implementations evaluate.
Here \(n=12\), so \(S=\operatorname{rad}(12)=6\) and \(G=12/6=2\). On one 6-cycle, the zero-sum subsets are easy to classify geometrically:
$$c_0=1,\qquad c_2=3,\qquad c_3=2,\qquad c_4=3,\qquad c_6=1,$$
and all other \(c_k\) are \(0\). Thus
$$P_6(t)=1+3t^2+2t^3+3t^4+t^6.$$
We only need the coefficient of \(t^4\), so terms above degree \(4\) can be ignored:
$$f(12,4)=\left[t^4\right](1+3t^2+2t^3+3t^4)^2.$$
The \(t^4\) contribution comes from \(1\cdot 3t^4\), \(3t^4\cdot 1\), and \(3t^2\cdot 3t^2\). Hence
$$f(12,4)=3+3+9=15,$$
which matches the small checkpoint used by the implementations.
The implementation first computes \(S=\operatorname{rad}(n)\) and \(G=n/S\). It then builds the cyclotomic polynomial \(\Phi_S(x)\) from the identity \(x^k-1=\prod_{d\mid k}\Phi_d(x)\), reducing powers of \(x\) to coefficient vectors modulo \(\Phi_S(x)\). With those vectors available, it performs the meet-in-the-middle count described above and obtains all coefficients \(c_0,c_1,\dots,c_m\) for one primitive block.
Next it forms the polynomial \(P_S(t)\) and multiplies it by itself \(G\) times, truncating degrees above \(m\) after every multiplication because only \(\left[t^m\right]\) matters. All arithmetic is exact: the Python version relies on native arbitrary-precision integers, the Java version uses arbitrary-precision integer objects, and the C++ version stores large integers explicitly so no modulus ever hides carries or cancellations.
Let \(d=\varphi(S)\). Building and using the quotient-ring representation costs polynomial time in \(S\) and \(d\), which is small compared with the subset search. The meet-in-the-middle stage enumerates about \(2^{S/2}\) subsets on each side and processes vectors of length \(d\), so its practical cost is roughly \(O(2^{S/2}d)\) hash-based work with \(O(2^{S/2})\) stored states. The polynomial stage performs \(G\) truncated convolutions up to degree \(m\), giving \(O(Gm^2)\) exact coefficient operations; the bit-cost depends on the size of the final integer. For the target case \(n=360\), the crucial win is that the hard subset stage depends on \(S=\operatorname{rad}(360)=30\), not on all \(360\) positions.
Sei \(\zeta_n=e^{2\pi i/n}\). Die Größe \(f(n,m)\) zählt die \(m\)-elementigen Teilmengen \(A\subseteq\{0,1,\dots,n-1\}\) mit
$$\sum_{j\in A}\zeta_n^j=0.$$
Geometrisch wählt man also \(m\) gleich schwere Punkte unter \(n\) gleichmäßig auf dem Einheitskreis verteilten Richtungen und verlangt, dass ihre Vektorsumme exakt verschwindet. Ein direktes Durchprobieren aller \(\binom{n}{m}\) Teilmengen ist für die echten Parameter unmöglich, daher zerlegen die Implementierungen das Problem zuerst in einen primitiven Zyklus und rekonstruieren das Gesamtergebnis anschließend über eine erzeugende Funktion.
Schreibe
$$S=\operatorname{rad}(n),\qquad G=\frac{n}{S},$$
wobei \(\operatorname{rad}(n)\) das Produkt der verschiedenen Primteiler von \(n\) ist. Die zentrale Beobachtung lautet: Alle mehrfachen Primzahlpotenzen lassen sich sauber abspalten, sodass die eigentliche Kombinatorik nur auf dem quadratfreien Anteil \(S\) stattfindet.
Für eine Teilmenge \(A\subseteq\{0,\dots,n-1\}\) definieren wir das Indikatorpolynom
$$F_A(x)=\sum_{j=0}^{n-1}\varepsilon_j x^j,\qquad \varepsilon_j\in\{0,1\},$$
wobei \(\varepsilon_j=1\) genau dann gilt, wenn \(j\in A\). Dann ist \(|A|=\sum \varepsilon_j\), und die Nullsummen-Bedingung wird zu
$$F_A(\zeta_n)=0.$$
Das Problem ist also keine numerische Geometrie mit Rundungsfehlern, sondern die Frage, wann ein \(0/1\)-Polynom an einer primitiven \(n\)-ten Einheitswurzel verschwindet.
Fasse die Exponenten nach ihrem Rest modulo \(G\) zusammen:
$$F_A(x)=\sum_{r=0}^{G-1}x^r B_r(x^G),$$
mit
$$B_r(y)=\sum_{q=0}^{S-1}\varepsilon_{r+qG}y^q.$$
Weil \(\zeta_n^G=\zeta_S\) gilt, folgt bei der Auswertung
$$F_A(\zeta_n)=\sum_{r=0}^{G-1}\zeta_n^r B_r(\zeta_S).$$
Da \(n\) und \(S\) dieselben Primteiler besitzen, erhält man
$$[\mathbb{Q}(\zeta_n):\mathbb{Q}(\zeta_S)]=\frac{\varphi(n)}{\varphi(S)}=\frac{n}{S}=G.$$
Somit sind \(1,\zeta_n,\zeta_n^2,\dots,\zeta_n^{G-1}\) über \(\mathbb{Q}(\zeta_S)\) linear unabhängig. Daher verschwindet die Summe genau dann, wenn jeder Block einzeln verschwindet:
$$F_A(\zeta_n)=0\iff B_r(\zeta_S)=0\quad\text{für alle }r=0,\dots,G-1.$$
Jede Restklasse modulo \(G\) ist also eine unabhängige, nur rotierte Kopie eines \(S\)-Zyklus. Genau diese Reduktion nutzt der Code aus.
Sei \(c_k\) die Anzahl der \(k\)-elementigen Teilmengen von \(\{0,\dots,S-1\}\), deren \(S\)-te Einheitswurzeln die Summe \(0\) haben. Für eine solche Teilmenge \(T\) definieren wir
$$F_T(x)=\sum_{q\in T}x^q.$$
Da \(\zeta_S\) eine primitive \(S\)-te Einheitswurzel ist, ist \(\Phi_S(x)\) ihr Minimalpolynom über \(\mathbb{Q}\). Also gilt
$$F_T(\zeta_S)=0\iff \Phi_S(x)\mid F_T(x).$$
Damit lautet das Teilproblem: Unter allen \(0/1\)-Polynomen vom Grad \(\lt S\) zählen wir diejenigen, die im Quotientenring
$$\mathbb{Z}[x]/(\Phi_S(x))$$
zum Nullelement werden. Die Implementierungen repräsentieren jedes \(x^q\) durch seinen Koeffizientenvektor modulo \(\Phi_S(x)\), dessen Dimension \(\varphi(S)\) ist. Eine Teilmenge ist genau dann gültig, wenn sich diese Vektoren zum Nullvektor addieren.
Die \(S\) Exponenten werden in zwei Hälften geteilt. Für jede linke Teilmenge berechnet die Implementierung ihre Vektorsumme in \(\mathbb{Z}[x]/(\Phi_S(x))\), speichert ihre Größe und zählt, wie oft dieser Vektor vorkommt. Danach werden alle rechten Teilmengen durchlaufen, ihre Vektorsummen negiert und passende Gegenvektoren auf der linken Seite gesucht. Haben eine linke Teilmenge der Größe \(a\) und eine rechte Teilmenge der Größe \(b\) entgegengesetzte Vektoren, dann bildet ihre Vereinigung eine Nullsummen-Teilmenge der Größe \(a+b\).
Ein einziger Meet-in-the-Middle-Durchgang liefert also alle Werte \(c_k\) für \(0\le k\le m\) und nicht nur eine einzige Kardinalität. Deshalb ist die anschließende Polynomphase exakt und kompakt.
Für einen primitiven Block definieren wir das gewöhnliche erzeugende Polynom
$$P_S(t)=\sum_{k=0}^{S}c_k t^k.$$
Weil die \(G\) Restklassen unabhängig sind, entspricht eine gültige Auswahl auf dem gesamten \(n\)-Zyklus der unabhängigen Wahl einer Nullsummen-Teilmenge in jedem Block. Die Größen addieren sich, also ist die globale erzeugende Funktion
$$P_S(t)^G.$$
Folglich gilt
$$\boxed{f(n,m)=\left[t^m\right]P_S(t)^G.}$$
Genau diese Formel berechnen die C++-, Python- und Java-Implementierungen.
Hier ist \(n=12\), also \(S=\operatorname{rad}(12)=6\) und \(G=12/6=2\). Auf einem 6-Zyklus lassen sich die Nullsummen-Teilmengen geometrisch leicht klassifizieren:
$$c_0=1,\qquad c_2=3,\qquad c_3=2,\qquad c_4=3,\qquad c_6=1,$$
alle anderen \(c_k\) sind \(0\). Damit
$$P_6(t)=1+3t^2+2t^3+3t^4+t^6.$$
Benötigt wird nur der Koeffizient von \(t^4\), also können Grade \(>4\) ignoriert werden:
$$f(12,4)=\left[t^4\right](1+3t^2+2t^3+3t^4)^2.$$
Der Beitrag zu \(t^4\) kommt von \(1\cdot 3t^4\), \(3t^4\cdot 1\) und \(3t^2\cdot 3t^2\). Daher
$$f(12,4)=3+3+9=15,$$
genau der kleine Kontrollwert aus den Implementierungen.
Die Implementierung berechnet zuerst \(S=\operatorname{rad}(n)\) und \(G=n/S\). Anschließend konstruiert sie das zyklotomische Polynom \(\Phi_S(x)\) aus der Identität \(x^k-1=\prod_{d\mid k}\Phi_d(x)\) und reduziert Potenzen von \(x\) auf Koeffizientenvektoren modulo \(\Phi_S(x)\). Mit diesen Vektoren führt sie den oben beschriebenen Meet-in-the-Middle-Schritt aus und erhält alle Koeffizienten \(c_0,c_1,\dots,c_m\) für einen primitiven Block.
Danach wird das Polynom \(P_S(t)\) aufgebaut und \(G\)-mal mit sich selbst multipliziert, wobei nach jeder Multiplikation alle Grade über \(m\) abgeschnitten werden, weil nur \(\left[t^m\right]\) gebraucht wird. Die Arithmetik bleibt vollständig exakt: Python nutzt eingebaute Ganzzahlen beliebiger Länge, Java verwendet Arbitrary-Precision-Integer, und C++ verwaltet große Ganzzahlen explizit, sodass kein Modulus Überträge oder Auslöschungen verdeckt.
Sei \(d=\varphi(S)\). Der Aufbau und die Nutzung der Quotientenring-Darstellung kosten polynomial viel Zeit in \(S\) und \(d\), was klein gegenüber der Teilmengen-Suche ist. Die Meet-in-the-Middle-Phase enumeriert auf jeder Seite ungefähr \(2^{S/2}\) Teilmengen und verarbeitet Vektoren der Länge \(d\); praktisch ergibt sich also etwa \(O(2^{S/2}d)\) hashbasierte Arbeit bei \(O(2^{S/2})\) gespeicherten Zuständen. Die Polynomphase führt \(G\) abgeschnittene Faltungen bis zum Grad \(m\) aus und benötigt damit \(O(Gm^2)\) exakte Koeffizientenoperationen; die Bitkomplexität hängt von der Größe der endgültigen Zahl ab. Beim Zielwert \(n=360\) ist der entscheidende Vorteil, dass die schwere Teilmengenphase nur von \(S=\operatorname{rad}(360)=30\) abhängt und nicht von allen \(360\) Positionen.
\(\zeta_n=e^{2\pi i/n}\) olsun. \(f(n,m)\),
$$\sum_{j\in A}\zeta_n^j=0$$
koşulunu sağlayan \(m\) elemanlı \(A\subseteq\{0,1,\dots,n-1\}\) altkümelerinin sayısını verir. Geometrik olarak, birim çember üzerindeki eşit aralıklı \(n\) yönden \(m\) tanesini seçiyor ve bu seçimin vektörel toplamının tam olarak sıfır olmasını istiyoruz. Gerçek hedefte \(\binom{n}{m}\) kadar altküme doğrudan denenemeyeceği için uygulamalar önce problemi daha küçük bir ilkel çevrime indiriyor, sonra da sonucu üretici polinom üzerinden geri kuruyor.
Şöyle yazalım:
$$S=\operatorname{rad}(n),\qquad G=\frac{n}{S},$$
burada \(\operatorname{rad}(n)\), \(n\)'nin farklı asal bölenlerinin çarpımıdır. Çözümün ana gözlemi şudur: tekrar eden asal kuvvetler temiz biçimde ayrılabilir; asıl kombinatorik zorluk sadece kareden arındırılmış kısım olan \(S\) üzerinde kalır.
\(A\subseteq\{0,\dots,n-1\}\) için gösterge polinomunu
$$F_A(x)=\sum_{j=0}^{n-1}\varepsilon_j x^j,\qquad \varepsilon_j\in\{0,1\},$$
şeklinde tanımlayalım; burada \(\varepsilon_j=1\) ancak ve ancak \(j\in A\) ise doğrudur. O zaman \(|A|=\sum \varepsilon_j\) olur ve sıfır-toplam koşulu
$$F_A(\zeta_n)=0$$
biçimine dönüşür. Yani problem kayan noktalı geometri problemi olmaktan çıkıp, bir \(0/1\) polinomunun ilkel bir \(n\).inci birim kökte ne zaman sıfır olduğuna indirgenir.
Üsleri \(G\)'ye göre kalıntı sınıflarına göre gruplayalım:
$$F_A(x)=\sum_{r=0}^{G-1}x^r B_r(x^G),$$
burada
$$B_r(y)=\sum_{q=0}^{S-1}\varepsilon_{r+qG}y^q.$$
\(\zeta_n^G=\zeta_S\) olduğundan
$$F_A(\zeta_n)=\sum_{r=0}^{G-1}\zeta_n^r B_r(\zeta_S)$$
elde edilir. Ayrıca \(n\) ile \(S\) aynı asal bölenlere sahip olduğu için
$$[\mathbb{Q}(\zeta_n):\mathbb{Q}(\zeta_S)]=\frac{\varphi(n)}{\varphi(S)}=\frac{n}{S}=G.$$
Dolayısıyla \(1,\zeta_n,\zeta_n^2,\dots,\zeta_n^{G-1}\) sayıları \(\mathbb{Q}(\zeta_S)\) üzerinde lineer bağımsızdır. Bu yüzden toplamın sıfır olması ancak her bloğun ayrı ayrı sıfır olmasıyla mümkündür:
$$F_A(\zeta_n)=0\iff B_r(\zeta_S)=0\quad\text{tüm }r=0,\dots,G-1\text{ için.}$$
Böylece \(G\)'ye göre her kalıntı sınıfı, sadece döndürülmüş bir \(S\)-çevrimi gibi bağımsız davranır. Kodun kullandığı temel indirgeme tam olarak budur.
\(c_k\), \(\{0,\dots,S-1\}\) içindeki ve \(S\).inci köklerin toplamı sıfır olan \(k\) elemanlı altkümelerin sayısı olsun. Böyle bir \(T\) altkümesi için
$$F_T(x)=\sum_{q\in T}x^q$$
tanımını yapalım. \(\zeta_S\), ilkel bir \(S\).inci birim kök olduğundan onun \(\mathbb{Q}\) üzerindeki minimal polinomu \(\Phi_S(x)\)'tir. Bu yüzden
$$F_T(\zeta_S)=0\iff \Phi_S(x)\mid F_T(x)$$
eşdeğerliği vardır. Yani alt problem şu hale gelir: derecesi \(\lt S\) olan bütün \(0/1\) polinomları içinde,
$$\mathbb{Z}[x]/(\Phi_S(x))$$
bölüm halkasında sıfıra düşenleri say. Uygulamalar her \(x^q\) kuvvetini \(\Phi_S(x)\)'e göre indirgenmiş bir katsayı vektörüyle temsil eder; bu vektörün boyutu \(\varphi(S)\)'dir. Bir altküme tam ve ancak bu vektörlerin toplamı sıfır vektör olduğunda geçerlidir.
\(S\) tane üs iki yarıya bölünür. Sol yarıdaki her altküme için bölüm halkasındaki vektör toplamı ve altküme boyutu hesaplanır; aynı vektörü veren kaç seçim olduğu saklanır. Ardından sağ yarının altkümeleri dolaşılır, vektör toplamları ters işaretlenir ve soldaki eşleşmeler aranır. Boyutu \(a\) olan bir sol altküme ile boyutu \(b\) olan bir sağ altküme zıt vektör veriyorsa birleşimleri boyutu \(a+b\) olan bir sıfır-toplam altkümedir.
Böylece tek bir meet-in-the-middle geçişi, yalnızca tek bir kardinaliteyi değil, \(0\le k\le m\) aralığındaki tüm \(c_k\) değerlerini birden üretir. Sonraki polinom aşamasının temiz olmasının nedeni budur.
Bir ilkel blok için olağan üretici polinomu
$$P_S(t)=\sum_{k=0}^{S}c_k t^k$$
olarak tanımlayalım. \(G\) tane kalıntı sınıfı bağımsız olduğundan, tam \(n\)-çevrimindeki geçerli bir seçim her bloktan bağımsız bir sıfır-toplam seçim yapmakla aynıdır. Boyutlar toplandığı için küresel üretici polinom
$$P_S(t)^G$$
olur. Sonuç olarak
$$\boxed{f(n,m)=\left[t^m\right]P_S(t)^G.}$$
C++, Python ve Java uygulamalarının hesapladığı şey tam olarak bu katsayıdır.
Burada \(n=12\), dolayısıyla \(S=\operatorname{rad}(12)=6\) ve \(G=12/6=2\). Tek bir 6'lı çevrim üzerinde sıfır-toplam altkümeleri geometrik olarak kolayca sınıflanır:
$$c_0=1,\qquad c_2=3,\qquad c_3=2,\qquad c_4=3,\qquad c_6=1,$$
diğer tüm \(c_k\) değerleri \(0\)'dır. Bu yüzden
$$P_6(t)=1+3t^2+2t^3+3t^4+t^6.$$
Sadece \(t^4\) katsayısı gerektiği için derece \(4\)'ün üstündeki terimleri ihmal edebiliriz:
$$f(12,4)=\left[t^4\right](1+3t^2+2t^3+3t^4)^2.$$
\(t^4\) katkısı \(1\cdot 3t^4\), \(3t^4\cdot 1\) ve \(3t^2\cdot 3t^2\) terimlerinden gelir. Dolayısıyla
$$f(12,4)=3+3+9=15,$$
ve bu küçük kontrol değeri uygulamaların ürettiği sonuçla aynıdır.
Uygulama önce \(S=\operatorname{rad}(n)\) ve \(G=n/S\) değerlerini hesaplar. Sonra \(x^k-1=\prod_{d\mid k}\Phi_d(x)\) özdeşliğinden yararlanarak \(\Phi_S(x)\) siklotomik polinomunu kurar ve \(x\) kuvvetlerini bu polinoma göre indirgenmiş katsayı vektörlerine dönüştürür. Bu vektörlerle yukarıdaki meet-in-the-middle sayımı yapılır ve tek bir ilkel blok için \(c_0,c_1,\dots,c_m\) katsayıları elde edilir.
Ardından \(P_S(t)\) polinomu kurulur ve derece \(m\)'in üzeri her çarpımda kesilerek toplam \(G\) kez kendisiyle çarpılır; çünkü gerekli olan tek şey \(\left[t^m\right]\) katsayısıdır. Bütün aritmetik tam sayılarla ve eksiksiz yürütülür: Python yerleşik büyük tamsayıları kullanır, Java keyfi duyarlıklı tamsayılara dayanır, C++ ise büyük sayıları açıkça temsil ederek mod alma yüzünden bilgi kaybı yaşanmasını engeller.
\(d=\varphi(S)\) olsun. Bölüm halkası temsilini kurmak ve kullanmak \(S\) ile \(d\) cinsinden polinomik maliyettedir; asıl ağır kısım altküme aramasıdır. Meet-in-the-middle aşaması her tarafta yaklaşık \(2^{S/2}\) altküme dolaşır ve uzunluğu \(d\) olan vektörler işler; pratikte bu yaklaşık \(O(2^{S/2}d)\) seviyesinde hash tabanlı iş ve \(O(2^{S/2})\) durum belleği demektir. Polinom aşaması derece \(m\)'e kadar kesilmiş \(G\) katlı konvolüsyonlardan oluşur; bu da \(O(Gm^2)\) tam katsayı işlemi verir. Bit düzeyindeki gerçek maliyet, sonucun kaç basamaklı olduğuna bağlıdır. Hedef örnek \(n=360\) için kritik kazanç, zor altküme sayımının \(360\) yerine sadece \(S=\operatorname{rad}(360)=30\) tarafından belirlenmesidir.
Sea \(\zeta_n=e^{2\pi i/n}\). La cantidad \(f(n,m)\) cuenta los subconjuntos \(A\subseteq\{0,1,\dots,n-1\}\) de tamaño \(m\) tales que
$$\sum_{j\in A}\zeta_n^j=0.$$
Geométricamente, se eligen \(m\) puntos con el mismo peso entre \(n\) direcciones igualmente espaciadas en el círculo unitario, y se pide que la suma vectorial sea exactamente cero. Probar directamente los \(\binom{n}{m}\) subconjuntos es inviable para el caso real, así que las implementaciones reducen primero el problema a un ciclo primitivo más pequeño y luego reconstruyen la respuesta completa con una función generadora.
Escribimos
$$S=\operatorname{rad}(n),\qquad G=\frac{n}{S},$$
donde \(\operatorname{rad}(n)\) es el producto de los divisores primos distintos de \(n\). La observación central es que las potencias primas repetidas pueden separarse limpiamente, de modo que la parte difícil de la combinatoria vive solo en la parte libre de cuadrados \(S\).
Para un subconjunto \(A\subseteq\{0,\dots,n-1\}\), definimos el polinomio indicador
$$F_A(x)=\sum_{j=0}^{n-1}\varepsilon_j x^j,\qquad \varepsilon_j\in\{0,1\},$$
con \(\varepsilon_j=1\) exactamente cuando \(j\in A\). Entonces \(|A|=\sum \varepsilon_j\), y la condición de suma nula se convierte en
$$F_A(\zeta_n)=0.$$
Así, el problema no se resuelve con aproximaciones numéricas sobre el círculo, sino comprobando cuándo un polinomio con coeficientes \(0/1\) se anula en una raíz primitiva \(n\)-ésima de la unidad.
Agrupamos los exponentes por su residuo módulo \(G\):
$$F_A(x)=\sum_{r=0}^{G-1}x^r B_r(x^G),$$
donde
$$B_r(y)=\sum_{q=0}^{S-1}\varepsilon_{r+qG}y^q.$$
Como \(\zeta_n^G=\zeta_S\), al evaluar obtenemos
$$F_A(\zeta_n)=\sum_{r=0}^{G-1}\zeta_n^r B_r(\zeta_S).$$
Además, \(n\) y \(S\) tienen los mismos divisores primos, por lo que
$$[\mathbb{Q}(\zeta_n):\mathbb{Q}(\zeta_S)]=\frac{\varphi(n)}{\varphi(S)}=\frac{n}{S}=G.$$
En consecuencia, \(1,\zeta_n,\zeta_n^2,\dots,\zeta_n^{G-1}\) son linealmente independientes sobre \(\mathbb{Q}(\zeta_S)\). La suma total es cero si y solo si cada bloque se anula por separado:
$$F_A(\zeta_n)=0\iff B_r(\zeta_S)=0\quad\text{para todo }r=0,\dots,G-1.$$
Cada clase residual módulo \(G\) se comporta, por tanto, como una copia rotada e independiente de un ciclo de tamaño \(S\). Esa es la reducción clave del algoritmo.
Sea \(c_k\) el número de subconjuntos de \(\{0,\dots,S-1\}\) con \(k\) elementos cuya suma de raíces \(S\)-ésimas es cero. Para un subconjunto \(T\), definimos
$$F_T(x)=\sum_{q\in T}x^q.$$
Como \(\zeta_S\) es una raíz primitiva \(S\)-ésima de la unidad, su polinomio minimal sobre \(\mathbb{Q}\) es \(\Phi_S(x)\). Por tanto,
$$F_T(\zeta_S)=0\iff \Phi_S(x)\mid F_T(x).$$
El subproblema pasa a ser: entre todos los polinomios \(0/1\) de grado \(\lt S\), contar los que representan el elemento cero en el cociente
$$\mathbb{Z}[x]/(\Phi_S(x)).$$
Las implementaciones representan cada potencia \(x^q\) mediante su vector de coeficientes módulo \(\Phi_S(x)\), de dimensión \(\varphi(S)\). Un subconjunto es válido exactamente cuando la suma de esos vectores es el vector nulo.
Los \(S\) exponentes se dividen en dos mitades. Para cada subconjunto de la mitad izquierda, la implementación calcula su suma vectorial en \(\mathbb{Z}[x]/(\Phi_S(x))\), registra su tamaño y guarda cuántas veces aparece ese vector. Luego recorre los subconjuntos de la mitad derecha, cambia el signo de su suma vectorial y busca coincidencias en la tabla izquierda. Si un subconjunto izquierdo de tamaño \(a\) y uno derecho de tamaño \(b\) producen vectores opuestos, su unión es un subconjunto de suma cero de tamaño \(a+b\).
Una sola pasada meet-in-the-middle produce así todos los valores \(c_k\) para \(0\le k\le m\), no solo una cardinalidad concreta. Esa es la razón por la que la fase posterior con polinomios puede ser exacta y compacta.
Para un bloque primitivo definimos el polinomio generador ordinario
$$P_S(t)=\sum_{k=0}^{S}c_k t^k.$$
Como las \(G\) clases residuales son independientes, elegir un subconjunto válido en el ciclo completo equivale a elegir, en cada bloque, un subconjunto de suma cero sobre el ciclo de tamaño \(S\). Los tamaños se suman, luego la función generadora global es
$$P_S(t)^G.$$
Por consiguiente,
$$\boxed{f(n,m)=\left[t^m\right]P_S(t)^G.}$$
Eso es exactamente lo que evalúan las implementaciones en C++, Python y Java.
Aquí \(n=12\), por lo que \(S=\operatorname{rad}(12)=6\) y \(G=12/6=2\). En un ciclo de 6 puntos, los subconjuntos de suma cero se clasifican fácilmente:
$$c_0=1,\qquad c_2=3,\qquad c_3=2,\qquad c_4=3,\qquad c_6=1,$$
y todos los demás \(c_k\) valen \(0\). Así,
$$P_6(t)=1+3t^2+2t^3+3t^4+t^6.$$
Solo hace falta el coeficiente de \(t^4\), por lo que podemos ignorar los términos de grado mayor que \(4\):
$$f(12,4)=\left[t^4\right](1+3t^2+2t^3+3t^4)^2.$$
La contribución a \(t^4\) viene de \(1\cdot 3t^4\), \(3t^4\cdot 1\) y \(3t^2\cdot 3t^2\). Por tanto,
$$f(12,4)=3+3+9=15,$$
que coincide con la comprobación pequeña usada por las implementaciones.
La implementación calcula primero \(S=\operatorname{rad}(n)\) y \(G=n/S\). Después construye el polinomio ciclotómico \(\Phi_S(x)\) a partir de la identidad \(x^k-1=\prod_{d\mid k}\Phi_d(x)\), y reduce las potencias de \(x\) a vectores de coeficientes módulo \(\Phi_S(x)\). Con esos vectores ejecuta el conteo meet-in-the-middle descrito arriba y obtiene todos los coeficientes \(c_0,c_1,\dots,c_m\) correspondientes a un bloque primitivo.
A continuación forma el polinomio \(P_S(t)\) y lo multiplica por sí mismo \(G\) veces, truncando después de cada multiplicación todos los grados mayores que \(m\), porque solo importa \(\left[t^m\right]\). Toda la aritmética es exacta: Python usa enteros arbitrariamente grandes, Java trabaja con enteros de precisión arbitraria y C++ mantiene enteros grandes explícitos, de modo que no hay ningún módulo que oculte arrastres ni cancelaciones.
Sea \(d=\varphi(S)\). Construir y usar la representación en el anillo cociente cuesta tiempo polinómico en \(S\) y \(d\), mucho menor que la búsqueda de subconjuntos. La fase meet-in-the-middle enumera aproximadamente \(2^{S/2}\) subconjuntos por lado y procesa vectores de longitud \(d\); en la práctica, esto supone del orden de \(O(2^{S/2}d)\) trabajo con tablas hash y \(O(2^{S/2})\) estados almacenados. La fase polinómica realiza \(G\) convoluciones truncadas hasta grado \(m\), es decir, \(O(Gm^2)\) operaciones exactas sobre coeficientes; el coste en bits depende del tamaño del entero final. Para el caso objetivo \(n=360\), la mejora esencial es que la fase difícil depende de \(S=\operatorname{rad}(360)=30\), no de las \(360\) posiciones originales.
设 \(\zeta_n=e^{2\pi i/n}\)。\(f(n,m)\) 统计的是所有满足
$$\sum_{j\in A}\zeta_n^j=0$$
的 \(m\) 元子集 \(A\subseteq\{0,1,\dots,n-1\}\) 的个数。几何上，这表示从单位圆上 \(n\) 个等间距方向中选出 \(m\) 个等权重点，并要求它们的向量和恰好为零。对于真实目标参数，直接枚举 \(\binom{n}{m}\) 个子集完全不可行，因此实现采用“先降维到更小的原始循环，再用生成函数重建总答案”的思路。
记
$$S=\operatorname{rad}(n),\qquad G=\frac{n}{S},$$
其中 \(\operatorname{rad}(n)\) 表示 \(n\) 的所有不同质因子的乘积。实现依赖的核心事实是：重复出现的质因子幂次可以被整齐地剥离出去，真正困难的组合计数只发生在平方因子被去掉后的部分 \(S\) 上。
对任意子集 \(A\subseteq\{0,\dots,n-1\}\)，定义指标多项式
$$F_A(x)=\sum_{j=0}^{n-1}\varepsilon_j x^j,\qquad \varepsilon_j\in\{0,1\},$$
其中 \(\varepsilon_j=1\) 当且仅当 \(j\in A\)。于是 \(|A|=\sum \varepsilon_j\)，而零和条件可以直接写成
$$F_A(\zeta_n)=0.$$
这说明问题并不需要数值近似或浮点几何，而是要判断一个 \(0/1\) 多项式何时在一个原始 \(n\) 次单位根处取值为零。
按模 \(G\) 的余数对指数分组：
$$F_A(x)=\sum_{r=0}^{G-1}x^r B_r(x^G),$$
其中
$$B_r(y)=\sum_{q=0}^{S-1}\varepsilon_{r+qG}y^q.$$
由于 \(\zeta_n^G=\zeta_S\)，代入后得到
$$F_A(\zeta_n)=\sum_{r=0}^{G-1}\zeta_n^r B_r(\zeta_S).$$
另一方面，\(n\) 与 \(S\) 具有完全相同的质因子集合，因此
$$[\mathbb{Q}(\zeta_n):\mathbb{Q}(\zeta_S)]=\frac{\varphi(n)}{\varphi(S)}=\frac{n}{S}=G.$$
所以 \(1,\zeta_n,\zeta_n^2,\dots,\zeta_n^{G-1}\) 在 \(\mathbb{Q}(\zeta_S)\) 上线性无关。于是总和为零当且仅当每个块分别为零：
$$F_A(\zeta_n)=0\iff B_r(\zeta_S)=0\quad\text{对所有 }r=0,\dots,G-1.$$
这意味着模 \(G\) 的每一个剩余类都可以看作一个彼此独立、仅仅整体旋转过的 \(S\) 点循环。代码正是先利用这个结构把问题缩小，再做后续计数。
设 \(c_k\) 为 \(\{0,\dots,S-1\}\) 中所有大小为 \(k\) 且对应 \(S\) 次单位根和为零的子集数量。对这样的子集 \(T\)，定义
$$F_T(x)=\sum_{q\in T}x^q.$$
因为 \(\zeta_S\) 是原始 \(S\) 次单位根，它在 \(\mathbb{Q}\) 上的极小多项式正是 \(\Phi_S(x)\)。因此有
$$F_T(\zeta_S)=0\iff \Phi_S(x)\mid F_T(x).$$
于是子问题变成：在所有次数小于 \(S\) 的 \(0/1\) 多项式中，统计哪些多项式在商环
$$\mathbb{Z}[x]/(\Phi_S(x))$$
里代表零元素。实现把每个幂 \(x^q\) 表示为模 \(\Phi_S(x)\) 之后的系数向量，其维数为 \(\varphi(S)\)。一个子集恰好在这些向量求和得到零向量时有效。
把 \(S\) 个指数拆成左右两半。对左半部分的每个子集，实现都会计算其在 \(\mathbb{Z}[x]/(\Phi_S(x))\) 中的向量和、记录其大小，并把同一个向量出现的次数存入表中。然后枚举右半部分所有子集，计算其向量和的相反数，并到左侧表中寻找匹配。若左侧一个大小为 \(a\) 的子集与右侧一个大小为 \(b\) 的子集对应向量互为相反数，那么它们的并集就是一个大小为 \(a+b\) 的零和子集。
这样一次 meet-in-the-middle 扫描就能同时得到 \(0\le k\le m\) 的全部 \(c_k\)，而不是只针对某一个固定大小单独计算。这正是后续生成函数阶段能够写得很整齐的原因。
对一个原始块，定义普通生成多项式
$$P_S(t)=\sum_{k=0}^{S}c_k t^k.$$
因为这 \(G\) 个剩余类彼此独立，在整个 \(n\) 环上的一个合法选择，等价于在每个块上各自选择一个零和子集。大小会相加，因此全局生成函数就是
$$P_S(t)^G.$$
从而
$$\boxed{f(n,m)=\left[t^m\right]P_S(t)^G.}$$
这正是 C++、Python 和 Java 实现最终计算的公式。
这里 \(n=12\)，所以 \(S=\operatorname{rad}(12)=6\)，\(G=12/6=2\)。在一个 6 点循环上，零和子集可以直接按几何形状分类：
$$c_0=1,\qquad c_2=3,\qquad c_3=2,\qquad c_4=3,\qquad c_6=1,$$
其余所有 \(c_k\) 都为 \(0\)。因此
$$P_6(t)=1+3t^2+2t^3+3t^4+t^6.$$
因为这里只需要 \(t^4\) 的系数，所以高于 4 次的项都可以忽略：
$$f(12,4)=\left[t^4\right](1+3t^2+2t^3+3t^4)^2.$$
\(t^4\) 的贡献来自 \(1\cdot 3t^4\)、\(3t^4\cdot 1\) 和 \(3t^2\cdot 3t^2\)。于是
$$f(12,4)=3+3+9=15,$$
这与实现中使用的小规模校验值完全一致。
实现首先计算 \(S=\operatorname{rad}(n)\) 和 \(G=n/S\)。随后利用恒等式 \(x^k-1=\prod_{d\mid k}\Phi_d(x)\) 逐步构造 \(\Phi_S(x)\)，并把各个 \(x\) 的幂化为模 \(\Phi_S(x)\) 的系数向量。有了这些向量后，就执行上面描述的 meet-in-the-middle 计数，一次性得到单个原始块对应的所有 \(c_0,c_1,\dots,c_m\)。
接着构造多项式 \(P_S(t)\)，并将其自乘 \(G\) 次；每次乘法后都会把次数大于 \(m\) 的项截掉，因为最终只关心 \(\left[t^m\right]\)。整个过程保持精确整数运算：Python 直接使用原生大整数，Java 使用任意精度整数对象，C++ 也显式维护大整数表示，因此不会因为取模而掩盖进位或抵消。
记 \(d=\varphi(S)\)。构造并使用商环表示的成本在 \(S\) 和 \(d\) 上是多项式级别，相比子集搜索要小得多。meet-in-the-middle 阶段在左右两侧各枚举大约 \(2^{S/2}\) 个子集，并处理长度为 \(d\) 的向量，因此实际复杂度可视为大约 \(O(2^{S/2}d)\) 的哈希工作，外加 \(O(2^{S/2})\) 级别的存储。多项式阶段进行 \(G\) 次截断卷积到次数 \(m\)，需要 \(O(Gm^2)\) 次精确系数运算；若从位复杂度角度衡量，还要再乘上大整数长度带来的代价。对于目标参数 \(n=360\)，关键收益在于困难的子集枚举只依赖 \(S=\operatorname{rad}(360)=30\)，而不是原始的 \(360\) 个位置。
Пусть \(\zeta_n=e^{2\pi i/n}\). Величина \(f(n,m)\) считает количество \(m\)-элементных подмножеств \(A\subseteq\{0,1,\dots,n-1\}\), для которых выполняется
$$\sum_{j\in A}\zeta_n^j=0.$$
Геометрически это означает выбор \(m\) одинаково взвешенных точек среди \(n\) равномерно расположенных направлений на единичной окружности с требованием, чтобы их векторная сумма была ровно нулевой. Прямой перебор всех \(\binom{n}{m}\) вариантов для целевого случая невозможен, поэтому реализации сначала сводят задачу к меньшему примитивному циклу, а затем восстанавливают полный ответ через производящую функцию.
Обозначим
$$S=\operatorname{rad}(n),\qquad G=\frac{n}{S},$$
где \(\operatorname{rad}(n)\) — произведение различных простых делителей числа \(n\). Основной факт состоит в том, что повторяющиеся простые степени можно отделить полностью, и вся нетривиальная комбинаторика остается только на свободной от квадратов части \(S\).
Для подмножества \(A\subseteq\{0,\dots,n-1\}\) введем индикаторный многочлен
$$F_A(x)=\sum_{j=0}^{n-1}\varepsilon_j x^j,\qquad \varepsilon_j\in\{0,1\},$$
где \(\varepsilon_j=1\) тогда и только тогда, когда \(j\in A\). Тогда \(|A|=\sum \varepsilon_j\), а условие нулевой суммы принимает вид
$$F_A(\zeta_n)=0.$$
То есть задача сводится не к численной геометрии, а к вопросу о том, когда многочлен с коэффициентами \(0/1\) обращается в нуль в примитивном \(n\)-м корне единицы.
Сгруппируем показатели по остаткам modulo \(G\):
$$F_A(x)=\sum_{r=0}^{G-1}x^r B_r(x^G),$$
где
$$B_r(y)=\sum_{q=0}^{S-1}\varepsilon_{r+qG}y^q.$$
Поскольку \(\zeta_n^G=\zeta_S\), получаем
$$F_A(\zeta_n)=\sum_{r=0}^{G-1}\zeta_n^r B_r(\zeta_S).$$
Так как \(n\) и \(S\) имеют один и тот же набор простых делителей, то
$$[\mathbb{Q}(\zeta_n):\mathbb{Q}(\zeta_S)]=\frac{\varphi(n)}{\varphi(S)}=\frac{n}{S}=G.$$
Следовательно, числа \(1,\zeta_n,\zeta_n^2,\dots,\zeta_n^{G-1}\) линейно независимы над \(\mathbb{Q}(\zeta_S)\). Поэтому общая сумма равна нулю тогда и только тогда, когда каждый блок зануляется отдельно:
$$F_A(\zeta_n)=0\iff B_r(\zeta_S)=0\quad\text{для всех }r=0,\dots,G-1.$$
Итак, каждый класс остатков modulo \(G\) ведет себя как независимая повернутая копия цикла длины \(S\). Именно на этом сокращении основан алгоритм.
Пусть \(c_k\) — число \(k\)-элементных подмножеств множества \(\{0,\dots,S-1\}\), для которых сумма соответствующих \(S\)-х корней единицы равна нулю. Для такого подмножества \(T\) определим
$$F_T(x)=\sum_{q\in T}x^q.$$
Так как \(\zeta_S\) является примитивным \(S\)-м корнем единицы, его минимальный многочлен над \(\mathbb{Q}\) равен \(\Phi_S(x)\). Значит,
$$F_T(\zeta_S)=0\iff \Phi_S(x)\mid F_T(x).$$
Подзадача становится такой: среди всех многочленов степени \(\lt S\) с коэффициентами \(0/1\) посчитать те, которые представляют нулевой элемент в фактор-кольце
$$\mathbb{Z}[x]/(\Phi_S(x)).$$
Реализации представляют каждую степень \(x^q\) как вектор коэффициентов по модулю \(\Phi_S(x)\); размерность этого вектора равна \(\varphi(S)\). Подмножество допустимо тогда и только тогда, когда сумма таких векторов дает нулевой вектор.
\(S\) показателей делятся на две половины. Для каждого подмножества левой половины реализация вычисляет его векторную сумму в \(\mathbb{Z}[x]/(\Phi_S(x))\), запоминает размер подмножества и считает число появлений данного вектора. Затем перебираются подмножества правой половины, их векторные суммы меняются на противоположные, и ищутся совпадения в левой таблице. Если левое подмножество размера \(a\) и правое подмножество размера \(b\) дают противоположные векторы, то их объединение образует нулевое подмножество размера \(a+b\).
Один проход meet-in-the-middle тем самым дает все значения \(c_k\) для \(0\le k\le m\), а не только одно фиксированное значение мощности. Благодаря этому дальнейшая полиномиальная часть получается короткой и точной.
Для одного примитивного блока введем обычный производящий многочлен
$$P_S(t)=\sum_{k=0}^{S}c_k t^k.$$
Поскольку все \(G\) классов остатков независимы, допустимый выбор на полном \(n\)-цикле эквивалентен независимому выбору нулевого подмножества в каждом блоке. Размеры складываются, поэтому глобальная производящая функция равна
$$P_S(t)^G.$$
Следовательно,
$$\boxed{f(n,m)=\left[t^m\right]P_S(t)^G.}$$
Именно этот коэффициент вычисляют реализации на C++, Python и Java.
Здесь \(n=12\), значит \(S=\operatorname{rad}(12)=6\) и \(G=12/6=2\). На одном 6-цикле нулевые подмножества легко классифицируются геометрически:
$$c_0=1,\qquad c_2=3,\qquad c_3=2,\qquad c_4=3,\qquad c_6=1,$$
а все остальные \(c_k\) равны нулю. Поэтому
$$P_6(t)=1+3t^2+2t^3+3t^4+t^6.$$
Нужен только коэффициент при \(t^4\), так что члены степени выше \(4\) можно отбросить:
$$f(12,4)=\left[t^4\right](1+3t^2+2t^3+3t^4)^2.$$
Вклад в \(t^4\) дают слагаемые \(1\cdot 3t^4\), \(3t^4\cdot 1\) и \(3t^2\cdot 3t^2\). Отсюда
$$f(12,4)=3+3+9=15,$$
что совпадает с малой контрольной проверкой в реализациях.
Сначала реализация вычисляет \(S=\operatorname{rad}(n)\) и \(G=n/S\). Затем она строит циклотомический многочлен \(\Phi_S(x)\) из тождества \(x^k-1=\prod_{d\mid k}\Phi_d(x)\) и переводит степени \(x\) в векторы коэффициентов по модулю \(\Phi_S(x)\). После этого выполняется описанный выше meet-in-the-middle, который сразу дает все коэффициенты \(c_0,c_1,\dots,c_m\) для одного примитивного блока.
Далее строится многочлен \(P_S(t)\) и \(G\) раз перемножается сам с собой с усечением всех степеней выше \(m\) после каждого шага, потому что нужен только коэффициент \(\left[t^m\right]\). Вся арифметика точная: Python использует встроенные целые произвольной длины, Java — целые произвольной точности, а C++ хранит большие числа явно, так что никакой модуль не скрывает переносы и сокращения.
Пусть \(d=\varphi(S)\). Построение и использование представления в фактор-кольце занимает полиномиальное время по \(S\) и \(d\), что мало по сравнению с перебором подмножеств. Этап meet-in-the-middle перечисляет примерно \(2^{S/2}\) подмножеств с каждой стороны и обрабатывает векторы длины \(d\), поэтому практическая стоимость близка к \(O(2^{S/2}d)\) хеш-операций при \(O(2^{S/2})\) сохраненных состояний. Полиномиальный этап выполняет \(G\) усеченных сверток до степени \(m\), что дает \(O(Gm^2)\) точных операций с коэффициентами; битовая стоимость зависит от длины итогового числа. Для целевого случая \(n=360\) решающее преимущество в том, что тяжелый этап зависит от \(S=\operatorname{rad}(360)=30\), а не от всех \(360\) исходных позиций.
ليكن \(\zeta_n=e^{2\pi i/n}\). العدد \(f(n,m)\) يساوي عدد المجموعات الجزئية \(A\subseteq\{0,1,\dots,n-1\}\) ذات الحجم \(m\) التي تحقق
$$\sum_{j\in A}\zeta_n^j=0.$$
من الناحية الهندسية نحن نختار \(m\) نقاط متساوية الوزن من بين \(n\) اتجاهات متباعدة بانتظام على دائرة الوحدة، ونطلب أن يكون مجموعها المتجهي صفراً تماماً. التجريب المباشر لكل \(\binom{n}{m}\) اختيار غير ممكن للحالة المطلوبة فعلياً، لذلك تبدأ التطبيقات باختزال المسألة إلى دورة أولية أصغر، ثم تعيد بناء الجواب الكامل باستعمال كثيرة حدود مولدة.
نكتب
$$S=\operatorname{rad}(n),\qquad G=\frac{n}{S},$$
حيث \(\operatorname{rad}(n)\) هو حاصل ضرب القواسم الأولية المختلفة للعدد \(n\). الفكرة المحورية هي أن قوى الأعداد الأولية المكررة يمكن فصلها تماماً، ولذلك يبقى جوهر العد التوافقي على الجزء الخالي من المربعات فقط، أي على \(S\).
لكل مجموعة جزئية \(A\subseteq\{0,\dots,n-1\}\) نعرّف كثيرة الحدود الدالة عليها:
$$F_A(x)=\sum_{j=0}^{n-1}\varepsilon_j x^j,\qquad \varepsilon_j\in\{0,1\},$$
بحيث تكون \(\varepsilon_j=1\) إذا وفقط إذا كان \(j\in A\). عندئذٍ \(|A|=\sum \varepsilon_j\)، ويصبح شرط المجموع الصفري
$$F_A(\zeta_n)=0.$$
إذن المسألة ليست حساباً عددياً تقريبياً على الدائرة، بل سؤالاً جبرياً: متى تنعدم كثيرة حدود بمعاملات \(0/1\) عند جذر وحدة أولي من الرتبة \(n\)؟
نجمع الأسس بحسب الباقي modulo \(G\):
$$F_A(x)=\sum_{r=0}^{G-1}x^r B_r(x^G),$$
حيث
$$B_r(y)=\sum_{q=0}^{S-1}\varepsilon_{r+qG}y^q.$$
وبما أن \(\zeta_n^G=\zeta_S\)، فإن التقييم يعطي
$$F_A(\zeta_n)=\sum_{r=0}^{G-1}\zeta_n^r B_r(\zeta_S).$$
ولأن \(n\) و\(S\) يملكان نفس مجموعة القواسم الأولية، نحصل على
$$[\mathbb{Q}(\zeta_n):\mathbb{Q}(\zeta_S)]=\frac{\varphi(n)}{\varphi(S)}=\frac{n}{S}=G.$$
ومن ثم تكون الأعداد \(1,\zeta_n,\zeta_n^2,\dots,\zeta_n^{G-1}\) مستقلة خطياً فوق \(\mathbb{Q}(\zeta_S)\). لذلك يكون المجموع الكلي صفراً إذا وفقط إذا انعدمت كل كتلة على حدة:
$$F_A(\zeta_n)=0\iff B_r(\zeta_S)=0\quad\text{for all }r=0,\dots,G-1.$$
أي أن كل فئة بواقي modulo \(G\) تتصرف كنسخة مستقلة ومُدارة فقط من دورة طولها \(S\). هذا هو الاختزال الحاسم الذي تعتمد عليه الخوارزمية.
ليكن \(c_k\) عدد المجموعات الجزئية ذات الحجم \(k\) من \(\{0,\dots,S-1\}\) التي يكون مجموع جذور الوحدة من الرتبة \(S\) المقابلة لها مساوياً للصفر. ولأي مجموعة \(T\) من هذا النوع نعرّف
$$F_T(x)=\sum_{q\in T}x^q.$$
وبما أن \(\zeta_S\) جذر وحدة أولي من الرتبة \(S\)، فإن كثير حدوده الأدنى فوق \(\mathbb{Q}\) هو \(\Phi_S(x)\). لذا
$$F_T(\zeta_S)=0\iff \Phi_S(x)\mid F_T(x).$$
وهكذا تصبح المسألة الفرعية: بين جميع كثيرات الحدود ذات المعاملات \(0/1\) والدرجة الأصغر من \(S\)، نعدّ تلك التي تمثل العنصر الصفري في حلقة خارج القسمة
$$\mathbb{Z}[x]/(\Phi_S(x)).$$
التطبيقات تمثل كل قوة \(x^q\) بواسطة متجه معاملات بعد الاختزال modulo \(\Phi_S(x)\)، وبُعد هذا المتجه هو \(\varphi(S)\). وتكون المجموعة الجزئية صحيحة بالضبط عندما يكون مجموع هذه المتجهات هو المتجه الصفري.
تُقسَّم الأسس وعددها \(S\) إلى نصفين. لكل مجموعة جزئية من النصف الأيسر تحسب الخوارزمية مجموعها المتجهي في \(\mathbb{Z}[x]/(\Phi_S(x))\)، وتخزن حجمها، وتسجل عدد مرات ظهور ذلك المتجه. ثم تُعدَّد مجموعات النصف الأيمن، ويؤخذ السالب لمجموعها المتجهي، ثم يُبحث عن المطابقات في جدول النصف الأيسر. فإذا أعطت مجموعة يسارية حجمها \(a\) ومجموعة يمينية حجمها \(b\) متجهين متعاكسين، كان اتحادهما مجموعة صفرية من الحجم \(a+b\).
بهذا المرور الواحد بطريقة meet-in-the-middle نحصل على كل القيم \(c_k\) من أجل \(0\le k\le m\)، وليس على قيمة واحدة فقط. ولهذا تصبح مرحلة كثيرة الحدود اللاحقة مباشرة ودقيقة.
لكتلة أولية واحدة نعرّف كثيرة الحدود المولدة العادية
$$P_S(t)=\sum_{k=0}^{S}c_k t^k.$$
وبما أن الكتل \(G\) مستقلة، فإن اختيار مجموعة صحيحة على دورة \(n\) الكاملة يكافئ اختيار مجموعة صفرية مستقلة على دورة \(S\) داخل كل كتلة. الأحجام تتجمع، ولذلك تكون كثيرة الحدود المولدة الكلية
$$P_S(t)^G.$$
ومن ثم
$$\boxed{f(n,m)=\left[t^m\right]P_S(t)^G.}$$
وهذه هي الصيغة التي تحسبها تطبيقات C++ وPython وJava حرفياً.
هنا \(n=12\)، وبالتالي \(S=\operatorname{rad}(12)=6\) و\(G=12/6=2\). على دورة سداسية واحدة يمكن تصنيف المجموعات الصفرية بسهولة هندسياً:
$$c_0=1,\qquad c_2=3,\qquad c_3=2,\qquad c_4=3,\qquad c_6=1,$$
وجميع القيم الأخرى لـ \(c_k\) تساوي الصفر. لذلك
$$P_6(t)=1+3t^2+2t^3+3t^4+t^6.$$
نحن نحتاج فقط إلى معامل \(t^4\)، لذا يمكن تجاهل الحدود ذات الدرجة الأكبر من \(4\):
$$f(12,4)=\left[t^4\right](1+3t^2+2t^3+3t^4)^2.$$
المساهمة في \(t^4\) تأتي من الحدود \(1\cdot 3t^4\) و\(3t^4\cdot 1\) و\(3t^2\cdot 3t^2\). ومن ثم
$$f(12,4)=3+3+9=15,$$
وهو نفس مقدار التحقق الصغير المستخدم في التطبيقات.
تحسب الخوارزمية أولاً \(S=\operatorname{rad}(n)\) و\(G=n/S\). ثم تبني كثيرة الحدود الدورية \(\Phi_S(x)\) انطلاقاً من الهوية \(x^k-1=\prod_{d\mid k}\Phi_d(x)\)، وبعد ذلك تختزل قوى \(x\) إلى متجهات معاملات modulo \(\Phi_S(x)\). وبالاعتماد على هذه المتجهات تنفذ مرحلة العد بطريقة meet-in-the-middle وتحصل دفعة واحدة على جميع المعاملات \(c_0,c_1,\dots,c_m\) الخاصة بكتلة أولية واحدة.
بعد ذلك تُنشأ كثيرة الحدود \(P_S(t)\) وتُضرب في نفسها \(G\) مرات، مع حذف كل الحدود التي تتجاوز درجتها \(m\) بعد كل عملية ضرب لأن المطلوب في النهاية هو المعامل \(\left[t^m\right]\) فقط. جميع الحسابات تتم بأعداد صحيحة دقيقة تماماً: Python يستعمل أعداداً صحيحة غير محدودة الطول، وJava يستخدم أعداداً صحيحة اعتباطية الدقة، أما C++ فيحافظ على تمثيل صريح للأعداد الكبيرة، ولذلك لا يوجد أي أخذ لباقي قسمة يمكن أن يخفي الحمل أو الإلغاء.
ليكن \(d=\varphi(S)\). بناء تمثيل حلقة خارج القسمة واستخدامه يكلف زمناً كثير حدود في \(S\) و\(d\)، وهو صغير مقارنة بمرحلة تعداد المجموعات الجزئية. مرحلة meet-in-the-middle تعدد تقريباً \(2^{S/2}\) مجموعة جزئية في كل جانب وتعالج متجهات طولها \(d\)، لذا يمكن النظر إلى كلفتها العملية على أنها نحو \(O(2^{S/2}d)\) من العمل المعتمد على الجداول المبعثرة، مع ذاكرة مقدارها \(O(2^{S/2})\). أما مرحلة كثيرات الحدود فتقوم بـ \(G\) التفافات مقطوعة حتى الدرجة \(m\)، أي \(O(Gm^2)\) من العمليات الدقيقة على المعاملات، بينما تعتمد كلفة البتات الفعلية على عدد أرقام الجواب النهائي. في الحالة المستهدفة \(n=360\)، الفائدة الأساسية هي أن مرحلة التعداد الصعبة تعتمد على \(S=\operatorname{rad}(360)=30\) فقط، لا على المواضع الأصلية البالغ عددها \(360\).