For each \(n\), the counting formula used by the implementations is
$$C(n)=6\sum_{k=0}^{\pi(n)} \binom{n-1}{k}5^{\,n-1-k},$$
where \(\pi(n)\) is the number of primes not exceeding \(n\). The final target is the cumulative sum
$$S(L)=\sum_{n=1}^{L} C(n)\pmod{10^9+7},\qquad L=50{,}000{,}000.$$
A direct evaluation of every truncated binomial sum would be far too slow, so the solution derives a constant-time transition from \(n\) to \(n+1\).
Define
$$B_n(k)=\binom{n-1}{k}5^{\,n-1-k},\qquad t_n=\pi(n).$$
Then the inner truncated sum is
$$P_n=\sum_{k=0}^{t_n} B_n(k),$$
so the quantity contributed at level \(n\) is simply
$$C(n)=6P_n.$$
The whole problem is therefore reduced to updating \(P_n\) efficiently as \(n\) increases.
Using
$$\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1},$$
we obtain
$$B_{n+1}(k)=\binom{n}{k}5^{\,n-k}=5B_n(k)+B_n(k-1).$$
This recurrence is the key structural fact. It says that every term in the next row depends only on two neighboring terms from the current row, so there is no need to rebuild the full truncated sum from scratch.
The cutoff \(t_n=\pi(n)\) changes by at most one when \(n\) increases. Therefore it is enough to keep:
$$P_n=\sum_{k=0}^{t_n} B_n(k),\qquad U_n=B_n(t_n),\qquad V_n=B_n(t_n+1).$$
These are, respectively, the truncated sum, the last included term, and the first excluded term. The initial state is immediate from \(n=1\):
$$t_1=\pi(1)=0,\qquad P_1=1,\qquad U_1=1,\qquad V_1=0.$$
If \(n+1\) is composite, then \(t_{n+1}=t_n=t\). Summing the row transition up to \(k=t\) gives
$$\begin{aligned} P_{n+1} &=\sum_{k=0}^{t}\left(5B_n(k)+B_n(k-1)\right) \\ &=5\sum_{k=0}^{t}B_n(k)+\sum_{k=0}^{t-1}B_n(k) \\ &=6P_n-U_n. \end{aligned}$$
The new boundary terms are
$$U_{n+1}=5U_n+B_n(t-1),\qquad V_{n+1}=5V_n+U_n.$$
The missing term \(B_n(t-1)\) is recovered from a ratio:
$$\frac{B_n(t-1)}{B_n(t)}=\frac{\binom{n-1}{t-1}5^{\,n-t}}{\binom{n-1}{t}5^{\,n-1-t}}=\frac{5t}{n-t},$$
hence
$$B_n(t-1)=U_n\cdot \frac{5t}{n-t}.$$
If \(n+1\) is prime, then the cutoff moves to the right: \(t_{n+1}=t_n+1=t+1\). The next truncated sum now includes one extra boundary term:
$$P_{n+1}=6P_n+5V_n.$$
The new last included term is
$$U_{n+1}=5V_n+U_n,$$
and the new first excluded term satisfies
$$V_{n+1}=5B_n(t+2)+V_n.$$
Again a ratio gives the unseen term:
$$\frac{B_n(t+2)}{B_n(t+1)}=\frac{\binom{n-1}{t+2}5^{\,n-t-3}}{\binom{n-1}{t+1}5^{\,n-t-2}}=\frac{n-t-2}{5(t+2)},$$
so
$$B_n(t+2)=V_n\cdot \frac{n-t-2}{5(t+2)}.$$
If \(t+2>n-1\), that term is simply \(0\), exactly as the implementations handle it.
Every step contributes
$$C(n)=6P_n,$$
therefore
$$S(L)\equiv \sum_{n=1}^{L} 6P_n \pmod{10^9+7}.$$
The recurrence contains divisions by \(n-t\), \(t+2\), and \(5\). Since the modulus \(10^9+7\) is prime and all these numbers are positive and strictly smaller than the modulus for the target range, each division is replaced by multiplication with a modular inverse.
The derived formulas reproduce the exact checkpoint values used by the implementations:
$$C(3)=216,\qquad C(4)=1290,\qquad C(11)=361912500,$$
$$C(24)=4727547363281250000,$$
and for the cumulative sum,
$$S(50)\equiv 832833871 \pmod{10^9+7}.$$
The C++, Python, and Java implementations all follow the same plan. They first build a primality table up to \(L+1\), because only the question “is \(n+1\) prime?” decides which recurrence branch to use. They also precompute modular inverses up to \(L+2\), which turns the rational boundary ratios into constant-time modular multiplications. A single forward pass then maintains the truncated sum together with the two boundary terms, updates them with the prime or composite formulas above, and adds \(6P_n\) to the running answer at each step.
The sieve costs \(O(L\log\log L)\) time. Precomputing modular inverses costs \(O(L)\) time. The recurrence itself performs only constant-time arithmetic per \(n\), so the main loop is \(O(L)\). Overall the method is \(O(L\log\log L)\) time and \(O(L)\) memory, with only \(O(1)\) recurrence state beyond the primality and inverse tables.
Für jedes \(n\) verwenden die Implementierungen die exakte Zählformel
$$C(n)=6\sum_{k=0}^{\pi(n)} \binom{n-1}{k}5^{\,n-1-k},$$
wobei \(\pi(n)\) die Anzahl der Primzahlen \(\le n\) ist. Gesucht ist die kumulative Summe
$$S(L)=\sum_{n=1}^{L} C(n)\pmod{10^9+7},\qquad L=50{,}000{,}000.$$
Eine direkte Auswertung jeder abgeschnittenen Binomialsumme wäre viel zu langsam. Deshalb leitet die Lösung einen Übergang in \(O(1)\) von \(n\) nach \(n+1\) her.
Wir definieren
$$B_n(k)=\binom{n-1}{k}5^{\,n-1-k},\qquad t_n=\pi(n).$$
Dann ist die abgeschnittene Summe
$$P_n=\sum_{k=0}^{t_n} B_n(k),$$
und der Beitrag auf Stufe \(n\) lautet einfach
$$C(n)=6P_n.$$
Damit reduziert sich das Problem darauf, \(P_n\) effizient fortzuschreiben.
Aus
$$\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$$
folgt sofort
$$B_{n+1}(k)=\binom{n}{k}5^{\,n-k}=5B_n(k)+B_n(k-1).$$
Das ist die zentrale Rekursion. Jede Größe der nächsten Zeile hängt nur von zwei benachbarten Größen der aktuellen Zeile ab.
Der Grenzwert \(t_n=\pi(n)\) ändert sich beim Übergang von \(n\) zu \(n+1\) um höchstens eins. Deshalb genügt es, drei Größen zu speichern:
$$P_n=\sum_{k=0}^{t_n} B_n(k),\qquad U_n=B_n(t_n),\qquad V_n=B_n(t_n+1).$$
Das sind die abgeschnittene Summe, der letzte einbezogene Term und der erste ausgeschlossene Term. Für \(n=1\) erhält man direkt
$$t_1=\pi(1)=0,\qquad P_1=1,\qquad U_1=1,\qquad V_1=0.$$
Ist \(n+1\) nicht prim, dann bleibt \(t_{n+1}=t_n=t\). Summation des Zeilenübergangs bis \(k=t\) ergibt
$$\begin{aligned} P_{n+1} &=\sum_{k=0}^{t}\left(5B_n(k)+B_n(k-1)\right) \\ &=5\sum_{k=0}^{t}B_n(k)+\sum_{k=0}^{t-1}B_n(k) \\ &=6P_n-U_n. \end{aligned}$$
Für die neuen Randterme gilt
$$U_{n+1}=5U_n+B_n(t-1),\qquad V_{n+1}=5V_n+U_n.$$
Der fehlende Term wird über ein Verhältnis gewonnen:
$$\frac{B_n(t-1)}{B_n(t)}=\frac{\binom{n-1}{t-1}5^{\,n-t}}{\binom{n-1}{t}5^{\,n-1-t}}=\frac{5t}{n-t},$$
also
$$B_n(t-1)=U_n\cdot \frac{5t}{n-t}.$$
Ist \(n+1\) prim, dann verschiebt sich die Grenze nach rechts: \(t_{n+1}=t_n+1=t+1\). Dadurch kommt ein zusätzlicher Randterm in die Summe:
$$P_{n+1}=6P_n+5V_n.$$
Der neue letzte einbezogene Term ist
$$U_{n+1}=5V_n+U_n,$$
und für den neuen ersten ausgeschlossenen Term gilt
$$V_{n+1}=5B_n(t+2)+V_n.$$
Wieder hilft ein Quotient:
$$\frac{B_n(t+2)}{B_n(t+1)}=\frac{\binom{n-1}{t+2}5^{\,n-t-3}}{\binom{n-1}{t+1}5^{\,n-t-2}}=\frac{n-t-2}{5(t+2)},$$
daher
$$B_n(t+2)=V_n\cdot \frac{n-t-2}{5(t+2)}.$$
Falls \(t+2>n-1\), ist dieser Term gleich \(0\), genau wie in den Implementierungen.
Jeder Schritt trägt
$$C(n)=6P_n$$
bei, also
$$S(L)\equiv \sum_{n=1}^{L} 6P_n \pmod{10^9+7}.$$
In der Rekursion treten Divisionen durch \(n-t\), \(t+2\) und \(5\) auf. Da der Modul \(10^9+7\) prim ist und alle diese Werte im Zielbereich positiv und kleiner als der Modul sind, lassen sich alle Divisionen durch multiplikative Inverse modulo \(10^9+7\) ersetzen.
Die hergeleiteten Formeln reproduzieren die exakten Kontrollwerte aus den Implementierungen:
$$C(3)=216,\qquad C(4)=1290,\qquad C(11)=361912500,$$
$$C(24)=4727547363281250000,$$
sowie für die kumulative Summe
$$S(50)\equiv 832833871 \pmod{10^9+7}.$$
Die C++-, Python- und Java-Implementierungen folgen demselben Aufbau. Zuerst wird eine Primtabelle bis \(L+1\) erzeugt, denn nur die Frage „ist \(n+1\) prim?“ entscheidet über den benutzten Rekursionszweig. Danach werden modulare Inverse bis \(L+2\) vorab berechnet, sodass die rationalen Randverhältnisse als konstante modulare Multiplikationen ausgeführt werden können. Anschließend läuft genau ein Vorwärtsdurchgang über alle \(n\), hält die abgeschnittene Summe und die beiden Randterme aktuell, aktualisiert sie mit den Prim-/Nichtprim-Formeln und addiert in jedem Schritt \(6P_n\) zum Ergebnis.
Das Primzahlsieb benötigt \(O(L\log\log L)\) Zeit. Die Vorberechnung der modularen Inversen kostet \(O(L)\) Zeit. Die eigentliche Rekursion führt pro \(n\) nur konstant viele modulare Operationen aus und ist daher \(O(L)\). Insgesamt ergibt sich \(O(L\log\log L)\) Zeit und \(O(L)\) Speicher, wobei der rekursive Zustand selbst nur \(O(1)\) Platz belegt.
Her \(n\) için uygulamaların kullandığı tam sayım formülü
$$C(n)=6\sum_{k=0}^{\pi(n)} \binom{n-1}{k}5^{\,n-1-k}$$
şeklindedir; burada \(\pi(n)\), \(n\)'den büyük olmayan asal sayıların adedidir. Amaç, kümülatif toplamı
$$S(L)=\sum_{n=1}^{L} C(n)\pmod{10^9+7},\qquad L=50{,}000{,}000$$
olarak hesaplamaktır. Her bir kesilmiş binom toplamını baştan hesaplamak çok pahalı olacağı için çözüm, \(n\)'den \(n+1\)'e sabit zamanlı bir geçiş çıkarır.
Şöyle tanımlayalım:
$$B_n(k)=\binom{n-1}{k}5^{\,n-1-k},\qquad t_n=\pi(n).$$
Buna göre kesilmiş iç toplam
$$P_n=\sum_{k=0}^{t_n} B_n(k)$$
olur ve \(n\) seviyesindeki katkı doğrudan
$$C(n)=6P_n$$
şeklinde yazılır. Dolayısıyla asıl iş, \(P_n\) değerini hızlı güncellemektir.
$$\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$$
özdeşliğini kullanınca
$$B_{n+1}(k)=\binom{n}{k}5^{\,n-k}=5B_n(k)+B_n(k-1)$$
elde edilir. Bu temel rekürsiyon sayesinde bir sonraki satırın her terimi, mevcut satırdaki iki komşu terimden gelir; tüm satırı yeniden kurmaya gerek kalmaz.
Kesme noktası \(t_n=\pi(n)\), \(n\) bir arttığında en fazla bir artar. Bu yüzden şu üç değeri taşımak yeterlidir:
$$P_n=\sum_{k=0}^{t_n} B_n(k),\qquad U_n=B_n(t_n),\qquad V_n=B_n(t_n+1).$$
Bunlar sırasıyla kesilmiş toplam, dahil edilen son terim ve dışarıda kalan ilk terimdir. Başlangıç durumu \(n=1\) için açıktır:
$$t_1=\pi(1)=0,\qquad P_1=1,\qquad U_1=1,\qquad V_1=0.$$
Eğer \(n+1\) bileşikse \(t_{n+1}=t_n=t\) kalır. Satır geçişini \(k=t\)'ye kadar toplarsak
$$\begin{aligned} P_{n+1} &=\sum_{k=0}^{t}\left(5B_n(k)+B_n(k-1)\right) \\ &=5\sum_{k=0}^{t}B_n(k)+\sum_{k=0}^{t-1}B_n(k) \\ &=6P_n-U_n \end{aligned}$$
bulunur. Yeni sınır terimleri ise
$$U_{n+1}=5U_n+B_n(t-1),\qquad V_{n+1}=5V_n+U_n$$
olur. Buradaki eksik terim bir oranla elde edilir:
$$\frac{B_n(t-1)}{B_n(t)}=\frac{\binom{n-1}{t-1}5^{\,n-t}}{\binom{n-1}{t}5^{\,n-1-t}}=\frac{5t}{n-t},$$
yani
$$B_n(t-1)=U_n\cdot \frac{5t}{n-t}.$$
Eğer \(n+1\) asalsa kesme noktası sağa kayar: \(t_{n+1}=t_n+1=t+1\). Böylece toplam bir ek sınır terimi daha içerir:
$$P_{n+1}=6P_n+5V_n.$$
Yeni son dahil terim
$$U_{n+1}=5V_n+U_n,$$
yeni ilk dışarıda kalan terim ise
$$V_{n+1}=5B_n(t+2)+V_n$$
bağıntısını sağlar. Görülmeyen terim yine oranla bulunur:
$$\frac{B_n(t+2)}{B_n(t+1)}=\frac{\binom{n-1}{t+2}5^{\,n-t-3}}{\binom{n-1}{t+1}5^{\,n-t-2}}=\frac{n-t-2}{5(t+2)},$$
dolayısıyla
$$B_n(t+2)=V_n\cdot \frac{n-t-2}{5(t+2)}.$$
Eğer \(t+2>n-1\) ise bu terim doğal olarak \(0\) olur; uygulamalar da tam olarak bu durumu ele alır.
Her adımın katkısı
$$C(n)=6P_n$$
olduğundan
$$S(L)\equiv \sum_{n=1}^{L} 6P_n \pmod{10^9+7}$$
yazılır. Rekürsiyonda \(n-t\), \(t+2\) ve \(5\) ile bölmeler vardır. Modül \(10^9+7\) asal olduğundan ve hedef aralıkta bu paydaların hepsi modülden küçük pozitif sayılar olduğundan, tüm bölmeler modüler ters ile çarpmaya dönüştürülür.
Türetilen formüller uygulamalarda kullanılan kesin kontrol değerlerini verir:
$$C(3)=216,\qquad C(4)=1290,\qquad C(11)=361912500,$$
$$C(24)=4727547363281250000,$$
ve kümülatif toplam için
$$S(50)\equiv 832833871 \pmod{10^9+7}.$$
C++, Python ve Java uygulamaları aynı planı uygular. Önce \(L+1\)'e kadar bir asallık tablosu oluşturulur; çünkü hangi güncellemenin kullanılacağını belirleyen tek bilgi \(n+1\)'in asal olup olmadığıdır. Sonra \(L+2\)'ye kadar modüler tersler önceden hesaplanır; böylece sınır oranlarındaki kesirler sabit zamanlı modüler çarpımlara dönüşür. Son aşamada tek bir ileri döngü, kesilmiş toplam ile iki sınır terimini güncel tutar, asal ve bileşik durumlara göre bu değerleri yeniler ve her \(n\) için \(6P_n\) katkısını cevaba ekler.
Asal eleği \(O(L\log\log L)\) zaman gerektirir. Modüler terslerin ön hesabı \(O(L)\) zamandır. Rekürsiyonun kendisi her \(n\) için sabit sayıda işlem yaptığı için \(O(L)\) sürer. Toplam karmaşıklık \(O(L\log\log L)\) zaman ve \(O(L)\) bellek olup, asıl durum değişkenleri yalnızca \(O(1)\) yer kaplar.
Para cada \(n\), las implementaciones usan la fórmula exacta
$$C(n)=6\sum_{k=0}^{\pi(n)} \binom{n-1}{k}5^{\,n-1-k},$$
donde \(\pi(n)\) es el número de primos menores o iguales que \(n\). El objetivo final es la suma acumulada
$$S(L)=\sum_{n=1}^{L} C(n)\pmod{10^9+7},\qquad L=50{,}000{,}000.$$
Evaluar desde cero cada suma binomial truncada sería demasiado costoso, así que la solución construye una transición de tiempo constante entre \(n\) y \(n+1\).
Definimos
$$B_n(k)=\binom{n-1}{k}5^{\,n-1-k},\qquad t_n=\pi(n).$$
Entonces la suma truncada interior es
$$P_n=\sum_{k=0}^{t_n} B_n(k),$$
y la contribución en el nivel \(n\) queda
$$C(n)=6P_n.$$
Por tanto, el problema se reduce a actualizar \(P_n\) de forma eficiente.
A partir de
$$\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1},$$
se obtiene
$$B_{n+1}(k)=\binom{n}{k}5^{\,n-k}=5B_n(k)+B_n(k-1).$$
Ésta es la observación central: cada término de la fila siguiente depende solo de dos términos vecinos de la fila actual.
El corte \(t_n=\pi(n)\) cambia como mucho en una unidad cuando \(n\) aumenta. Por eso basta con guardar
$$P_n=\sum_{k=0}^{t_n} B_n(k),\qquad U_n=B_n(t_n),\qquad V_n=B_n(t_n+1).$$
Estas cantidades son, respectivamente, la suma truncada, el último término incluido y el primer término excluido. El estado inicial en \(n=1\) es
$$t_1=\pi(1)=0,\qquad P_1=1,\qquad U_1=1,\qquad V_1=0.$$
Si \(n+1\) es compuesto, entonces \(t_{n+1}=t_n=t\). Sumando la transición hasta \(k=t\) se obtiene
$$\begin{aligned} P_{n+1} &=\sum_{k=0}^{t}\left(5B_n(k)+B_n(k-1)\right) \\ &=5\sum_{k=0}^{t}B_n(k)+\sum_{k=0}^{t-1}B_n(k) \\ &=6P_n-U_n. \end{aligned}$$
Los nuevos términos de frontera satisfacen
$$U_{n+1}=5U_n+B_n(t-1),\qquad V_{n+1}=5V_n+U_n.$$
El término faltante se recupera mediante un cociente:
$$\frac{B_n(t-1)}{B_n(t)}=\frac{\binom{n-1}{t-1}5^{\,n-t}}{\binom{n-1}{t}5^{\,n-1-t}}=\frac{5t}{n-t},$$
de modo que
$$B_n(t-1)=U_n\cdot \frac{5t}{n-t}.$$
Si \(n+1\) es primo, la frontera se desplaza a la derecha: \(t_{n+1}=t_n+1=t+1\). Entonces la suma truncada incluye un término adicional:
$$P_{n+1}=6P_n+5V_n.$$
El nuevo último término incluido es
$$U_{n+1}=5V_n+U_n,$$
y el nuevo primer término excluido cumple
$$V_{n+1}=5B_n(t+2)+V_n.$$
Otra razón cerrada da el término invisible:
$$\frac{B_n(t+2)}{B_n(t+1)}=\frac{\binom{n-1}{t+2}5^{\,n-t-3}}{\binom{n-1}{t+1}5^{\,n-t-2}}=\frac{n-t-2}{5(t+2)},$$
por lo tanto
$$B_n(t+2)=V_n\cdot \frac{n-t-2}{5(t+2)}.$$
Si \(t+2>n-1\), ese término vale \(0\), exactamente como hace la implementación.
Cada paso aporta
$$C(n)=6P_n,$$
así que
$$S(L)\equiv \sum_{n=1}^{L} 6P_n \pmod{10^9+7}.$$
La recurrencia contiene divisiones por \(n-t\), \(t+2\) y \(5\). Como el módulo \(10^9+7\) es primo y todos esos valores son positivos y menores que el módulo en el rango objetivo, cada división se reemplaza por una multiplicación con el inverso modular correspondiente.
Las fórmulas anteriores reproducen los valores exactos de control usados por las implementaciones:
$$C(3)=216,\qquad C(4)=1290,\qquad C(11)=361912500,$$
$$C(24)=4727547363281250000,$$
y para la suma acumulada
$$S(50)\equiv 832833871 \pmod{10^9+7}.$$
Las implementaciones en C++, Python y Java siguen la misma estructura. Primero construyen una tabla de primalidad hasta \(L+1\), porque la única decisión lógica es si \(n+1\) es primo o compuesto. Después precalculan inversos modulares hasta \(L+2\), convirtiendo los cocientes de frontera en multiplicaciones modulares de tiempo constante. Por último, una sola pasada hacia adelante mantiene la suma truncada y los dos términos de frontera, los actualiza con las fórmulas del caso primo o compuesto y añade \(6P_n\) a la respuesta en cada iteración.
La criba cuesta \(O(L\log\log L)\) tiempo. El precálculo de inversos modulares cuesta \(O(L)\). La recurrencia realiza solo un número constante de operaciones por cada \(n\), así que el bucle principal es \(O(L)\). En conjunto, el método usa \(O(L\log\log L)\) tiempo y \(O(L)\) memoria, mientras que el estado de la recurrencia ocupa solo \(O(1)\).
对每个 \(n\)，实现中使用的精确计数公式是
$$C(n)=6\sum_{k=0}^{\pi(n)} \binom{n-1}{k}5^{\,n-1-k},$$
其中 \(\pi(n)\) 表示不超过 \(n\) 的素数个数。最终要求的是累计和
$$S(L)=\sum_{n=1}^{L} C(n)\pmod{10^9+7},\qquad L=50{,}000{,}000.$$
如果对每个 \(n\) 都从头计算一次截断二项式和，代价会非常高，因此解法要推导出从 \(n\) 到 \(n+1\) 的常数时间转移。
记
$$B_n(k)=\binom{n-1}{k}5^{\,n-1-k},\qquad t_n=\pi(n).$$
于是截断内和为
$$P_n=\sum_{k=0}^{t_n} B_n(k),$$
而第 \(n\) 层的贡献就是
$$C(n)=6P_n.$$
因此问题变成怎样高效地更新 \(P_n\)。
由
$$\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$$
可得
$$B_{n+1}(k)=\binom{n}{k}5^{\,n-k}=5B_n(k)+B_n(k-1).$$
这是整个方法的核心。下一行的每一项只依赖当前行的两个相邻项，因此没有必要保留整行数据。
阈值 \(t_n=\pi(n)\) 在 \(n\) 增加时最多只会增加 \(1\)。所以只需维护三项信息：
$$P_n=\sum_{k=0}^{t_n} B_n(k),\qquad U_n=B_n(t_n),\qquad V_n=B_n(t_n+1).$$
它们分别表示截断和、最后一个被包含的项，以及第一个被排除的项。初始状态来自 \(n=1\)：
$$t_1=\pi(1)=0,\qquad P_1=1,\qquad U_1=1,\qquad V_1=0.$$
若 \(n+1\) 是合数，则 \(t_{n+1}=t_n=t\)。把转移式从 \(k=0\) 加到 \(k=t\)，得到
$$\begin{aligned} P_{n+1} &=\sum_{k=0}^{t}\left(5B_n(k)+B_n(k-1)\right) \\ &=5\sum_{k=0}^{t}B_n(k)+\sum_{k=0}^{t-1}B_n(k) \\ &=6P_n-U_n. \end{aligned}$$
新的边界项满足
$$U_{n+1}=5U_n+B_n(t-1),\qquad V_{n+1}=5V_n+U_n.$$
缺失的 \(B_n(t-1)\) 可以通过比值恢复：
$$\frac{B_n(t-1)}{B_n(t)}=\frac{\binom{n-1}{t-1}5^{\,n-t}}{\binom{n-1}{t}5^{\,n-1-t}}=\frac{5t}{n-t},$$
因此
$$B_n(t-1)=U_n\cdot \frac{5t}{n-t}.$$
若 \(n+1\) 是素数，则阈值右移一格：\(t_{n+1}=t_n+1=t+1\)。这时截断和会多包含一个边界项：
$$P_{n+1}=6P_n+5V_n.$$
新的最后包含项为
$$U_{n+1}=5V_n+U_n,$$
新的第一个排除项满足
$$V_{n+1}=5B_n(t+2)+V_n.$$
同样用比值求出看不见的那一项：
$$\frac{B_n(t+2)}{B_n(t+1)}=\frac{\binom{n-1}{t+2}5^{\,n-t-3}}{\binom{n-1}{t+1}5^{\,n-t-2}}=\frac{n-t-2}{5(t+2)},$$
从而
$$B_n(t+2)=V_n\cdot \frac{n-t-2}{5(t+2)}.$$
如果 \(t+2>n-1\)，那么该项自然为 \(0\)，实现中的处理也是如此。
每一步贡献
$$C(n)=6P_n,$$
于是
$$S(L)\equiv \sum_{n=1}^{L} 6P_n \pmod{10^9+7}.$$
递推中出现了对 \(n-t\)、\(t+2\) 和 \(5\) 的除法。由于模数 \(10^9+7\) 是素数，而这些分母在目标范围内都为正且严格小于模数，所以都可以改写为乘以相应的模逆元。
上述推导能够重现实现里使用的精确检查值：
$$C(3)=216,\qquad C(4)=1290,\qquad C(11)=361912500,$$
$$C(24)=4727547363281250000,$$
并且累计和满足
$$S(50)\equiv 832833871 \pmod{10^9+7}.$$
C++、Python 和 Java 实现采用完全相同的结构。首先建立到 \(L+1\) 为止的素性表，因为递推只需要知道 \(n+1\) 是否为素数。接着预计算到 \(L+2\) 的模逆元，把边界比值中的分式全部变成常数时间的模乘。随后只需一次线性前向扫描，就能持续维护截断和以及两个边界项，按“下一个数是素数还是合数”选择对应公式更新，并在每个 \(n\) 把 \(6P_n\) 加入答案。
素数筛需要 \(O(L\log\log L)\) 时间。模逆元预处理需要 \(O(L)\) 时间。递推主循环对每个 \(n\) 只做常数次模运算，因此是 \(O(L)\)。总时间复杂度为 \(O(L\log\log L)\)，总空间复杂度为 \(O(L)\)，其中递推状态本身只占 \(O(1)\) 空间。
Для каждого \(n\) реализации используют точную формулу
$$C(n)=6\sum_{k=0}^{\pi(n)} \binom{n-1}{k}5^{\,n-1-k},$$
где \(\pi(n)\) обозначает число простых, не превосходящих \(n\). Нужно вычислить накопленную сумму
$$S(L)=\sum_{n=1}^{L} C(n)\pmod{10^9+7},\qquad L=50{,}000{,}000.$$
Если пересчитывать каждую усечённую биномиальную сумму отдельно, решение будет слишком медленным, поэтому используется переход за \(O(1)\) от \(n\) к \(n+1\).
Обозначим
$$B_n(k)=\binom{n-1}{k}5^{\,n-1-k},\qquad t_n=\pi(n).$$
Тогда усечённая внутренняя сумма равна
$$P_n=\sum_{k=0}^{t_n} B_n(k),$$
и вклад уровня \(n\) записывается как
$$C(n)=6P_n.$$
Следовательно, задача сводится к быстрому обновлению \(P_n\).
Из равенства
$$\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$$
следует
$$B_{n+1}(k)=\binom{n}{k}5^{\,n-k}=5B_n(k)+B_n(k-1).$$
Это основной структурный факт: каждый элемент следующей строки зависит только от двух соседних элементов текущей строки.
Порог \(t_n=\pi(n)\) при увеличении \(n\) меняется не более чем на единицу. Поэтому достаточно поддерживать
$$P_n=\sum_{k=0}^{t_n} B_n(k),\qquad U_n=B_n(t_n),\qquad V_n=B_n(t_n+1).$$
Это, соответственно, усечённая сумма, последний включённый член и первый исключённый член. Начальное состояние для \(n=1\) таково:
$$t_1=\pi(1)=0,\qquad P_1=1,\qquad U_1=1,\qquad V_1=0.$$
Если \(n+1\) составное, то \(t_{n+1}=t_n=t\). Суммируя переход по \(k\) до \(t\), получаем
$$\begin{aligned} P_{n+1} &=\sum_{k=0}^{t}\left(5B_n(k)+B_n(k-1)\right) \\ &=5\sum_{k=0}^{t}B_n(k)+\sum_{k=0}^{t-1}B_n(k) \\ &=6P_n-U_n. \end{aligned}$$
Новые граничные члены равны
$$U_{n+1}=5U_n+B_n(t-1),\qquad V_{n+1}=5V_n+U_n.$$
Недостающий член восстанавливается по отношению:
$$\frac{B_n(t-1)}{B_n(t)}=\frac{\binom{n-1}{t-1}5^{\,n-t}}{\binom{n-1}{t}5^{\,n-1-t}}=\frac{5t}{n-t},$$
то есть
$$B_n(t-1)=U_n\cdot \frac{5t}{n-t}.$$
Если \(n+1\) простое, то порог сдвигается вправо: \(t_{n+1}=t_n+1=t+1\). Тогда в усечённую сумму входит ещё один граничный член:
$$P_{n+1}=6P_n+5V_n.$$
Новый последний включённый член равен
$$U_{n+1}=5V_n+U_n,$$
а новый первый исключённый член удовлетворяет
$$V_{n+1}=5B_n(t+2)+V_n.$$
Ещё одно отношение даёт скрытый член:
$$\frac{B_n(t+2)}{B_n(t+1)}=\frac{\binom{n-1}{t+2}5^{\,n-t-3}}{\binom{n-1}{t+1}5^{\,n-t-2}}=\frac{n-t-2}{5(t+2)},$$
следовательно,
$$B_n(t+2)=V_n\cdot \frac{n-t-2}{5(t+2)}.$$
Если \(t+2>n-1\), этот член равен \(0\); именно так поступают реализации.
Каждый шаг даёт вклад
$$C(n)=6P_n,$$
поэтому
$$S(L)\equiv \sum_{n=1}^{L} 6P_n \pmod{10^9+7}.$$
В рекуррентных формулах есть деление на \(n-t\), \(t+2\) и \(5\). Поскольку модуль \(10^9+7\) прост, а все эти знаменатели в целевом диапазоне положительны и меньше модуля, деление заменяется умножением на соответствующие модульные обратные.
Выведенные формулы воспроизводят точные контрольные значения из реализаций:
$$C(3)=216,\qquad C(4)=1290,\qquad C(11)=361912500,$$
$$C(24)=4727547363281250000,$$
а также
$$S(50)\equiv 832833871 \pmod{10^9+7}.$$
Реализации на C++, Python и Java устроены одинаково. Сначала строится таблица простоты до \(L+1\), потому что единственный выбор в рекурсии зависит от того, является ли число \(n+1\) простым. Затем заранее вычисляются модульные обратные до \(L+2\), чтобы все дробные граничные коэффициенты превратились в постоянное число модульных умножений. После этого один линейный проход поддерживает усечённую сумму и два граничных члена, обновляет их по формуле для простого или составного случая и на каждом шаге прибавляет \(6P_n\) к ответу.
Решето требует \(O(L\log\log L)\) времени. Предвычисление модульных обратных занимает \(O(L)\) времени. Основной цикл рекурсии делает лишь константное число операций для каждого \(n\), то есть работает за \(O(L)\). Итого получаем \(O(L\log\log L)\) по времени и \(O(L)\) по памяти; само рекуррентное состояние использует только \(O(1)\) памяти.
لكل \(n\)، تستخدم التطبيقات الصيغة الدقيقة
$$C(n)=6\sum_{k=0}^{\pi(n)} \binom{n-1}{k}5^{\,n-1-k},$$
حيث تمثل \(\pi(n)\) عدد الأعداد الأولية التي لا تتجاوز \(n\). والمطلوب في النهاية هو حساب المجموع التراكمي
$$S(L)=\sum_{n=1}^{L} C(n)\pmod{10^9+7},\qquad L=50{,}000{,}000.$$
إعادة حساب هذا المجموع المبتور من البداية لكل قيمة \(n\) ستكون بطيئة جداً، لذلك يعتمد الحل على اشتقاق انتقال بزمن ثابت من \(n\) إلى \(n+1\).
نعرّف
$$B_n(k)=\binom{n-1}{k}5^{\,n-1-k},\qquad t_n=\pi(n).$$
وعندئذ يصبح المجموع الداخلي المبتور
$$P_n=\sum_{k=0}^{t_n} B_n(k),$$
فتكون مساهمة المستوى \(n\) هي
$$C(n)=6P_n.$$
إذن جوهر المسألة هو تحديث \(P_n\) بكفاءة عالية.
من الهوية
$$\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$$
نحصل على
$$B_{n+1}(k)=\binom{n}{k}5^{\,n-k}=5B_n(k)+B_n(k-1).$$
وهذه هي الفكرة المركزية: كل حد في الصف التالي يعتمد فقط على حدين متجاورين في الصف الحالي، لذلك لا نحتاج إلى تخزين الصف كاملاً.
العتبة \(t_n=\pi(n)\) لا تتغير عند زيادة \(n\) إلا بمقدار \(1\) كحد أقصى. لذلك يكفي الاحتفاظ بالكميات الثلاث الآتية:
$$P_n=\sum_{k=0}^{t_n} B_n(k),\qquad U_n=B_n(t_n),\qquad V_n=B_n(t_n+1).$$
وهذه تمثل على الترتيب: المجموع المبتور، وآخر حد داخل المجموع، وأول حد خارجه. أما الحالة الابتدائية عند \(n=1\) فهي
$$t_1=\pi(1)=0,\qquad P_1=1,\qquad U_1=1,\qquad V_1=0.$$
إذا كان \(n+1\) مركباً فإن \(t_{n+1}=t_n=t\). بجمع علاقة الانتقال حتى \(k=t\) نحصل على
$$\begin{aligned} P_{n+1} &=\sum_{k=0}^{t}\left(5B_n(k)+B_n(k-1)\right) \\ &=5\sum_{k=0}^{t}B_n(k)+\sum_{k=0}^{t-1}B_n(k) \\ &=6P_n-U_n. \end{aligned}$$
أما حداّ الحافة الجديدان فيحققان
$$U_{n+1}=5U_n+B_n(t-1),\qquad V_{n+1}=5V_n+U_n.$$
والحد المفقود يُستعاد من نسبة مغلقة:
$$\frac{B_n(t-1)}{B_n(t)}=\frac{\binom{n-1}{t-1}5^{\,n-t}}{\binom{n-1}{t}5^{\,n-1-t}}=\frac{5t}{n-t},$$
ومنها
$$B_n(t-1)=U_n\cdot \frac{5t}{n-t}.$$
إذا كان \(n+1\) أولياً فإن العتبة تتحرك إلى اليمين: \(t_{n+1}=t_n+1=t+1\). عندها يدخل حد إضافي في المجموع المبتور:
$$P_{n+1}=6P_n+5V_n.$$
ويصبح آخر حد داخل المجموع
$$U_{n+1}=5V_n+U_n,$$
أما أول حد خارج المجموع فيحقق
$$V_{n+1}=5B_n(t+2)+V_n.$$
وبنسبة أخرى نحصل على الحد غير المرئي:
$$\frac{B_n(t+2)}{B_n(t+1)}=\frac{\binom{n-1}{t+2}5^{\,n-t-3}}{\binom{n-1}{t+1}5^{\,n-t-2}}=\frac{n-t-2}{5(t+2)},$$
لذلك
$$B_n(t+2)=V_n\cdot \frac{n-t-2}{5(t+2)}.$$
وإذا كان \(t+2>n-1\) فإن هذا الحد يساوي \(0\)، وهذا بالضبط ما تعتمده التطبيقات.
كل خطوة تضيف
$$C(n)=6P_n,$$
وبالتالي
$$S(L)\equiv \sum_{n=1}^{L} 6P_n \pmod{10^9+7}.$$
تتضمن العلاقة التكرارية قسمة على \(n-t\) و\(t+2\) و\(5\). وبما أن \(10^9+7\) عدد أولي، وجميع هذه المقامات موجبة وأصغر من المعيار ضمن المجال المطلوب، فيمكن استبدال كل قسمة بضرب في المعكوس المعياري المناسب.
الصيغ السابقة تعيد إنتاج قيم التحقق الدقيقة المستخدمة في التطبيقات:
$$C(3)=216,\qquad C(4)=1290,\qquad C(11)=361912500,$$
$$C(24)=4727547363281250000,$$
وكذلك
$$S(50)\equiv 832833871 \pmod{10^9+7}.$$
تتبع تطبيقات C++ وPython وJava الخطة نفسها. أولاً تُبنى قائمة أولية حتى \(L+1\)، لأن القرار الوحيد في الانتقال هو ما إذا كان \(n+1\) أولياً أم لا. بعد ذلك تُحسب المعكوسات المعيارية حتى \(L+2\) مسبقاً، فيتحول كل كسر في نسب الحافة إلى ضرب معياري بزمن ثابت. ثم يمر التنفيذ مرة واحدة على القيم من \(1\) إلى \(L\)، محافظاً على المجموع المبتور وحدّي الحافة، ومحدّثاً هذه القيم وفق حالة الأولية أو التركيب، ثم يضيف \(6P_n\) إلى الجواب في كل خطوة.
تكلفة الغربلة هي \(O(L\log\log L)\) زمناً. أما حساب المعكوسات المعيارية مسبقاً فيكلف \(O(L)\) زمناً. الحلقة التكرارية نفسها تنفذ عدداً ثابتاً من العمليات لكل \(n\)، لذا فهي \(O(L)\). بالتالي يكون التعقيد الكلي \(O(L\log\log L)\) زمناً و\(O(L)\) ذاكرة، بينما حالة التكرار نفسها لا تحتاج إلا إلى \(O(1)\) إضافية.