The Chess Sliders problem leads to a counting function \(L(N,K)\). For the required parameters \(N=10^9\) and \(K=10^{15}\), a direct combinatorial enumeration is hopeless, so the goal is to evaluate the answer modulo \(p^2\) with
$$p=10{,}000{,}019.$$
The implementations show that the practical route is to replace the original counting problem by a finite alternating sum, then evaluate each summand through coefficient extraction and p-adic binomial arithmetic.
The formula used by the implementations is
$$L(N,K)=\sum_{j=0}^{J}(-1)^{Nj}\binom{N}{j}\,c\bigl(N(N-2j),\,K-Nj\bigr)\pmod{p^2},\qquad J=\left\lfloor\frac{K}{N}\right\rfloor,$$
where \(c(m,k)\) is a coefficient extracted from the algebraic series \(\lambda_+(x)\) that appears in the combinatorial derivation. The rest of the work is making this expression computable modulo \(p^2\).
The outer index only runs up to
$$J=\left\lfloor\frac{K}{N}\right\rfloor,$$
because the second argument of \(c(m,k)\) is \(k=K-Nj\), which becomes negative once \(j>J\). So the chess-slider count is already reduced to a finite sum of about \(K/N\) terms rather than an exponential search over configurations.
For the actual input,
$$J=\left\lfloor\frac{10^{15}}{10^9}\right\rfloor=10^6,$$
which is large but still feasible if each term can be evaluated quickly.
The implementations never expand \(\lambda_+(x)\) term by term. Instead they use Lagrange inversion, which gives, for \(k\ge 1\),
$$c(m,k)=[x^k]\lambda_+(x)^m=\frac{m}{k}\binom{m-k-1}{k-1}.$$
This is the key simplification: a coefficient of an algebraic series becomes a single binomial coefficient multiplied by \(m/k\). The constant-term case is handled separately:
$$c(m,0)=\begin{cases} 1,&m=0,\\ 0,&m\ne 0. \end{cases}$$
That boundary value is essential for the last term in small validation examples.
Now we must compute \(\binom{n}{r}\pmod{p^2}\) when \(n\) and \(r\) may be enormous. Let
$$v_p(n!)=\sum_{t\ge 1}\left\lfloor\frac{n}{p^t}\right\rfloor$$
be Legendre's formula. Then
$$e=v_p\!\left(\binom{n}{r}\right)=v_p(n!)-v_p(r!)-v_p((n-r)!).$$
If \(e\ge 2\), then the binomial coefficient is divisible by \(p^2\), so it is \(0\) modulo \(p^2\). Otherwise write
$$n!=p^{v_p(n!)}\,n!_{(p)},$$
where \(n!_{(p)}\) is the factorial with all factors of \(p\) removed. Since the remaining denominator is now coprime to \(p\), it is invertible modulo \(p^2\), and therefore
$$\binom{n}{r}\equiv p^e\cdot\frac{n!_{(p)}}{r!_{(p)}(n-r)!_{(p)}}\pmod{p^2}.$$
So the real task is to compute these p-free factorial parts efficiently.
Write
$$n=qp+r,\qquad 0\le r<p.$$
Splitting \(1,2,\dots,n\) into complete blocks of length \(p\) and one final partial block gives the congruence
$$n!_{(p)}\equiv q!_{(p)}\cdot\bigl((p-1)!\bigr)^q\cdot r!\cdot\bigl(1+qp\,H_r\bigr)\pmod{p^2},$$
where
$$H_r=\sum_{i=1}^{r} i^{-1}\pmod{p^2}.$$
The harmonic factor comes from
$$\prod_{i=1}^{r}(qp+i)=r!\prod_{i=1}^{r}\left(1+\frac{qp}{i}\right)\equiv r!\left(1+qp\sum_{i=1}^{r}\frac{1}{i}\right)\pmod{p^2}.$$
Each recursive step divides the argument by \(p\), so the depth is only \(O(\log_p n)\), which is tiny here.
The alternating sum needs \(\binom{N}{j}\) for every \(0\le j\le J\). Instead of recomputing each binomial from scratch, the implementations use the recurrence
$$\binom{N}{j+1}=\binom{N}{j}\cdot\frac{N-j}{j+1}\pmod{p^2}.$$
For the actual input, \(J=10^6<p\), so every denominator \(j+1\) is invertible modulo \(p^2\). This turns the whole row into a linear-time precomputation.
For each \(j\), define
$$m_j=N(N-2j),\qquad k_j=K-Nj.$$
Then evaluate \(c(m_j,k_j)\) using Step 2, compute the required binomial coefficient modulo \(p^2\) via Steps 3 and 4, multiply by \(\binom{N}{j}\), apply the sign \((-1)^{Nj}\), and add the result modulo \(p^2\).
Because
$$(-1)^{Nj}=\begin{cases} 1,&N\text{ is even},\\ (-1)^j,&N\text{ is odd}, \end{cases}$$
the sign rule is especially cheap to evaluate.
This is the smallest checkpoint used by the implementations. Here
$$J=\left\lfloor\frac{2}{2}\right\rfloor=1,$$
so there are two terms.
For \(j=0\),
$$m_0=2(2-0)=4,\qquad k_0=2,\qquad \binom{2}{0}=1,$$
hence
$$c(4,2)=\frac{4}{2}\binom{1}{1}=2.$$
The first contribution is \(1\cdot 2=2\).
For \(j=1\),
$$m_1=2(2-2)=0,\qquad k_1=0,\qquad \binom{2}{1}=2.$$
The boundary rule gives \(c(0,0)=1\), so the second contribution is \(2\cdot 1=2\). Since \(N\) is even, no sign change occurs. Therefore
$$L(2,2)=2+2=4,$$
matching the validation value.
The C++, Python, and Java implementations follow the same mathematical pipeline. First they precompute factorial residues up to \(p-1\), modular inverses of the small nonzero residues, and the cumulative harmonic sums \(H_r\). Those tables are exactly what the p-free factorial recursion needs.
Next they generate the entire row \(\binom{N}{0},\binom{N}{1},\dots,\binom{N}{J}\) with the one-step recurrence from Step 5. After that they iterate over \(j=0,\dots,J\), evaluate the coefficient \(c(m_j,k_j)\), compute the associated binomial coefficient modulo \(p^2\), multiply by \(\binom{N}{j}\), apply the alternating sign, and accumulate the total.
The C++ implementation additionally splits the range of \(j\) across available hardware threads and combines the partial sums at the end. The Python and Java implementations perform the same arithmetic serially, but the underlying mathematics is identical.
Let \(J=\lfloor K/N\rfloor\). Precomputing factorial residues, inverses, and harmonic sums up to \(p-1\) costs \(O(p)\) time and \(O(p)\) memory. Building the row \(\binom{N}{j}\) costs \(O(J)\) time and \(O(J)\) memory. Each summand then needs only \(O(\log_p K)\) p-adic recursive work, so the whole accumulation is \(O(J\log_p K)\), which is essentially linear here because \(p\approx 10^7\). The total memory usage is \(O(p+J)\), and the C++ version reduces wall-clock time further by parallelizing the outer sum.
Das Problem Chess Sliders führt auf eine Zählfunktion \(L(N,K)\). Für die geforderten Werte \(N=10^9\) und \(K=10^{15}\) ist eine direkte Aufzählung ausgeschlossen, daher muss das Ergebnis modulo \(p^2\) mit
$$p=10{,}000{,}019$$
berechnet werden. Die Implementierungen zeigen, dass man die ursprüngliche Kombinatorik durch eine endliche alternierende Summe ersetzt und deren Summanden dann mit Koeffizientenextraktion und p-adischer Binomialarithmetik auswertet.
Die verwendete Formel lautet
$$L(N,K)=\sum_{j=0}^{J}(-1)^{Nj}\binom{N}{j}\,c\bigl(N(N-2j),\,K-Nj\bigr)\pmod{p^2},\qquad J=\left\lfloor\frac{K}{N}\right\rfloor,$$
wobei \(c(m,k)\) ein Koeffizient der algebraischen Reihe \(\lambda_+(x)\) ist, die in der Herleitung des Problems auftritt. Die restliche Arbeit besteht darin, diesen Ausdruck effizient modulo \(p^2\) auszuwerten.
Der äußere Index läuft nur bis
$$J=\left\lfloor\frac{K}{N}\right\rfloor,$$
denn das zweite Argument von \(c(m,k)\) ist \(k=K-Nj\) und wird für \(j>J\) negativ. Damit wird die Chess-Sliders-Zählung bereits auf ungefähr \(K/N\) Summanden reduziert, statt auf eine exponentielle Suche über Konfigurationen.
Für die eigentlichen Eingaben gilt
$$J=\left\lfloor\frac{10^{15}}{10^9}\right\rfloor=10^6,$$
also eine große, aber immer noch handhabbare Anzahl von Termen.
Die Implementierungen entwickeln \(\lambda_+(x)\) nicht explizit. Stattdessen liefert die Lagrange-Inversion für \(k\ge 1\) die geschlossene Formel
$$c(m,k)=[x^k]\lambda_+(x)^m=\frac{m}{k}\binom{m-k-1}{k-1}.$$
Genau hier liegt die zentrale mathematische Verdichtung: Ein Koeffizient einer algebraischen Reihe wird zu einem einzelnen Binomialkoeffizienten mit dem Faktor \(m/k\). Der konstante Term wird gesondert behandelt:
$$c(m,0)=\begin{cases} 1,&m=0,\\ 0,&m\ne 0. \end{cases}$$
Diese Randbedingung ist in kleinen Prüfbeispielen unverzichtbar.
Nun muss \(\binom{n}{r}\pmod{p^2}\) für sehr große \(n\) und \(r\) bestimmt werden. Mit Legendre gilt
$$v_p(n!)=\sum_{t\ge 1}\left\lfloor\frac{n}{p^t}\right\rfloor,$$
also
$$e=v_p\!\left(\binom{n}{r}\right)=v_p(n!)-v_p(r!)-v_p((n-r)!).$$
Falls \(e\ge 2\), ist der Binomialkoeffizient durch \(p^2\) teilbar und damit modulo \(p^2\) gleich \(0\). Sonst schreibt man
$$n!=p^{v_p(n!)}\,n!_{(p)},$$
wobei \(n!_{(p)}\) den von allen \(p\)-Faktoren bereinigten Fakultätsteil bezeichnet. Dann folgt
$$\binom{n}{r}\equiv p^e\cdot\frac{n!_{(p)}}{r!_{(p)}(n-r)!_{(p)}}\pmod{p^2}.$$
Die Aufgabe reduziert sich also auf eine schnelle Berechnung dieser p-freien Fakultätsteile.
Schreibe
$$n=qp+r,\qquad 0\le r<p.$$
Durch Zerlegung von \(1,2,\dots,n\) in volle Blöcke der Länge \(p\) und einen letzten Teilblock erhält man
$$n!_{(p)}\equiv q!_{(p)}\cdot\bigl((p-1)!\bigr)^q\cdot r!\cdot\bigl(1+qp\,H_r\bigr)\pmod{p^2},$$
mit
$$H_r=\sum_{i=1}^{r} i^{-1}\pmod{p^2}.$$
Der harmonische Korrekturterm stammt aus
$$\prod_{i=1}^{r}(qp+i)=r!\prod_{i=1}^{r}\left(1+\frac{qp}{i}\right)\equiv r!\left(1+qp\sum_{i=1}^{r}\frac{1}{i}\right)\pmod{p^2}.$$
Da jeder Rekursionsschritt das Argument durch \(p\) teilt, ist die Tiefe nur \(O(\log_p n)\).
Für die alternierende Summe werden alle Werte \(\binom{N}{j}\) mit \(0\le j\le J\) benötigt. Die Implementierungen verwenden dafür die Rekursion
$$\binom{N}{j+1}=\binom{N}{j}\cdot\frac{N-j}{j+1}\pmod{p^2}.$$
Beim echten Input gilt \(J=10^6<p\), daher ist jeder Nenner \(j+1\) modulo \(p^2\) invertierbar. Das macht diese Vorberechnung linear.
Für jedes \(j\) definiert man
$$m_j=N(N-2j),\qquad k_j=K-Nj.$$
Dann wird \(c(m_j,k_j)\) aus Schritt 2 bestimmt, der dazugehörige Binomialkoeffizient mit den Schritten 3 und 4 modulo \(p^2\) ausgewertet, mit \(\binom{N}{j}\) multipliziert, das Vorzeichen \((-1)^{Nj}\) angewendet und alles modulo \(p^2\) aufsummiert.
Wegen
$$(-1)^{Nj}=\begin{cases} 1,&N\text{ gerade},\\ (-1)^j,&N\text{ ungerade}, \end{cases}$$
ist die Vorzeichenbehandlung besonders einfach.
Dies ist der kleinste Prüffall aus den Implementierungen. Hier gilt
$$J=\left\lfloor\frac{2}{2}\right\rfloor=1,$$
also gibt es genau zwei Summanden.
Für \(j=0\) erhält man
$$m_0=2(2-0)=4,\qquad k_0=2,\qquad \binom{2}{0}=1,$$
und damit
$$c(4,2)=\frac{4}{2}\binom{1}{1}=2.$$
Der erste Beitrag ist also \(1\cdot 2=2\).
Für \(j=1\) gilt
$$m_1=2(2-2)=0,\qquad k_1=0,\qquad \binom{2}{1}=2.$$
Die Randregel liefert \(c(0,0)=1\), also ist der zweite Beitrag \(2\cdot 1=2\). Da \(N\) gerade ist, tritt kein Vorzeichenwechsel auf. Somit
$$L(2,2)=2+2=4,$$
genau wie im Kontrollwert.
Die C++-, Python- und Java-Implementierungen folgen derselben mathematischen Pipeline. Zuerst werden Fakultätsreste bis \(p-1\), modulare Inverse der kleinen Nichtnullreste und die kumulierten harmonischen Summen \(H_r\) vorab berechnet. Genau diese Tabellen benötigt die Rekursion für den p-freien Fakultätsteil.
Anschließend wird die komplette Zeile \(\binom{N}{0},\binom{N}{1},\dots,\binom{N}{J}\) über die Ein-Schritt-Rekursion aufgebaut. Danach iterieren die Programme über \(j=0,\dots,J\), berechnen den Koeffizienten \(c(m_j,k_j)\), werten den nötigen Binomialkoeffizienten modulo \(p^2\) aus, multiplizieren mit \(\binom{N}{j}\), berücksichtigen das Vorzeichen und akkumulieren die Summe.
Die C++-Implementierung teilt den Bereich der \(j\)-Werte zusätzlich auf mehrere Hardware-Threads auf und reduziert am Ende die Teilsummen. Python und Java führen dieselbe Arithmetik seriell aus, aber die mathematische Methode bleibt identisch.
Mit \(J=\lfloor K/N\rfloor\) kostet die Vorberechnung der Fakultätsreste, Inversen und harmonischen Summen bis \(p-1\) insgesamt \(O(p)\) Zeit und \(O(p)\) Speicher. Der Aufbau der Zeile \(\binom{N}{j}\) kostet \(O(J)\) Zeit und \(O(J)\) Speicher. Jeder Summand benötigt danach nur \(O(\log_p K)\) p-adische Rekursionsarbeit, sodass die vollständige Akkumulation \(O(J\log_p K)\) kostet und in dieser Aufgabe praktisch linear ist, weil \(p\approx 10^7\) bereits sehr groß ist. Insgesamt liegt der Speicherbedarf bei \(O(p+J)\).
Chess Sliders problemi bir \(L(N,K)\) sayım fonksiyonuna indirgeniyor. İstenen parametreler \(N=10^9\) ve \(K=10^{15}\) olduğu için doğrudan kombinatorik tarama mümkün değil; bu yüzden sonuç
$$p=10{,}000{,}019$$
asalı için \(p^2\) modunda hesaplanıyor. Uygulamalar, asıl problemin sonlu bir alternatif toplam haline getirildiğini ve her terimin katsayı çıkarımı ile p-adik binom aritmetiği üzerinden değerlendirildiğini gösteriyor.
Uygulamalarda kullanılan temel formül şudur:
$$L(N,K)=\sum_{j=0}^{J}(-1)^{Nj}\binom{N}{j}\,c\bigl(N(N-2j),\,K-Nj\bigr)\pmod{p^2},\qquad J=\left\lfloor\frac{K}{N}\right\rfloor.$$
Burada \(c(m,k)\), problemin kombinatorik türetiminde ortaya çıkan \(\lambda_+(x)\) cebirsel serisinden alınan bir katsayıdır. Geriye kalan iş, bu ifadeyi \(p^2\) modunda pratik biçimde hesaplamaktır.
Dış indis yalnızca
$$J=\left\lfloor\frac{K}{N}\right\rfloor$$
değerine kadar gider; çünkü \(c(m,k)\) içindeki ikinci parametre \(k=K-Nj\) olup \(j>J\) olduğunda negatife düşer. Böylece satranç yerleşimlerini doğrudan saymak yerine, yaklaşık \(K/N\) terimli sonlu bir toplam hesaplanır.
Gerçek girdi için
$$J=\left\lfloor\frac{10^{15}}{10^9}\right\rfloor=10^6$$
elde edilir. Bu sayı büyük olsa da, terim başına maliyet küçük tutulursa rahatça yönetilebilir.
Uygulamalar \(\lambda_+(x)\) serisini terim terim açmaz. Bunun yerine Lagrange inversion kullanılır ve \(k\ge 1\) için
$$c(m,k)=[x^k]\lambda_+(x)^m=\frac{m}{k}\binom{m-k-1}{k-1}$$
formülü elde edilir. Asıl matematiksel kazanım budur: cebirsel bir seriden katsayı çekme işi, tek bir binom katsayısı ile \(m/k\) çarpanına indirgenir. Sabit terim ayrıca ele alınır:
$$c(m,0)=\begin{cases} 1,&m=0,\\ 0,&m\ne 0. \end{cases}$$
Küçük doğrulama örneklerinde son terimin doğru çıkması için bu sınır durumu gereklidir.
Şimdi \(\binom{n}{r}\pmod{p^2}\) değerini, \(n\) ve \(r\) çok büyük olsa bile hesaplamak gerekir. Legendre formülü
$$v_p(n!)=\sum_{t\ge 1}\left\lfloor\frac{n}{p^t}\right\rfloor$$
ile verilir. O halde binom katsayısındaki \(p\) üssü
$$e=v_p\!\left(\binom{n}{r}\right)=v_p(n!)-v_p(r!)-v_p((n-r)!)$$
olur. Eğer \(e\ge 2\) ise katsayı \(p^2\) ile bölünür ve mod \(p^2\) altında doğrudan \(0\) olur. Aksi halde
$$n!=p^{v_p(n!)}\,n!_{(p)}$$
yazılır; burada \(n!_{(p)}\), faktöriyeldeki tüm \(p\) çarpanları atıldıktan sonra kalan kısımdır. Böylece
$$\binom{n}{r}\equiv p^e\cdot\frac{n!_{(p)}}{r!_{(p)}(n-r)!_{(p)}}\pmod{p^2}$$
elde edilir. Yani asıl mesele p'siz faktöriyel parçalarını hızlı bulmaktır.
\(n\) sayısını
$$n=qp+r,\qquad 0\le r<p$$
şeklinde yazalım. \(1,2,\dots,n\) aralığını \(p\) uzunluklu tam bloklara ve bir son parçaya ayırınca
$$n!_{(p)}\equiv q!_{(p)}\cdot\bigl((p-1)!\bigr)^q\cdot r!\cdot\bigl(1+qp\,H_r\bigr)\pmod{p^2}$$
bağıntısı gelir. Burada
$$H_r=\sum_{i=1}^{r} i^{-1}\pmod{p^2}$$
kümülatif harmonik toplamdır. Harmonik düzeltme şu açılımdan gelir:
$$\prod_{i=1}^{r}(qp+i)=r!\prod_{i=1}^{r}\left(1+\frac{qp}{i}\right)\equiv r!\left(1+qp\sum_{i=1}^{r}\frac{1}{i}\right)\pmod{p^2}.$$
Her özyineleme adımı girdiyi \(p\)'ye böldüğü için derinlik yalnızca \(O(\log_p n)\) olur.
Alternatif toplamda \(0\le j\le J\) için tüm \(\binom{N}{j}\) değerlerine ihtiyaç vardır. Bunlar baştan hesaplanmak yerine
$$\binom{N}{j+1}=\binom{N}{j}\cdot\frac{N-j}{j+1}\pmod{p^2}$$
özyinelemesiyle sırayla üretilir. Gerçek girdide \(J=10^6<p\) olduğundan her \(j+1\) değeri mod \(p^2\) altında terslenebilir; böylece bu hazırlık lineer zamana iner.
Her \(j\) için
$$m_j=N(N-2j),\qquad k_j=K-Nj$$
tanımlanır. Sonra Step 2'deki formülle \(c(m_j,k_j)\) bulunur, Step 3 ve 4 kullanılarak gerekli binom katsayısı \(p^2\) modunda hesaplanır, \(\binom{N}{j}\) ile çarpılır, \((-1)^{Nj}\) işareti uygulanır ve toplam mod \(p^2\) altında biriktirilir.
Çünkü
$$(-1)^{Nj}=\begin{cases} 1,&N\text{ çiftse},\\ (-1)^j,&N\text{ tekse}, \end{cases}$$
işaret kontrolü çok ucuzdur.
Bu, uygulamalarda kullanılan en küçük kontrol örneğidir. Burada
$$J=\left\lfloor\frac{2}{2}\right\rfloor=1$$
olur; yani iki terim vardır.
\(j=0\) için
$$m_0=2(2-0)=4,\qquad k_0=2,\qquad \binom{2}{0}=1$$
ve dolayısıyla
$$c(4,2)=\frac{4}{2}\binom{1}{1}=2.$$
İlk katkı \(1\cdot 2=2\) olur.
\(j=1\) için
$$m_1=2(2-2)=0,\qquad k_1=0,\qquad \binom{2}{1}=2$$
elde edilir. Sınır kuralı \(c(0,0)=1\) verdiğinden ikinci katkı \(2\cdot 1=2\) olur. \(N\) çift olduğu için işaret değişmez. Sonuç:
$$L(2,2)=2+2=4,$$
ki doğrulama değeriyle aynıdır.
C++, Python ve Java uygulamaları aynı matematiksel hattı izler. İlk olarak \(p-1\)'e kadar faktöriyel kalıntıları, küçük sıfır olmayan kalıntıların modüler tersleri ve kümülatif harmonik toplamlar \(H_r\) önceden hesaplanır. p'siz faktöriyel özyinelemesinin ihtiyaç duyduğu tüm veri bunlardır.
Daha sonra \(\binom{N}{0},\binom{N}{1},\dots,\binom{N}{J}\) satırı Step 5'teki tek adımlı bağıntıyla üretilir. Ardından \(j=0,\dots,J\) boyunca gidilir; ilgili \(c(m_j,k_j)\) katsayısı bulunur, gereken binom katsayısı \(p^2\) modunda değerlendirilir, \(\binom{N}{j}\) ile çarpılır, işaret uygulanır ve toplam biriktirilir.
C++ uygulaması ayrıca \(j\) aralığını mevcut donanım iş parçacıklarına bölüp kısmi toplamları sonunda birleştirir. Python ve Java sürümleri aynı aritmetiği tek iş parçacığında yapar; değişen yalnızca yürütme biçimidir, matematik değildir.
\(J=\lfloor K/N\rfloor\) olsun. \(p-1\)'e kadar faktöriyel kalıntıları, tersler ve harmonik toplamların ön hesabı \(O(p)\) zaman ve \(O(p)\) bellek ister. \(\binom{N}{j}\) satırının kurulması \(O(J)\) zaman ve \(O(J)\) bellek kullanır. Her terim için gereken p-adik özyineleme maliyeti yalnızca \(O(\log_p K)\) olduğundan toplam birikim \(O(J\log_p K)\) olur; bu problemde \(p\approx 10^7\) çok büyük olduğu için pratikte neredeyse lineerdir. Toplam bellek kullanımı \(O(p+J)\) düzeyindedir; C++ sürümü dış toplamı paralelleştirerek duvar saati süresini daha da düşürür.
El problema Chess Sliders conduce a una función de conteo \(L(N,K)\). Para los valores pedidos \(N=10^9\) y \(K=10^{15}\), una enumeración directa es imposible, así que el objetivo es calcular el resultado módulo \(p^2\) con
$$p=10{,}000{,}019.$$
Las implementaciones muestran que la vía práctica consiste en transformar la combinatoria original en una suma alternante finita y luego evaluar cada término mediante extracción de coeficientes y aritmética binomial p-ádica.
La fórmula utilizada es
$$L(N,K)=\sum_{j=0}^{J}(-1)^{Nj}\binom{N}{j}\,c\bigl(N(N-2j),\,K-Nj\bigr)\pmod{p^2},\qquad J=\left\lfloor\frac{K}{N}\right\rfloor.$$
Aquí \(c(m,k)\) es un coeficiente tomado de la serie algebraica \(\lambda_+(x)\) que aparece en la derivación combinatoria del problema. Todo el trabajo posterior consiste en hacer computable esta expresión módulo \(p^2\).
El índice exterior solo llega hasta
$$J=\left\lfloor\frac{K}{N}\right\rfloor,$$
porque el segundo argumento de \(c(m,k)\) es \(k=K-Nj\), y pasa a ser negativo cuando \(j>J\). Por tanto, el conteo de configuraciones se comprime desde una búsqueda combinatoria gigantesca hasta una suma con aproximadamente \(K/N\) términos.
En la entrada real,
$$J=\left\lfloor\frac{10^{15}}{10^9}\right\rfloor=10^6,$$
de modo que el bucle exterior sigue siendo grande, pero perfectamente abordable si cada término se calcula con rapidez.
Las implementaciones no expanden \(\lambda_+(x)\) término a término. En su lugar usan inversión de Lagrange, que para \(k\ge 1\) da
$$c(m,k)=[x^k]\lambda_+(x)^m=\frac{m}{k}\binom{m-k-1}{k-1}.$$
Este es el paso matemático central: un coeficiente de una serie algebraica se convierte en un único coeficiente binomial multiplicado por \(m/k\). El caso constante se trata aparte:
$$c(m,0)=\begin{cases} 1,&m=0,\\ 0,&m\ne 0. \end{cases}$$
Esa condición de borde es necesaria para que los ejemplos pequeños salgan correctamente.
Ahora hay que obtener \(\binom{n}{r}\pmod{p^2}\) aun cuando \(n\) y \(r\) sean muy grandes. Con la fórmula de Legendre,
$$v_p(n!)=\sum_{t\ge 1}\left\lfloor\frac{n}{p^t}\right\rfloor,$$
y por tanto
$$e=v_p\!\left(\binom{n}{r}\right)=v_p(n!)-v_p(r!)-v_p((n-r)!).$$
Si \(e\ge 2\), entonces \(\binom{n}{r}\) es múltiplo de \(p^2\) y vale \(0\) módulo \(p^2\). Si no, escribimos
$$n!=p^{v_p(n!)}\,n!_{(p)},$$
donde \(n!_{(p)}\) es la parte factorial con todos los factores \(p\) eliminados. Así obtenemos
$$\binom{n}{r}\equiv p^e\cdot\frac{n!_{(p)}}{r!_{(p)}(n-r)!_{(p)}}\pmod{p^2}.$$
De este modo, el problema se reduce a evaluar rápidamente esas partes libres de \(p\).
Escribimos
$$n=qp+r,\qquad 0\le r<p.$$
Al separar \(1,2,\dots,n\) en bloques completos de longitud \(p\) y un bloque final parcial, se obtiene
$$n!_{(p)}\equiv q!_{(p)}\cdot\bigl((p-1)!\bigr)^q\cdot r!\cdot\bigl(1+qp\,H_r\bigr)\pmod{p^2},$$
donde
$$H_r=\sum_{i=1}^{r} i^{-1}\pmod{p^2}.$$
La corrección armónica sale de
$$\prod_{i=1}^{r}(qp+i)=r!\prod_{i=1}^{r}\left(1+\frac{qp}{i}\right)\equiv r!\left(1+qp\sum_{i=1}^{r}\frac{1}{i}\right)\pmod{p^2}.$$
Cada llamada recursiva divide el argumento por \(p\), así que la profundidad es solo \(O(\log_p n)\).
La suma alternante necesita \(\binom{N}{j}\) para todos los \(j\) entre \(0\) y \(J\). En vez de recalcularlos, se usa
$$\binom{N}{j+1}=\binom{N}{j}\cdot\frac{N-j}{j+1}\pmod{p^2}.$$
Como en la entrada real \(J=10^6<p\), cada denominador \(j+1\) es invertible módulo \(p^2\). Eso convierte esta etapa en una precalculación lineal.
Para cada \(j\) definimos
$$m_j=N(N-2j),\qquad k_j=K-Nj.$$
Luego se evalúa \(c(m_j,k_j)\) con el paso 2, se calcula el binomial necesario módulo \(p^2\) con los pasos 3 y 4, se multiplica por \(\binom{N}{j}\), se aplica el signo \((-1)^{Nj}\) y se acumula todo módulo \(p^2\).
Como
$$(-1)^{Nj}=\begin{cases} 1,&N\text{ es par},\\ (-1)^j,&N\text{ es impar}, \end{cases}$$
la gestión del signo es muy barata.
Este es el control más pequeño usado por las implementaciones. Aquí
$$J=\left\lfloor\frac{2}{2}\right\rfloor=1,$$
así que aparecen dos términos.
Para \(j=0\),
$$m_0=2(2-0)=4,\qquad k_0=2,\qquad \binom{2}{0}=1,$$
y por tanto
$$c(4,2)=\frac{4}{2}\binom{1}{1}=2.$$
La primera contribución vale \(1\cdot 2=2\).
Para \(j=1\),
$$m_1=2(2-2)=0,\qquad k_1=0,\qquad \binom{2}{1}=2.$$
La regla de borde da \(c(0,0)=1\), así que la segunda contribución es \(2\cdot 1=2\). Como \(N\) es par, no hay cambio de signo. Luego
$$L(2,2)=2+2=4,$$
que coincide con el valor de validación.
Las implementaciones en C++, Python y Java siguen el mismo esquema matemático. Primero precalculan residuos factoriales hasta \(p-1\), inversos modulares de los residuos pequeños no nulos y las sumas armónicas acumuladas \(H_r\). Esas tablas son exactamente las que necesita la recurrencia de la parte factorial libre de \(p\).
Después generan toda la fila \(\binom{N}{0},\binom{N}{1},\dots,\binom{N}{J}\) usando la recurrencia del paso 5. A continuación recorren \(j=0,\dots,J\), evalúan \(c(m_j,k_j)\), calculan el binomial asociado módulo \(p^2\), multiplican por \(\binom{N}{j}\), aplican el signo alternante y acumulan la suma total.
La implementación en C++ además divide el rango de \(j\) entre varios hilos de hardware y reduce al final las sumas parciales. Las implementaciones en Python y Java hacen el mismo cálculo en serie, pero la matemática subyacente es exactamente la misma.
Sea \(J=\lfloor K/N\rfloor\). La precalculación de residuos factoriales, inversos y sumas armónicas hasta \(p-1\) cuesta \(O(p)\) tiempo y \(O(p)\) memoria. Construir la fila \(\binom{N}{j}\) cuesta \(O(J)\) tiempo y \(O(J)\) memoria. Después, cada término necesita solo \(O(\log_p K)\) trabajo p-ádico recursivo, así que la acumulación completa vale \(O(J\log_p K)\), que aquí es casi lineal porque \(p\approx 10^7\). El uso total de memoria es \(O(p+J)\), y la versión en C++ reduce aún más el tiempo real gracias a la paralelización del sumatorio exterior.
Chess Sliders 这个问题最终会落到一个计数函数 \(L(N,K)\) 上。对于题目要求的参数 \(N=10^9\)、\(K=10^{15}\)，根本不可能直接枚举原始组合对象，因此目标是把答案在
$$p=10{,}000{,}019$$
对应的模 \(p^2\) 下算出来。现有实现表明，真正可行的方法是先把原问题压缩成一个有限的交错求和，再把每一项变成代数级数的系数提取问题，最后用 p-adic 的二项式计算来完成整个求值。
实现所使用的核心公式是
$$L(N,K)=\sum_{j=0}^{J}(-1)^{Nj}\binom{N}{j}\,c\bigl(N(N-2j),\,K-Nj\bigr)\pmod{p^2},\qquad J=\left\lfloor\frac{K}{N}\right\rfloor.$$
其中 \(c(m,k)\) 是来自代数级数 \(\lambda_+(x)\) 的一个系数，这个级数来自题目的组合推导。剩下要做的事情，就是把这个表达式中的每一个部分都变成可以在模 \(p^2\) 下高效计算的对象。
外层指标只需要跑到
$$J=\left\lfloor\frac{K}{N}\right\rfloor,$$
因为 \(c(m,k)\) 的第二个参数是 \(k=K-Nj\)，一旦 \(j>J\)，这个值就会变成负数，不再有贡献。也就是说，原本庞大的计数问题先被压缩成大约 \(K/N\) 项的有限求和，而不是去做不可行的直接枚举。
在实际输入下，
$$J=\left\lfloor\frac{10^{15}}{10^9}\right\rfloor=10^6,$$
所以外层循环虽然不小，但如果每一项都能快速算出，就仍然是完全可控的。
实现并不会真的把 \(\lambda_+(x)\) 展开成幂级数后逐项取系数，因为那样代价太大。关键在于拉格朗日反演，它直接给出 \(k\ge 1\) 时的闭式：
$$c(m,k)=[x^k]\lambda_+(x)^m=\frac{m}{k}\binom{m-k-1}{k-1}.$$
这一步是整个数学化简的核心：一个代数级数的系数，直接变成了一个普通二项式系数再乘上 \(m/k\)。常数项需要单独处理：
$$c(m,0)=\begin{cases} 1,&m=0,\\ 0,&m\ne 0. \end{cases}$$
这个边界条件并不是装饰性的，它会直接影响最小验证样例中的最后一项。
接下来需要计算 \(\binom{n}{r}\pmod{p^2}\)，而这里的 \(n\) 与 \(r\) 都可能非常大。先用 Legendre 公式计算阶乘中 \(p\) 的指数：
$$v_p(n!)=\sum_{t\ge 1}\left\lfloor\frac{n}{p^t}\right\rfloor.$$
于是二项式系数中的 p-adic 估值就是
$$e=v_p\!\left(\binom{n}{r}\right)=v_p(n!)-v_p(r!)-v_p((n-r)!).$$
如果 \(e\ge 2\)，那么 \(\binom{n}{r}\) 已经被 \(p^2\) 整除，在模 \(p^2\) 下直接就是 \(0\)。如果 \(e=0\) 或 \(e=1\)，就把阶乘写成
$$n!=p^{v_p(n!)}\,n!_{(p)},$$
这里 \(n!_{(p)}\) 表示把所有 \(p\) 因子都剥离之后剩下的部分。这样一来，分母中的剩余部分与 \(p\) 互素，因此在模 \(p^2\) 下可逆，从而得到
$$\binom{n}{r}\equiv p^e\cdot\frac{n!_{(p)}}{r!_{(p)}(n-r)!_{(p)}}\pmod{p^2}.$$
所以真正需要解决的，不是普通的大整数阶乘，而是这些去掉 \(p\) 因子后的“p-free”阶乘部分。
把 \(n\) 写成
$$n=qp+r,\qquad 0\le r<p.$$
把区间 \(1,2,\dots,n\) 切成若干个长度为 \(p\) 的完整块，再加上最后一个不完整块之后，可以得到实现中使用的同余式：
$$n!_{(p)}\equiv q!_{(p)}\cdot\bigl((p-1)!\bigr)^q\cdot r!\cdot\bigl(1+qp\,H_r\bigr)\pmod{p^2},$$
其中
$$H_r=\sum_{i=1}^{r} i^{-1}\pmod{p^2}$$
是模 \(p^2\) 下的前缀调和和。这个调和修正项来自
$$\prod_{i=1}^{r}(qp+i)=r!\prod_{i=1}^{r}\left(1+\frac{qp}{i}\right)\equiv r!\left(1+qp\sum_{i=1}^{r}\frac{1}{i}\right)\pmod{p^2}.$$
每次递归都会把输入规模除以 \(p\)，因此深度只有 \(O(\log_p n)\)。由于这里的 \(p\) 已经非常大，这个递归实际上非常浅。
外层求和对所有 \(0\le j\le J\) 都需要 \(\binom{N}{j}\)。实现没有反复单独计算，而是使用递推关系
$$\binom{N}{j+1}=\binom{N}{j}\cdot\frac{N-j}{j+1}\pmod{p^2}.$$
在真实输入中，\(J=10^6<p\)，所以每个分母 \(j+1\) 在模 \(p^2\) 下都可逆。这使得整行二项式系数可以在线性时间内完成预处理。
对于每个 \(j\)，定义
$$m_j=N(N-2j),\qquad k_j=K-Nj.$$
然后用步骤 2 的公式求出 \(c(m_j,k_j)\)，再借助步骤 3 与步骤 4 计算所需的二项式系数模 \(p^2\) 的值，乘上 \(\binom{N}{j}\)，套用符号 \((-1)^{Nj}\)，最后把所有结果在模 \(p^2\) 下累加起来。
由于
$$(-1)^{Nj}=\begin{cases} 1,&N\text{ 为偶数},\\ (-1)^j,&N\text{ 为奇数}, \end{cases}$$
所以符号处理本身几乎没有成本。
这是实现里使用的最小检验点。此时
$$J=\left\lfloor\frac{2}{2}\right\rfloor=1,$$
因此只有两项。
当 \(j=0\) 时，
$$m_0=2(2-0)=4,\qquad k_0=2,\qquad \binom{2}{0}=1,$$
于是
$$c(4,2)=\frac{4}{2}\binom{1}{1}=2.$$
第一项贡献为 \(1\cdot 2=2\)。
当 \(j=1\) 时，
$$m_1=2(2-2)=0,\qquad k_1=0,\qquad \binom{2}{1}=2.$$
边界规则给出 \(c(0,0)=1\)，因此第二项贡献为 \(2\cdot 1=2\)。由于 \(N\) 是偶数，没有额外负号，所以
$$L(2,2)=2+2=4,$$
正好与实现中的验证值一致。
C++、Python 和 Java 三个实现走的是同一条数学路线。第一步是预计算三类表：到 \(p-1\) 为止的阶乘残值、小的非零剩余类在模 \(p^2\) 下的逆元，以及前缀调和和 \(H_r\)。这些表正是 p-free 阶乘递归所依赖的基础数据。
接下来，程序利用步骤 5 的递推式一次性生成整行 \(\binom{N}{0},\binom{N}{1},\dots,\binom{N}{J}\)。然后对每个 \(j=0,\dots,J\)，先求出对应的 \(c(m_j,k_j)\)，再算出相关二项式系数在模 \(p^2\) 下的值，乘上 \(\binom{N}{j}\)，根据 \((-1)^{Nj}\) 处理符号，最后把结果累加到总和中。
C++ 实现还会把 \(j\) 的区间切分给多个硬件线程，分别求出部分和，最后再合并。Python 与 Java 实现按单线程顺序完成相同的运算，但底层数学内容完全相同。
设 \(J=\lfloor K/N\rfloor\)。预计算到 \(p-1\) 的阶乘残值、逆元和调和和需要 \(O(p)\) 时间与 \(O(p)\) 内存。构造整行 \(\binom{N}{j}\) 需要 \(O(J)\) 时间与 \(O(J)\) 内存。之后，每一项只需要 \(O(\log_p K)\) 的 p-adic 递归工作，因此总求和代价是 \(O(J\log_p K)\)。由于这里 \(p\approx 10^7\) 已经很大，\(\log_p K\) 非常小，所以整体几乎就是线性的。总内存占用为 \(O(p+J)\)，而 C++ 版本还能通过并行化外层求和进一步降低实际运行时间。
Задача Chess Sliders сводится к вычислению некоторой функции подсчёта \(L(N,K)\). Для требуемых параметров \(N=10^9\) и \(K=10^{15}\) прямой перебор невозможен, поэтому ответ нужно получить по модулю \(p^2\), где
$$p=10{,}000{,}019.$$
Реализации показывают, что практичный путь состоит в замене исходной комбинаторики конечной знакопеременной суммой, а затем в вычислении каждого её члена через извлечение коэффициента и p-адическую арифметику биномиальных коэффициентов.
Используемая формула такова:
$$L(N,K)=\sum_{j=0}^{J}(-1)^{Nj}\binom{N}{j}\,c\bigl(N(N-2j),\,K-Nj\bigr)\pmod{p^2},\qquad J=\left\lfloor\frac{K}{N}\right\rfloor.$$
Здесь \(c(m,k)\) — коэффициент при степени в алгебраическом ряде \(\lambda_+(x)\), возникающем в комбинаторическом выводе задачи. Остаётся сделать все части этого выражения эффективно вычислимыми по модулю \(p^2\).
Внешний индекс идёт только до
$$J=\left\lfloor\frac{K}{N}\right\rfloor,$$
потому что вторым аргументом функции \(c(m,k)\) является \(k=K-Nj\), а при \(j>J\) он становится отрицательным. Значит, исходный подсчёт заменяется суммой примерно из \(K/N\) членов вместо недостижимого прямого перебора конфигураций.
Для реальных параметров
$$J=\left\lfloor\frac{10^{15}}{10^9}\right\rfloor=10^6,$$
то есть внешний цикл велик, но всё ещё хорошо контролируется, если каждый член считать быстро.
Ряд \(\lambda_+(x)\) не раскладывается явно. Вместо этого используется формула обращения Лагранжа, которая при \(k\ge 1\) даёт
$$c(m,k)=[x^k]\lambda_+(x)^m=\frac{m}{k}\binom{m-k-1}{k-1}.$$
Это и есть главное упрощение: коэффициент алгебраического ряда заменяется одним биномиальным коэффициентом и множителем \(m/k\). Отдельно задаётся граничный случай:
$$c(m,0)=\begin{cases} 1,&m=0,\\ 0,&m\ne 0. \end{cases}$$
Именно это правило нужно, чтобы самые маленькие проверочные примеры сходились правильно.
Теперь требуется находить \(\binom{n}{r}\pmod{p^2}\) при очень больших \(n\) и \(r\). По формуле Лежандра
$$v_p(n!)=\sum_{t\ge 1}\left\lfloor\frac{n}{p^t}\right\rfloor,$$
а значит
$$e=v_p\!\left(\binom{n}{r}\right)=v_p(n!)-v_p(r!)-v_p((n-r)!).$$
Если \(e\ge 2\), то биномиальный коэффициент делится на \(p^2\), и по модулю \(p^2\) он сразу равен нулю. Иначе представим факториал в виде
$$n!=p^{v_p(n!)}\,n!_{(p)},$$
где \(n!_{(p)}\) — часть факториала после удаления всех множителей \(p\). Тогда получаем
$$\binom{n}{r}\equiv p^e\cdot\frac{n!_{(p)}}{r!_{(p)}(n-r)!_{(p)}}\pmod{p^2}.$$
То есть задача сводится к быстрому вычислению именно этих p-свободных частей факториалов.
Пусть
$$n=qp+r,\qquad 0\le r<p.$$
Разбиение диапазона \(1,2,\dots,n\) на полные блоки длины \(p\) и последний неполный блок даёт сравнение
$$n!_{(p)}\equiv q!_{(p)}\cdot\bigl((p-1)!\bigr)^q\cdot r!\cdot\bigl(1+qp\,H_r\bigr)\pmod{p^2},$$
где
$$H_r=\sum_{i=1}^{r} i^{-1}\pmod{p^2}.$$
Гармоническая поправка появляется из
$$\prod_{i=1}^{r}(qp+i)=r!\prod_{i=1}^{r}\left(1+\frac{qp}{i}\right)\equiv r!\left(1+qp\sum_{i=1}^{r}\frac{1}{i}\right)\pmod{p^2}.$$
Каждый рекурсивный шаг делит аргумент на \(p\), поэтому глубина равна всего лишь \(O(\log_p n)\).
Для знакопеременной суммы нужны все значения \(\binom{N}{j}\) при \(0\le j\le J\). Их не пересчитывают независимо, а используют рекуррентное соотношение
$$\binom{N}{j+1}=\binom{N}{j}\cdot\frac{N-j}{j+1}\pmod{p^2}.$$
Для реального входа \(J=10^6<p\), поэтому каждый знаменатель \(j+1\) обратим по модулю \(p^2\). Это превращает построение всей строки в линейную предобработку.
Для каждого \(j\) задаются величины
$$m_j=N(N-2j),\qquad k_j=K-Nj.$$
Затем вычисляется \(c(m_j,k_j)\) по формуле из шага 2, нужный биномиальный коэффициент находится по шагам 3 и 4, результат умножается на \(\binom{N}{j}\), применяется знак \((-1)^{Nj}\), и всё суммируется по модулю \(p^2\).
Поскольку
$$(-1)^{Nj}=\begin{cases} 1,&N\text{ чётно},\\ (-1)^j,&N\text{ нечётно}, \end{cases}$$
обработка знака оказывается очень дешёвой.
Это самый маленький контрольный пример из реализаций. Здесь
$$J=\left\lfloor\frac{2}{2}\right\rfloor=1,$$
поэтому сумма состоит из двух членов.
Для \(j=0\)
$$m_0=2(2-0)=4,\qquad k_0=2,\qquad \binom{2}{0}=1,$$
и потому
$$c(4,2)=\frac{4}{2}\binom{1}{1}=2.$$
Первый вклад равен \(1\cdot 2=2\).
Для \(j=1\)
$$m_1=2(2-2)=0,\qquad k_1=0,\qquad \binom{2}{1}=2.$$
Граничное правило даёт \(c(0,0)=1\), значит второй вклад равен \(2\cdot 1=2\). Поскольку \(N\) чётно, знак не меняется. Следовательно,
$$L(2,2)=2+2=4,$$
что совпадает с проверочным значением.
Реализации на C++, Python и Java используют один и тот же математический конвейер. Сначала они предварительно вычисляют факториальные остатки до \(p-1\), модульные обратные для малых ненулевых остатков и накопленные гармонические суммы \(H_r\). Именно эти таблицы нужны рекурсии для p-свободной части факториала.
Затем строится вся строка \(\binom{N}{0},\binom{N}{1},\dots,\binom{N}{J}\) с помощью одношаговой рекурсии из шага 5. После этого программы перебирают \(j=0,\dots,J\), вычисляют коэффициент \(c(m_j,k_j)\), находят соответствующий биномиальный коэффициент по модулю \(p^2\), умножают на \(\binom{N}{j}\), применяют знак и добавляют результат к общей сумме.
Реализация на C++ дополнительно делит диапазон значений \(j\) между доступными аппаратными потоками и затем складывает частичные суммы. Реализации на Python и Java выполняют ту же арифметику последовательно, но математический алгоритм остаётся тем же самым.
Пусть \(J=\lfloor K/N\rfloor\). Предварительное вычисление факториальных остатков, обратных элементов и гармонических сумм до \(p-1\) требует \(O(p)\) времени и \(O(p)\) памяти. Построение строки \(\binom{N}{j}\) требует \(O(J)\) времени и \(O(J)\) памяти. Каждый член суммы после этого требует лишь \(O(\log_p K)\) p-адической рекурсии, так что полное суммирование имеет стоимость \(O(J\log_p K)\), что здесь практически линейно, потому что \(p\approx 10^7\) уже очень велико. Общая память составляет \(O(p+J)\), а версия на C++ дополнительно уменьшает реальное время работы благодаря параллелизации внешнего цикла.
مسألة Chess Sliders تؤدي في النهاية إلى دالة عد اسمها \(L(N,K)\). عند القيم المطلوبة \(N=10^9\) و\(K=10^{15}\)، يصبح العد المباشر غير ممكن عمليًا، لذلك يجب حساب الجواب بترديد \(p^2\) حيث
$$p=10{,}000{,}019.$$
تُظهر التطبيقات أن الطريق العملي هو تحويل العد الأصلي إلى مجموع متناوب منتهٍ، ثم تقييم كل حد فيه عبر استخراج معاملات من سلسلة جبرية، مع حسابات توافقية p-adic لمعاملات ثنائية الحد.
الصيغة الأساسية المستخدمة هي
$$L(N,K)=\sum_{j=0}^{J}(-1)^{Nj}\binom{N}{j}\,c\bigl(N(N-2j),\,K-Nj\bigr)\pmod{p^2},\qquad J=\left\lfloor\frac{K}{N}\right\rfloor.$$
هنا \(c(m,k)\) هو معامل مأخوذ من السلسلة الجبرية \(\lambda_+(x)\) التي تظهر في الاشتقاق التوافقي للمسألة. وبذلك تصبح المهمة هي جعل هذا التعبير قابلًا للحساب بكفاءة تحت الترديد \(p^2\).
المؤشر الخارجي لا يحتاج أن يتجاوز
$$J=\left\lfloor\frac{K}{N}\right\rfloor,$$
لأن الوسيط الثاني في \(c(m,k)\) هو \(k=K-Nj\)، وعندما يصبح \(j>J\) يصير هذا المقدار سالبًا فلا تبقى مساهمة. بهذه الطريقة يتحول العد الأصلي إلى مجموع فيه تقريبًا \(K/N\) حدود بدل محاولة تعداد التراكيب مباشرة.
بالنسبة إلى المدخل الفعلي، نحصل على
$$J=\left\lfloor\frac{10^{15}}{10^9}\right\rfloor=10^6,$$
وهو عدد كبير لكنه يبقى عمليًا إذا كان تقييم كل حد سريعًا.
التطبيقات لا توسع \(\lambda_+(x)\) حدًا حدًا. بدلًا من ذلك تستخدم عكس لاغرانج، والذي يعطي عندما \(k\ge 1\):
$$c(m,k)=[x^k]\lambda_+(x)^m=\frac{m}{k}\binom{m-k-1}{k-1}.$$
هذه هي النقلة الرياضية الأساسية: معامل في سلسلة جبرية يتحول إلى معامل ثنائي واحد مضروبًا في \(m/k\). أما الحد الثابت فيُعالج على نحو منفصل:
$$c(m,0)=\begin{cases} 1,&m=0,\\ 0,&m\ne 0. \end{cases}$$
وهذه الحالة الحدية ضرورية لكي تتطابق أمثلة التحقق الصغيرة مع القيم الصحيحة.
الآن يجب حساب \(\binom{n}{r}\pmod{p^2}\) رغم أن \(n\) و\(r\) قد يكونان كبيرين جدًا. نعتمد أولًا على صيغة ليجاندر:
$$v_p(n!)=\sum_{t\ge 1}\left\lfloor\frac{n}{p^t}\right\rfloor.$$
ومنها تكون رتبة \(p\) داخل معامل ثنائي الحد
$$e=v_p\!\left(\binom{n}{r}\right)=v_p(n!)-v_p(r!)-v_p((n-r)!).$$
إذا كان \(e\ge 2\)، فإن \(\binom{n}{r}\) قابل للقسمة على \(p^2\)، وبالتالي يساوي صفرًا بترديد \(p^2\). أما إذا كان \(e=0\) أو \(e=1\)، فنكتب
$$n!=p^{v_p(n!)}\,n!_{(p)},$$
حيث \(n!_{(p)}\) هو الجزء المتبقي بعد حذف جميع عوامل \(p\). وبما أن المقام المتبقي يصبح أوليًا مع \(p\)، فهو قابل للعكس تحت الترديد \(p^2\)، ومن ثم
$$\binom{n}{r}\equiv p^e\cdot\frac{n!_{(p)}}{r!_{(p)}(n-r)!_{(p)}}\pmod{p^2}.$$
إذن جوهر المسألة هو حساب هذه الأجزاء الخالية من \(p\) بسرعة.
نكتب
$$n=qp+r,\qquad 0\le r<p.$$
وبتقسيم الفترة \(1,2,\dots,n\) إلى كتل كاملة طولها \(p\) وكتلة أخيرة جزئية، نحصل على التطابق
$$n!_{(p)}\equiv q!_{(p)}\cdot\bigl((p-1)!\bigr)^q\cdot r!\cdot\bigl(1+qp\,H_r\bigr)\pmod{p^2},$$
حيث
$$H_r=\sum_{i=1}^{r} i^{-1}\pmod{p^2}.$$
ويأتي التصحيح التوافقي من العلاقة
$$\prod_{i=1}^{r}(qp+i)=r!\prod_{i=1}^{r}\left(1+\frac{qp}{i}\right)\equiv r!\left(1+qp\sum_{i=1}^{r}\frac{1}{i}\right)\pmod{p^2}.$$
كل خطوة عودية تقسم الوسيط على \(p\)، لذلك يكون العمق \(O(\log_p n)\) فقط، وهو صغير جدًا هنا.
المجموع المتناوب يحتاج إلى \(\binom{N}{j}\) لكل \(0\le j\le J\). بدل إعادة حسابها من الصفر، تُستخدم العلاقة
$$\binom{N}{j+1}=\binom{N}{j}\cdot\frac{N-j}{j+1}\pmod{p^2}.$$
في المدخل الفعلي لدينا \(J=10^6<p\)، لذا فإن كل مقام \(j+1\) قابل للعكس بترديد \(p^2\). وهذا يجعل هذه المرحلة تهيئة خطية الزمن.
لكل قيمة \(j\) نعرّف
$$m_j=N(N-2j),\qquad k_j=K-Nj.$$
بعد ذلك نحسب \(c(m_j,k_j)\) من الخطوة 2، ثم نحسب معامل ثنائي الحد اللازم بترديد \(p^2\) باستخدام الخطوتين 3 و4، ونضربه في \(\binom{N}{j}\)، ونطبّق الإشارة \((-1)^{Nj}\)، ثم نجمع كل شيء تحت الترديد \(p^2\).
وبما أن
$$(-1)^{Nj}=\begin{cases} 1,&2\mid N,\\ (-1)^j,&2\nmid N, \end{cases}$$
فإن معالجة الإشارة رخيصة جدًا حسابيًا.
هذا هو أصغر مثال تحقق تستخدمه التطبيقات. هنا
$$J=\left\lfloor\frac{2}{2}\right\rfloor=1,$$
أي إن لدينا حدين فقط.
عند \(j=0\)،
$$m_0=2(2-0)=4,\qquad k_0=2,\qquad \binom{2}{0}=1,$$
ومن ثم
$$c(4,2)=\frac{4}{2}\binom{1}{1}=2.$$
المساهمة الأولى تساوي \(1\cdot 2=2\).
وعند \(j=1\)،
$$m_1=2(2-2)=0,\qquad k_1=0,\qquad \binom{2}{1}=2.$$
تعطي القاعدة الحدية \(c(0,0)=1\)، ولذلك تكون المساهمة الثانية \(2\cdot 1=2\). وبما أن \(N\) زوجي فلا يحدث تبديل في الإشارة، وبالتالي
$$L(2,2)=2+2=4,$$
وهي قيمة التحقق نفسها.
تتبع تطبيقات C++ وPython وJava المسار الرياضي نفسه. تبدأ أولًا بتهيئة ثلاثة جداول بترديد \(p^2\): بواقي المضاريب حتى \(p-1\)، والمقلوبات الضربية للبواقي الصغيرة غير الصفرية، والمجاميع التوافقية التراكمية \(H_r\). هذه الجداول هي ما تحتاجه العلاقة العودية الخاصة بالجزء الخالي من \(p\).
بعد ذلك تُبنى القيم \(\binom{N}{0},\binom{N}{1},\dots,\binom{N}{J}\) كلها باستخدام العلاقة التكرارية من الخطوة 5. ثم يجري المرور على \(j=0,\dots,J\)، فيُحسب المعامل \(c(m_j,k_j)\)، ويُقيَّم معامل ثنائي الحد المطلوب بترديد \(p^2\)، ثم يُضرب الناتج في \(\binom{N}{j}\)، وتُطبَّق الإشارة، ويُراكَم الناتج داخل المجموع النهائي.
تضيف نسخة C++ تقسيم مجال \(j\) على عدة خيوط عتادية ثم تجمع المجاميع الجزئية في النهاية. أما نسختا Python وJava فتقومان بالحساب نفسه بشكل تسلسلي، لكن الرياضيات المستعملة لا تتغير.
ليكن \(J=\lfloor K/N\rfloor\). تهيئة بواقي المضاريب والمقلوبات والمجاميع التوافقية حتى \(p-1\) تكلف \(O(p)\) زمنًا و\(O(p)\) ذاكرة. بناء السطر \(\binom{N}{j}\) يكلف \(O(J)\) زمنًا و\(O(J)\) ذاكرة. بعد ذلك يحتاج كل حد فقط إلى \(O(\log_p K)\) من العمل العودي p-adic، لذا تصبح الكلفة الكلية \(O(J\log_p K)\)، وهي هنا شبه خطية لأن \(p\approx 10^7\) كبير أصلًا. الاستهلاك الكلي للذاكرة هو \(O(p+J)\)، ونسخة C++ تقلل الزمن الفعلي أكثر عبر موازاة المجموع الخارجي.