Let \(\mathcal{P}\) be the set of all primes below 5000. There are 669 such primes, so a brute-force search would have to reason about \(2^{669}\) different subsets. For each subset \(A \subseteq \mathcal{P}\), form the sum \(\sum_{p \in A} p\). The task is to count how many subsets have a prime-valued sum and report that count modulo \(10^{16}\).
The count is over subsets, not over distinct sums. If two different subsets produce the same prime total, both must be counted. The empty subset contributes the sum 0, which is not prime, so it never enters the final answer, but it is still the correct base case for the recurrence.
The natural state space is the set of all achievable subset sums. Since every input value is itself prime and may be chosen at most once, the problem is a counting version of 0/1 subset sum rather than an unbounded partition problem.
Order the input primes increasingly as
$$p_1 < p_2 < \cdots < p_m,\qquad m=669.$$
If
$$G(x)=\prod_{i=1}^{m}(1+x^{p_i}),$$
then choosing the term \(1\) means “do not use \(p_i\)”, while choosing \(x^{p_i}\) means “use \(p_i\) once”. Therefore
$$G(x)=\sum_{s=0}^{S_{\max}} F(s)x^s,$$
where \(F(s)\) is exactly the number of subsets whose elements sum to \(s\), and
$$S_{\max}=\sum_{p\in\mathcal{P}} p = 1{,}548{,}136.$$
The required answer is then
$$\text{Answer}=\sum_{\substack{q \text{ prime} \\ 0 \le q \le S_{\max}}} F(q)\pmod{10^{16}}.$$
Let \(F_k(s)\) be the number of subsets of \(\{p_1,\dots,p_k\}\) whose sum is \(s\). Then
$$F_0(0)=1,\qquad F_0(s)=0 \text{ for } s>0,$$
and for \(k\ge 1\), each subset counted by \(F_k(s)\) either omits \(p_k\) or includes it exactly once. That gives the recurrence
$$F_k(s)=F_{k-1}(s)+F_{k-1}(s-p_k),$$
where the second term is interpreted as 0 when \(s<p_k\). This is the whole mathematics behind the dynamic program: every valid subset of the first \(k\) primes appears in exactly one of those two disjoint cases.
The implementations do not store the full two-dimensional table. Instead, they keep a single array of coefficients and update it in descending order of \(s\). After the first \(k-1\) primes, suppose the array stores \(F_{k-1}(s)\). When processing \(p_k\), the update
$$F(s+p_k)\leftarrow F(s+p_k)+F(s)\pmod{10^{16}}$$
must read the old value of \(F(s)\), not a value already modified by the same prime. Sweeping \(s\) downward guarantees exactly that, so each prime is used either zero times or one time, never twice in the same stage.
A second invariant is that after the first \(k\) primes, all nonzero entries lie in
$$0 \le s \le \sigma_k,\qquad \sigma_k=p_1+\cdots+p_k.$$
This explains why the code only iterates over the currently reachable frontier instead of scanning the whole array after every prime.
For the smaller set \(\{2,3,5,7\}\), the generating function is
$$G(x)=(1+x^2)(1+x^3)(1+x^5)(1+x^7).$$
Expanding it gives
$$G(x)=1+x^2+x^3+2x^5+2x^7+x^8+x^9+2x^{10}+2x^{12}+x^{14}+x^{15}+x^{17}.$$
The prime exponents are \(2,3,5,7,17\), with coefficients \(1,1,2,2,1\). Therefore the number of subsets with prime sum is
$$1+1+2+2+1=7.$$
This example also shows why we count subsets rather than distinct sums: the coefficient of \(x^5\) is 2 because both \(\{5\}\) and \(\{2,3\}\) produce the prime sum 5.
Once every coefficient \(F(s)\) has been computed modulo \(10^{16}\), the remaining task is only to know which indices \(s\) are prime. That is why the solution performs a second sieve up to \(S_{\max}\): it marks prime sums once, then adds the stored subset counts at exactly those indices.
The C++, Python, and Java implementations first run a sieve up to 5000 to list the input primes. During that same pass they accumulate the total sum \(S_{\max}\), which determines the length of the dynamic-programming array.
The array starts with one nonzero entry: there is exactly one way to make sum 0 before any prime has been processed. Then each prime is folded in by a descending sweep over currently reachable sums. If a sum \(s\) already has \(c\) representations, then \(s+p\) gains another \(c\) representations by appending the new prime \(p\).
Every entry is reduced modulo \(10^{16}\) immediately, so the code never needs the astronomically large exact counts. In the fixed-width implementations this is especially convenient: each update combines two residues below \(10^{16}\), which comfortably fits in 64-bit arithmetic.
After the subset-count array has been completed, the implementation runs another sieve, now on the interval from 0 to \(S_{\max}\). This second sieve is about the possible subset sums, not about the input primes. A final linear pass adds the counts stored at prime indices only.
The small sanity cases are consistent across the implementations: using primes below 10 gives 7, and using primes below 20 gives 65. Those checks confirm that the recurrence and the prime-sum filter are aligned correctly.
If \(m=\pi(5000)=669\) and \(S_{\max}=1{,}548{,}136\), the dynamic program costs \(O(mS_{\max})\) time and \(O(S_{\max})\) memory. The final sieve on subset sums costs \(O(S_{\max}\log\log S_{\max})\), which is smaller than the DP term at this scale.
So the problem is solved with one large but manageable one-dimensional table instead of enumerating \(2^{669}\) subsets. That is the decisive reduction: exponential search over subsets becomes polynomial counting over reachable sums.
Sei \(\mathcal{P}\) die Menge aller Primzahlen unter 5000. Davon gibt es 669, also müsste ein naiver Ansatz \(2^{669}\) verschiedene Teilmengen betrachten. Für jede Teilmenge \(A \subseteq \mathcal{P}\) wird die Summe \(\sum_{p \in A} p\) gebildet. Gesucht ist die Anzahl der Teilmengen, deren Summe selbst prim ist, modulo \(10^{16}\).
Gezählt werden Teilmengen, nicht verschiedene Summen. Wenn zwei unterschiedliche Teilmengen dieselbe primzahlige Summe liefern, tragen beide zum Ergebnis bei. Die leere Menge ergibt die Summe 0; sie zählt daher nicht zur Endantwort, bleibt aber der richtige Startwert der Rekursion.
Der passende Zustandsraum besteht aus allen erreichbaren Teilmengensummen. Da jede Eingabeprimzahl höchstens einmal gewählt werden darf, handelt es sich um eine zählende 0/1-Variante des Teilmengen-Summen-Problems.
Ordne die Eingabeprimzahlen aufsteigend als
$$p_1 < p_2 < \cdots < p_m,\qquad m=669.$$
Definiert man
$$G(x)=\prod_{i=1}^{m}(1+x^{p_i}),$$
dann bedeutet die Wahl von \(1\), dass \(p_i\) nicht verwendet wird, und die Wahl von \(x^{p_i}\), dass \(p_i\) genau einmal verwendet wird. Daher gilt
$$G(x)=\sum_{s=0}^{S_{\max}} F(s)x^s,$$
wobei \(F(s)\) genau die Anzahl der Teilmengen mit Summe \(s\) ist und
$$S_{\max}=\sum_{p\in\mathcal{P}} p = 1{,}548{,}136.$$
Die gesuchte Größe ist also
$$\text{Antwort}=\sum_{\substack{q \text{ prim} \\ 0 \le q \le S_{\max}}} F(q)\pmod{10^{16}}.$$
Sei \(F_k(s)\) die Anzahl der Teilmengen von \(\{p_1,\dots,p_k\}\) mit Summe \(s\). Dann gilt
$$F_0(0)=1,\qquad F_0(s)=0 \text{ für } s>0,$$
und für \(k\ge 1\) kann eine Teilmenge aus \(F_k(s)\) die Primzahl \(p_k\) entweder weglassen oder genau einmal enthalten. Damit erhält man
$$F_k(s)=F_{k-1}(s)+F_{k-1}(s-p_k),$$
wobei der zweite Term als 0 verstanden wird, wenn \(s<p_k\) ist. Genau diese Zerlegung in zwei disjunkte Fälle steckt hinter der gesamten dynamischen Programmierung.
Die Implementierungen speichern keine vollständige zweidimensionale Tabelle, sondern nur ein einziges Koeffizientenfeld. Nach den ersten \(k-1\) Primzahlen enthält es die Werte \(F_{k-1}(s)\). Beim Einfügen von \(p_k\) verwendet man das Update
$$F(s+p_k)\leftarrow F(s+p_k)+F(s)\pmod{10^{16}}.$$
Wichtig ist, dass dabei der alte Wert von \(F(s)\) gelesen wird und nicht ein Wert, der durch dieselbe Primzahl bereits verändert wurde. Genau deshalb läuft die Schleife über \(s\) absteigend: So bleibt die 0/1-Bedeutung erhalten, und keine Primzahl wird in einer Runde zweimal benutzt.
Außerdem gilt als Invariante: Nach den ersten \(k\) Primzahlen liegen alle möglichen Summen im Intervall
$$0 \le s \le \sigma_k,\qquad \sigma_k=p_1+\cdots+p_k.$$
Darum genügt es, in jeder Runde nur bis zur aktuell erreichbaren Grenze zu iterieren.
Für die kleinere Menge \(\{2,3,5,7\}\) lautet die erzeugende Funktion
$$G(x)=(1+x^2)(1+x^3)(1+x^5)(1+x^7).$$
Ausmultipliziert ergibt sich
$$G(x)=1+x^2+x^3+2x^5+2x^7+x^8+x^9+2x^{10}+2x^{12}+x^{14}+x^{15}+x^{17}.$$
Die primen Exponenten sind \(2,3,5,7,17\) mit Koeffizienten \(1,1,2,2,1\). Also ist die Zahl der Teilmengen mit primzahliger Summe
$$1+1+2+2+1=7.$$
Hier sieht man auch den Unterschied zwischen Summen und Teilmengen: Der Koeffizient von \(x^5\) ist 2, weil sowohl \(\{5\}\) als auch \(\{2,3\}\) die Primzahl 5 ergeben.
Sind alle Werte \(F(s)\) modulo \(10^{16}\) berechnet, muss nur noch entschieden werden, welche Indizes \(s\) prim sind. Deshalb verwendet die Lösung ein zweites Sieb bis \(S_{\max}\): Es markiert die primen Summen ein einziges Mal, danach werden genau an diesen Stellen die gespeicherten Teilmengenanzahlen addiert.
Die C++-, Python- und Java-Implementierungen erzeugen zunächst mit einem Sieb alle Primzahlen unter 5000. Gleichzeitig wird die Gesamtsumme \(S_{\max}\) gebildet, weil sie die benötigte Größe des DP-Feldes vorgibt.
Zu Beginn gibt es genau eine nichtverschwindende Möglichkeit: die Summe 0 vor der Verarbeitung irgendeiner Primzahl. Danach wird jede neue Primzahl durch einen absteigenden Durchlauf über die aktuell erreichbaren Summen eingearbeitet. Hat eine Summe \(s\) bereits \(c\) Darstellungen, dann erhält \(s+p\) durch Anhängen der neuen Primzahl \(p\) weitere \(c\) Darstellungen.
Jeder Feldwert wird sofort modulo \(10^{16}\) reduziert. Dadurch müssen die exakten, astronomisch großen Zählwerte nie vollständig gespeichert werden. In den Implementierungen mit fester Wortbreite ist das besonders praktisch, weil jede Aktualisierung nur zwei Residuen unter \(10^{16}\) addiert und daher sicher in 64 Bit bleibt.
Nach Abschluss der Teilmengen-DP wird ein zweites Sieb auf dem Intervall von 0 bis \(S_{\max}\) ausgeführt. Dieses Sieb betrifft also die möglichen Summen, nicht die Eingabeprimzahlen. Ein letzter linearer Durchlauf addiert nur die Koeffizienten an primen Positionen.
Die kleinen Kontrollfälle stimmen in allen Implementierungen überein: Für Primzahlen unter 10 erhält man 7, für Primzahlen unter 20 erhält man 65. Das bestätigt sowohl die Rekursion als auch den Primzahlfilter über den Summenraum.
Mit \(m=\pi(5000)=669\) und \(S_{\max}=1{,}548{,}136\) kostet die dynamische Programmierung \(O(mS_{\max})\) Zeit und \(O(S_{\max})\) Speicher. Das abschließende Sieb über die möglichen Summen benötigt \(O(S_{\max}\log\log S_{\max})\) Zeit und ist für diese Eingabe kleiner als der DP-Anteil.
Entscheidend ist also, dass die exponentielle Suche über \(2^{669}\) Teilmengen in eine polynomielle Zählung über erreichbare Summen umgewandelt wird. Genau diese Reduktion macht das Problem praktisch lösbar.
\(\mathcal{P}\), 5000'den küçük tüm asal sayıların kümesi olsun. Bu kümede 669 asal vardır; dolayısıyla kaba kuvvet yaklaşımı \(2^{669}\) farklı alt kümeyi düşünmek zorunda kalır. Her \(A \subseteq \mathcal{P}\) alt kümesi için \(\sum_{p \in A} p\) toplamı alınır. İstenen şey, toplamı da asal olan alt kümelerin sayısını \(10^{16}\) modunda bulmaktır.
Sayım, farklı toplamlar üzerinden değil, alt kümeler üzerinden yapılır. İki farklı alt küme aynı asal toplamı üretirse ikisi de ayrı ayrı sayılır. Boş kümenin toplamı 0'dır; 0 asal olmadığı için sonuca katkı vermez, ama yine de dinamik programın doğru başlangıç durumu odur.
Doğru durum uzayı, elde edilebilen tüm alt küme toplamlarıdır. Her giriş asalı en fazla bir kez seçilebildiği için problem, sınırsız parçalama problemi değil, sayım yapan bir 0/1 alt küme toplamı problemidir.
Girişteki asalları artan sırayla
$$p_1 < p_2 < \cdots < p_m,\qquad m=669$$
şeklinde dizelim. Eğer
$$G(x)=\prod_{i=1}^{m}(1+x^{p_i})$$
tanımlanırsa, \(1\) terimini seçmek “\(p_i\)'yi alma”, \(x^{p_i}\) terimini seçmek ise “\(p_i\)'yi bir kez al” anlamına gelir. Bu yüzden
$$G(x)=\sum_{s=0}^{S_{\max}} F(s)x^s$$
olur; burada \(F(s)\), toplamı \(s\) olan alt kümelerin sayısıdır ve
$$S_{\max}=\sum_{p\in\mathcal{P}} p = 1{,}548{,}136.$$
Dolayısıyla aranan nicelik
$$\text{Cevap}=\sum_{\substack{q \text{ asal} \\ 0 \le q \le S_{\max}}} F(q)\pmod{10^{16}}$$
şeklindedir.
\(F_k(s)\), \(\{p_1,\dots,p_k\}\) kümesinin toplamı \(s\) olan alt kümelerinin sayısı olsun. O zaman
$$F_0(0)=1,\qquad F_0(s)=0 \text{ } (s>0)$$
ve \(k\ge 1\) için her alt küme ya \(p_k\)'yi hiç kullanmaz ya da tam bir kez kullanır. Bu iki ayrık durum şu bağıntıyı verir:
$$F_k(s)=F_{k-1}(s)+F_{k-1}(s-p_k).$$
Burada \(s<p_k\) ise ikinci terim 0 kabul edilir. Dinamik programın tamamı aslında bu tek gözleme dayanır.
Uygulamalar tam iki boyutlu tablo tutmaz; onun yerine tek bir katsayı dizisi kullanır. İlk \(k-1\) asal işlendiğinde dizide \(F_{k-1}(s)\) değerleri bulunur. \(p_k\) işlenirken yapılan güncelleme
$$F(s+p_k)\leftarrow F(s+p_k)+F(s)\pmod{10^{16}}$$
şeklindedir. Burada kritik nokta, \(F(s)\) değerinin aynı turda \(p_k\) ile daha önce değiştirilmemiş eski değer olmasıdır. Bu yüzden \(s\) büyükten küçüğe dolaşılır; böylece her asal ya 0 kez ya 1 kez kullanılır, aynı aşamada ikinci kez kullanılamaz.
Bir başka değişmez de şudur: ilk \(k\) asaldan sonra sıfır olmayan bütün katsayılar
$$0 \le s \le \sigma_k,\qquad \sigma_k=p_1+\cdots+p_k$$
aralığında kalır. Bu nedenle kod her turda tüm diziyi değil, yalnızca o ana kadar erişilebilen sınırı dolaşır.
\(\{2,3,5,7\}\) kümesi için üreteç fonksiyonu
$$G(x)=(1+x^2)(1+x^3)(1+x^5)(1+x^7)$$
olur. Açılımı
$$G(x)=1+x^2+x^3+2x^5+2x^7+x^8+x^9+2x^{10}+2x^{12}+x^{14}+x^{15}+x^{17}$$
şeklindedir. Asal üsler \(2,3,5,7,17\) ve bunların katsayıları sırasıyla \(1,1,2,2,1\)'dir. Dolayısıyla asal toplam veren alt küme sayısı
$$1+1+2+2+1=7$$
olur. Bu örnek, “toplam” ile “alt küme sayısı” arasındaki farkı da açıkça gösterir: \(x^5\)'in katsayısı 2'dir, çünkü hem \(\{5\}\) hem de \(\{2,3\}\) alt kümesi asal toplam 5'i verir.
Bütün \(F(s)\) değerleri \(10^{16}\) modunda hesaplandıktan sonra geriye yalnızca hangi indislerin asal olduğunu belirlemek kalır. Bu nedenle çözüm \(S_{\max}\)'e kadar ikinci bir asal eleği çalıştırır; sonra sadece asal indislerdeki alt küme sayıları toplanır.
C++, Python ve Java uygulamaları önce 5000'e kadar bir elek çalıştırarak girişte kullanılacak asalları listeler. Aynı geçiş sırasında toplam üst sınır \(S_{\max}\) da hesaplanır; çünkü dinamik program dizisinin uzunluğu buna göre belirlenir.
Dizi başlangıçta yalnızca bir tane sıfır olmayan değer içerir: henüz hiçbir asal işlenmemişken toplam 0'ı elde etmenin tek yolu boş kümedir. Sonra her yeni asal, o ana kadar erişilebilen toplamlar üzerinde tersten dolaşarak içeri katılır. Eğer bir \(s\) toplamının \(c\) farklı gösterimi varsa, yeni asal \(p\) eklenince \(s+p\) toplamı da ek olarak \(c\) yeni gösterim kazanır.
Her güncellemeden sonra değerler hemen \(10^{16}\) moduna indirgenir; böylece gerçek sayıların astronomik boyutlara çıkması hiç sorun olmaz. Sabit genişlikli sürümlerde bu ayrıca güvenlidir, çünkü her adımda toplanan iki artık da \(10^{16}\)'dan küçüktür ve 64 bit aralığında rahatlıkla tutulur.
Alt küme sayım dizisi tamamlandıktan sonra, bu kez 0 ile \(S_{\max}\) arasındaki olası toplamlar üzerinde ikinci bir elek çalıştırılır. Bu ikinci elek giriş asalları için değil, alt küme toplamlarının asal olup olmadığını anlamak içindir. Son doğrusal geçişte yalnızca asal indislerdeki değerler toplanır.
Küçük doğrulama örnekleri de bunu destekler: 10'dan küçük asallar için sonuç 7, 20'den küçük asallar için sonuç 65'tir. Bu sayılar hem bağıntının hem de asal-toplam filtresinin doğru kurulduğunu gösterir.
\(m=\pi(5000)=669\) ve \(S_{\max}=1{,}548{,}136\) olmak üzere dinamik programın zaman maliyeti \(O(mS_{\max})\), bellek maliyeti ise \(O(S_{\max})\)'tir. Son aşamadaki asal eleği \(O(S_{\max}\log\log S_{\max})\) zamanda çalışır ve bu problem boyutunda DP maliyetinden küçüktür.
Asıl kazanım şudur: \(2^{669}\) alt kümeyi tek tek dolaşmak yerine, erişilebilir toplamlar üzerinde tek boyutlu bir sayım yapılır. Üstel arama böylece polinomik bir hesaplamaya dönüşür.
Sea \(\mathcal{P}\) el conjunto de todos los primos menores que 5000. Hay 669 de ellos, así que un enfoque por fuerza bruta tendría que considerar \(2^{669}\) subconjuntos distintos. Para cada subconjunto \(A \subseteq \mathcal{P}\), se forma la suma \(\sum_{p \in A} p\). La tarea consiste en contar cuántos subconjuntos tienen una suma que también es prima, y dar el resultado módulo \(10^{16}\).
Se cuentan subconjuntos, no sumas distintas. Si dos subconjuntos diferentes producen el mismo total primo, ambos cuentan. El subconjunto vacío produce la suma 0; como 0 no es primo, no contribuye al resultado final, pero sí debe permanecer como caso base de la recurrencia.
El espacio de estados correcto es el conjunto de todas las sumas de subconjuntos alcanzables. Como cada primo de entrada puede elegirse a lo sumo una vez, el problema es una versión de conteo del subset sum 0/1.
Ordenemos los primos de entrada como
$$p_1 < p_2 < \cdots < p_m,\qquad m=669.$$
Si definimos
$$G(x)=\prod_{i=1}^{m}(1+x^{p_i}),$$
entonces elegir el término \(1\) significa “no usar \(p_i\)”, mientras que elegir \(x^{p_i}\) significa “usar \(p_i\) exactamente una vez”. Por lo tanto,
$$G(x)=\sum_{s=0}^{S_{\max}} F(s)x^s,$$
donde \(F(s)\) es el número de subconjuntos cuya suma vale \(s\), y
$$S_{\max}=\sum_{p\in\mathcal{P}} p = 1{,}548{,}136.$$
La respuesta buscada es entonces
$$\text{Respuesta}=\sum_{\substack{q \text{ primo} \\ 0 \le q \le S_{\max}}} F(q)\pmod{10^{16}}.$$
Sea \(F_k(s)\) el número de subconjuntos de \(\{p_1,\dots,p_k\}\) cuya suma es \(s\). Se tiene
$$F_0(0)=1,\qquad F_0(s)=0 \text{ para } s>0,$$
y para \(k\ge 1\), cada subconjunto contado por \(F_k(s)\) o bien no usa \(p_k\), o bien lo usa exactamente una vez. De ahí sale la recurrencia
$$F_k(s)=F_{k-1}(s)+F_{k-1}(s-p_k),$$
donde el segundo término se interpreta como 0 si \(s<p_k\). Esa partición en dos casos disjuntos es toda la base matemática del algoritmo.
Las implementaciones no guardan toda la tabla bidimensional. En su lugar mantienen un solo arreglo de coeficientes y lo actualizan en orden descendente de \(s\). Después de procesar los primeros \(k-1\) primos, el arreglo contiene \(F_{k-1}(s)\). Al incorporar \(p_k\), la actualización es
$$F(s+p_k)\leftarrow F(s+p_k)+F(s)\pmod{10^{16}}.$$
Lo importante es que \(F(s)\) debe seguir siendo el valor antiguo, no uno ya modificado por el mismo primo. Recorrer \(s\) de mayor a menor garantiza exactamente eso y preserva la semántica 0/1: cada primo se usa cero o una vez, nunca dos veces en la misma etapa.
Además, después de los primeros \(k\) primos, todas las sumas no nulas viven en
$$0 \le s \le \sigma_k,\qquad \sigma_k=p_1+\cdots+p_k.$$
Esa invariante explica por qué el código solo recorre la frontera actualmente alcanzable.
Para el conjunto \(\{2,3,5,7\}\), la función generadora es
$$G(x)=(1+x^2)(1+x^3)(1+x^5)(1+x^7).$$
Al expandirla se obtiene
$$G(x)=1+x^2+x^3+2x^5+2x^7+x^8+x^9+2x^{10}+2x^{12}+x^{14}+x^{15}+x^{17}.$$
Los exponentes primos son \(2,3,5,7,17\), con coeficientes \(1,1,2,2,1\). Por tanto, el número de subconjuntos con suma prima es
$$1+1+2+2+1=7.$$
Este ejemplo también muestra por qué contamos subconjuntos y no solo sumas distintas: el coeficiente de \(x^5\) es 2 porque tanto \(\{5\}\) como \(\{2,3\}\) producen la suma prima 5.
Una vez calculados todos los valores \(F(s)\) módulo \(10^{16}\), solo falta saber qué índices \(s\) son primos. Por eso la solución ejecuta una segunda criba hasta \(S_{\max}\): marca una vez todas las sumas primas y luego acumula los conteos almacenados únicamente en esos índices.
Las implementaciones en C++, Python y Java comienzan con una criba hasta 5000 para enumerar los primos de entrada. En ese mismo recorrido acumulan también la suma total \(S_{\max}\), que fija el tamaño del arreglo dinámico.
El arreglo empieza con un único valor no nulo: hay exactamente una forma de obtener la suma 0 antes de procesar ningún primo. Después, cada primo nuevo se incorpora con un recorrido descendente sobre las sumas actualmente alcanzables. Si una suma \(s\) ya tiene \(c\) representaciones, entonces \(s+p\) gana otras \(c\) representaciones al añadir el nuevo primo \(p\).
Cada celda se reduce inmediatamente módulo \(10^{16}\), así que nunca hace falta almacenar los conteos exactos gigantescos. En las implementaciones con enteros de ancho fijo esto resulta especialmente cómodo, porque cada actualización suma dos residuos menores que \(10^{16}\), lo cual cabe sin problema en 64 bits.
Una vez terminado el arreglo de conteos, la implementación ejecuta otra criba, ahora sobre el intervalo entre 0 y \(S_{\max}\). Esta segunda criba se refiere a las posibles sumas de subconjuntos, no a los primos de entrada. Un último recorrido lineal suma únicamente las posiciones primas.
Los casos pequeños usados como comprobación son coherentes en las tres versiones: con primos menores que 10 el resultado es 7, y con primos menores que 20 el resultado es 65. Eso confirma que la recurrencia y el filtro de primalidad están coordinados correctamente.
Con \(m=\pi(5000)=669\) y \(S_{\max}=1{,}548{,}136\), el programa dinámico cuesta \(O(mS_{\max})\) en tiempo y \(O(S_{\max})\) en memoria. La criba final sobre las sumas cuesta \(O(S_{\max}\log\log S_{\max})\), menor que el término principal del DP en este tamaño.
La reducción clave es que el problema deja de ser una enumeración exponencial sobre \(2^{669}\) subconjuntos y pasa a ser un conteo polinómico sobre sumas alcanzables. Esa es la razón por la que el enfoque resulta viable.
设 \(\mathcal{P}\) 为所有小于 5000 的素数集合。这样的素数一共有 669 个，因此如果直接暴力枚举，就要面对 \(2^{669}\) 个不同的子集。对每个子集 \(A \subseteq \mathcal{P}\)，取其元素和 \(\sum_{p \in A} p\)。题目要求统计其中“子集元素和也是素数”的子集个数，并将结果对 \(10^{16}\) 取模。
这里统计的是子集的数量，而不是不同素数和的种类数。两个不同的子集如果得到同一个素数和，它们都必须分别计入答案。空集的和是 0，0 不是素数，所以空集不会出现在最终答案里；但它仍然必须作为动态规划最初的基态保留下来。
这个问题最自然的状态空间，就是所有“能够由这些素数组成的子集和”。由于每个输入素数只能选或不选一次，所以它不是无界拆分问题，而是一个带计数意义的 0/1 子集和问题。
把输入素数按从小到大排列为
$$p_1 < p_2 < \cdots < p_m,\qquad m=669.$$
定义
$$G(x)=\prod_{i=1}^{m}(1+x^{p_i}).$$
对于每个因子，选 \(1\) 表示“不取 \(p_i\)”，选 \(x^{p_i}\) 表示“恰好取一次 \(p_i\)”。因此展开后有
$$G(x)=\sum_{s=0}^{S_{\max}} F(s)x^s,$$
其中 \(F(s)\) 恰好表示元素和为 \(s\) 的子集个数，而
$$S_{\max}=\sum_{p\in\mathcal{P}} p = 1{,}548{,}136.$$
于是题目所求可以写成
$$\text{Answer}=\sum_{\substack{q \text{ 是素数} \\ 0 \le q \le S_{\max}}} F(q)\pmod{10^{16}}.$$
也就是说，先把所有子集和的计数都算出来，再把其中下标为素数的位置加起来即可。
记 \(F_k(s)\) 为只使用 \(\{p_1,\dots,p_k\}\) 这 \(k\) 个素数时，和为 \(s\) 的子集个数。那么初始条件是
$$F_0(0)=1,\qquad F_0(s)=0 \text{ 当 } s>0.$$
当 \(k\ge 1\) 时，任意一个和为 \(s\) 的子集只有两种来源：要么不使用 \(p_k\)，要么使用 \(p_k\) 一次。于是得到
$$F_k(s)=F_{k-1}(s)+F_{k-1}(s-p_k),$$
其中如果 \(s<p_k\)，第二项视为 0。这个公式已经把问题的核心数学结构完整表达出来了，因为每个合法子集都唯一地落在这两个互斥情形之一中。
实现时并不需要保存整个二维表 \(F_k(s)\)，只需要保留当前这一层的系数数组即可。假设处理完前 \(k-1\) 个素数后，数组中存的是 \(F_{k-1}(s)\)。接下来处理 \(p_k\) 时，执行更新
$$F(s+p_k)\leftarrow F(s+p_k)+F(s)\pmod{10^{16}}.$$
这里最关键的一点是：右侧的 \(F(s)\) 必须是“加入 \(p_k\) 之前”的旧值，而不能是本轮已经被 \(p_k\) 修改过的新值。正因为如此，循环必须从大到小扫描 \(s\)。只有倒序更新，才能保证每个素数在当前阶段只被使用 0 次或 1 次，而不会在同一轮中被重复使用。
还有一个同样重要的不变量：处理完前 \(k\) 个素数后，所有可能出现的和都落在区间
$$0 \le s \le \sigma_k,\qquad \sigma_k=p_1+\cdots+p_k.$$
因此代码不必每次都扫到全局最大长度，只需要扫到当前可达的前沿边界即可。
先看较小的集合 \(\{2,3,5,7\}\)。此时生成函数为
$$G(x)=(1+x^2)(1+x^3)(1+x^5)(1+x^7).$$
把它展开，得到
$$G(x)=1+x^2+x^3+2x^5+2x^7+x^8+x^9+2x^{10}+2x^{12}+x^{14}+x^{15}+x^{17}.$$
其中指数为素数的位置是 \(2,3,5,7,17\)，对应系数分别是 \(1,1,2,2,1\)。所以满足条件的子集总数为
$$1+1+2+2+1=7.$$
这个例子非常适合说明“统计子集个数”而不是“统计不同和”的区别：\(x^5\) 的系数是 2，因为 \(\{5\}\) 和 \(\{2,3\}\) 这两个不同子集都会产生素数和 5。
当所有 \(F(s)\) 都已经按 \(10^{16}\) 取模算出后，剩下的问题只是在区间 \(0\) 到 \(S_{\max}\) 内判断哪些 \(s\) 是素数。因此解法还会再做一次筛法，不过这次筛的对象不是输入素数，而是“所有可能的子集和”。最后顺序扫描一次，把所有素数下标处的计数加起来即可。
C++、Python 和 Java 实现首先都用筛法生成 5000 以内的素数列表。同时，它们也在这一阶段计算所有这些素数的总和 \(S_{\max}\)，因为这就是后续计数数组所需的长度上界。
计数数组最开始只有一个非零位置：在尚未处理任何素数时，得到和 0 的方法只有一种，也就是选空集。之后每加入一个新的素数，就对当前已经可达的所有和做一次倒序扫描。如果某个和 \(s\) 已经有 \(c\) 种表示方式，那么把新素数 \(p\) 附加上去之后，和 \(s+p\) 就会新增 \(c\) 种表示方式。
数组中的每个值都会立即对 \(10^{16}\) 取模，因此程序始终保存的是模意义下的计数，而不是极其巨大的精确整数。对于使用固定宽度整数的实现，这一点也很方便，因为每次更新只是把两个小于 \(10^{16}\) 的余数相加，完全落在 64 位整数可承受的范围内。
当子集和计数数组全部算完以后，程序会在 0 到 \(S_{\max}\) 上再跑一次筛法。这第二次筛法判断的是“哪些和本身是素数”，而不是重新生成输入素数。最后一次线性扫描只把素数位置上的计数累加进答案。
几个小规模结果可以作为一致性的校验：使用小于 10 的素数时结果是 7，使用小于 20 的素数时结果是 65。它们说明递推关系和最终的素数过滤步骤是彼此吻合的。
记 \(m=\pi(5000)=669\)，\(S_{\max}=1{,}548{,}136\)。那么动态规划部分的时间复杂度是 \(O(mS_{\max})\)，空间复杂度是 \(O(S_{\max})\)。最后对和空间做的筛法时间复杂度为 \(O(S_{\max}\log\log S_{\max})\)，在这个问题规模下它比动态规划主项更小。
真正决定成败的，是把原本需要面对的 \(2^{669}\) 个子集，压缩成了一个长度约 155 万的一维计数问题。也就是说，指数级的枚举被替换成了可管理的多项式时间计算。
Пусть \(\mathcal{P}\) — множество всех простых чисел, меньших 5000. Таких простых 669, поэтому прямой перебор должен был бы рассматривать \(2^{669}\) различных подмножеств. Для каждого подмножества \(A \subseteq \mathcal{P}\) берётся сумма \(\sum_{p \in A} p\). Нужно посчитать, у скольких подмножеств эта сумма тоже является простым числом, и выдать ответ по модулю \(10^{16}\).
Считаются именно подмножества, а не различные значения суммы. Если два разных подмножества дают одну и ту же простую сумму, оба должны быть учтены. Пустое подмножество даёт сумму 0; она не входит в окончательный ответ, но остаётся правильным базовым случаем динамики.
Естественное пространство состояний здесь — все достижимые суммы подмножеств. Поскольку каждое входное простое можно взять не более одного раза, задача является счётной версией 0/1 subset sum.
Упорядочим входные простые по возрастанию:
$$p_1 < p_2 < \cdots < p_m,\qquad m=669.$$
Рассмотрим произведение
$$G(x)=\prod_{i=1}^{m}(1+x^{p_i}).$$
Выбор множителя \(1\) означает, что \(p_i\) не включается в подмножество, а выбор \(x^{p_i}\) означает, что \(p_i\) включается ровно один раз. Поэтому
$$G(x)=\sum_{s=0}^{S_{\max}} F(s)x^s,$$
где \(F(s)\) — число подмножеств с суммой \(s\), а
$$S_{\max}=\sum_{p\in\mathcal{P}} p = 1{,}548{,}136.$$
Тогда искомый результат можно записать так:
$$\text{Ответ}=\sum_{\substack{q \text{ простое} \\ 0 \le q \le S_{\max}}} F(q)\pmod{10^{16}}.$$
Пусть \(F_k(s)\) обозначает число подмножеств множества \(\{p_1,\dots,p_k\}\) с суммой \(s\). Тогда
$$F_0(0)=1,\qquad F_0(s)=0 \text{ при } s>0,$$
а при \(k\ge 1\) каждое подмножество, дающее сумму \(s\), либо не содержит \(p_k\), либо содержит его ровно один раз. Поэтому получаем
$$F_k(s)=F_{k-1}(s)+F_{k-1}(s-p_k),$$
где второй член считается равным 0, если \(s<p_k\). Именно это разбиение на два взаимоисключающих случая и лежит в основе всей динамики.
Полную двумерную таблицу хранить не нужно. Реализации держат один массив коэффициентов и обновляют его по \(s\) в убывающем порядке. После обработки первых \(k-1\) простых в массиве находятся значения \(F_{k-1}(s)\). При добавлении \(p_k\) используется обновление
$$F(s+p_k)\leftarrow F(s+p_k)+F(s)\pmod{10^{16}}.$$
Ключевое требование состоит в том, что справа должен стоять старый \(F(s)\), а не значение, уже изменённое текущим простым. Именно поэтому проход идёт сверху вниз: так сохраняется смысл 0/1, и одно и то же простое не может быть использовано дважды на одном шаге.
Есть и ещё одна полезная инварианта: после первых \(k\) простых все возможные суммы лежат в пределах
$$0 \le s \le \sigma_k,\qquad \sigma_k=p_1+\cdots+p_k.$$
Поэтому код перебирает только текущую достижимую границу, а не весь массив целиком на каждом шаге.
Для меньшего набора \(\{2,3,5,7\}\) производящая функция равна
$$G(x)=(1+x^2)(1+x^3)(1+x^5)(1+x^7).$$
Её раскрытие даёт
$$G(x)=1+x^2+x^3+2x^5+2x^7+x^8+x^9+2x^{10}+2x^{12}+x^{14}+x^{15}+x^{17}.$$
Простые показатели степени здесь — \(2,3,5,7,17\), а их коэффициенты равны \(1,1,2,2,1\). Значит, число подмножеств с простой суммой равно
$$1+1+2+2+1=7.$$
Этот пример ясно показывает, почему считаются подмножества, а не только сами суммы: коэффициент при \(x^5\) равен 2, потому что и \(\{5\}\), и \(\{2,3\}\) дают простую сумму 5.
После того как все значения \(F(s)\) посчитаны по модулю \(10^{16}\), остаётся только определить, какие индексы \(s\) являются простыми. Поэтому решение запускает второе решето до \(S_{\max}\): оно помечает простые суммы, после чего их коэффициенты суммируются.
Реализации на C++, Python и Java сначала запускают решето до 5000, чтобы получить все входные простые числа. В том же проходе они суммируют их и получают \(S_{\max}\), который задаёт длину динамического массива.
В начале у массива есть ровно одно ненулевое значение: получить сумму 0 до обработки любых простых можно единственным способом, выбрав пустое подмножество. Затем каждое новое простое добавляется обратным проходом по уже достижимым суммам. Если сумма \(s\) имеет \(c\) представлений, то сумма \(s+p\) получает ещё \(c\) представлений после добавления нового простого \(p\).
Каждое значение сразу сокращается по модулю \(10^{16}\), так что точные гигантские числа нигде не хранятся. В реализациях с фиксированной разрядностью это особенно удобно: на каждом шаге складываются только два остатка, оба меньше \(10^{16}\), и это безопасно помещается в 64-битный тип.
После завершения динамики выполняется ещё одно решето, теперь уже на отрезке от 0 до \(S_{\max}\). Это второе решето отвечает не за входные простые, а за вопрос, какие суммы подмножеств сами являются простыми. Последний линейный проход добавляет только те коэффициенты, которые стоят на простых индексах.
Небольшие проверочные случаи согласуются во всех версиях: для простых меньше 10 ответ равен 7, а для простых меньше 20 — 65. Это подтверждает корректность как рекуррентной формулы, так и финального фильтра.
При \(m=\pi(5000)=669\) и \(S_{\max}=1{,}548{,}136\) динамическая часть работает за \(O(mS_{\max})\) времени и использует \(O(S_{\max})\) памяти. Заключительное решето по пространству сумм занимает \(O(S_{\max}\log\log S_{\max})\) времени и при данном размере уступает основному DP-члену.
Главное упрощение состоит в том, что задача перестаёт быть экспоненциальным перебором \(2^{669}\) подмножеств и превращается в полиномиальный подсчёт по достижимым суммам. Именно это делает решение практичным.
لتكن \(\mathcal{P}\) مجموعة جميع الأعداد الأولية الأصغر من 5000. عدد هذه الأوليات هو 669، ولذلك فإن أي بحث مباشر بالقوة الغاشمة سيضطر إلى التعامل مع \(2^{669}\) مجموعة جزئية مختلفة. لكل مجموعة جزئية \(A \subseteq \mathcal{P}\) نحسب المجموع \(\sum_{p \in A} p\). المطلوب هو عدّ المجموعات الجزئية التي يكون مجموع عناصرها عددًا أوليًا أيضًا، ثم إعطاء النتيجة بترديد \(10^{16}\).
العد هنا يقع على المجموعات الجزئية نفسها، لا على القيم المختلفة للمجاميع. فإذا أعطت مجموعتان جزئيتان مختلفتان نفس المجموع الأولي، فيجب احتسابهما معًا. المجموعة الخالية تعطي المجموع 0، و0 ليس عددًا أوليًا، لذلك لا تدخل في الجواب النهائي؛ لكنها تبقى حالة الأساس الصحيحة في البرمجة الديناميكية.
فضاء الحالات الطبيعي هنا هو جميع مجاميع المجموعات الجزئية الممكنة. وبما أن كل عدد أولي من المعطيات يمكن اختياره مرة واحدة على الأكثر، فإن المسألة هي نسخة عدّية من مسألة مجموع المجموعات الجزئية من نوع 0/1.
لنرتب الأوليات تصاعديًا على الصورة
$$p_1 < p_2 < \cdots < p_m,\qquad m=669.$$
إذا عرّفنا
$$G(x)=\prod_{i=1}^{m}(1+x^{p_i}),$$
فإن اختيار الحد \(1\) يعني “لا نستخدم \(p_i\)”، بينما اختيار الحد \(x^{p_i}\) يعني “نستخدم \(p_i\) مرة واحدة بالضبط”. ومن ثم
$$G(x)=\sum_{s=0}^{S_{\max}} F(s)x^s,$$
حيث يمثّل \(F(s)\) عدد المجموعات الجزئية التي مجموعها \(s\)، ويكون
$$S_{\max}=\sum_{p\in\mathcal{P}} p = 1{,}548{,}136.$$
إذًا الجواب المطلوب هو
$$A=\sum_{\substack{q \text{ prime} \\ 0 \le q \le S_{\max}}} F(q)\pmod{10^{16}}.$$
لتكن \(F_k(s)\) عدد المجموعات الجزئية من \(\{p_1,\dots,p_k\}\) التي مجموعها \(s\). عندئذٍ
$$F_0(0)=1,\qquad F_0(s)=0 \quad (s>0),$$
ولكل \(k\ge 1\)، فإن أي مجموعة جزئية تُحسب داخل \(F_k(s)\) تقع في إحدى حالتين منفصلتين: إما أنها لا تحتوي \(p_k\)، أو أنها تحتويه مرة واحدة بالضبط. لذلك نحصل على
$$F_k(s)=F_{k-1}(s)+F_{k-1}(s-p_k),$$
مع اعتبار الحد الثاني مساويًا للصفر إذا كان \(s<p_k\). هذه الملاحظة الثنائية البسيطة هي جوهر الاشتقاق كله.
لا تحتاج التطبيقات إلى تخزين الجدول الثنائي الكامل. بدلًا من ذلك، تحتفظ بمصفوفة واحدة للمعاملات وتحدّثها بترتيب تنازلي في \(s\). بعد معالجة أول \(k-1\) عدد أولي، تحتوي المصفوفة على القيم \(F_{k-1}(s)\). وعند إدخال \(p_k\) يكون التحديث
$$F(s+p_k)\leftarrow F(s+p_k)+F(s)\pmod{10^{16}}.$$
النقطة الحاسمة هي أن القيمة \(F(s)\) على الطرف الأيمن يجب أن تبقى هي القيمة القديمة قبل استخدام \(p_k\)، لا قيمةً تم تعديلها بالفعل في الجولة نفسها. لهذا السبب يمرّ الكود على \(s\) من الأكبر إلى الأصغر. وبهذا يبقى معنى 0/1 صحيحًا: كل عدد أولي يُستخدم صفر مرة أو مرة واحدة فقط في تلك المرحلة.
وهناك ثابت آخر مهم: بعد معالجة أول \(k\) أوليات، تكون جميع المجاميع الممكنة ضمن المجال
$$0 \le s \le \sigma_k,\qquad \sigma_k=p_1+\cdots+p_k.$$
ولهذا لا يفحص الكود كامل المصفوفة في كل خطوة، بل يتوقف عند الحد الحالي الممكن الوصول إليه.
إذا أخذنا المجموعة \(\{2,3,5,7\}\)، فإن الدالة المولدة تصبح
$$G(x)=(1+x^2)(1+x^3)(1+x^5)(1+x^7).$$
وبتوسيعها نحصل على
$$G(x)=1+x^2+x^3+2x^5+2x^7+x^8+x^9+2x^{10}+2x^{12}+x^{14}+x^{15}+x^{17}.$$
الأسس الأولية هنا هي \(2,3,5,7,17\)، ومعاملاتها هي \(1,1,2,2,1\). إذًا عدد المجموعات الجزئية ذات المجموع الأولي يساوي
$$1+1+2+2+1=7.$$
ويُظهر هذا المثال أيضًا لماذا نعدّ المجموعات الجزئية لا القيم المختلفة فقط: فمعامل \(x^5\) يساوي 2 لأن كلًا من \(\{5\}\) و\(\{2,3\}\) يعطيان المجموع الأولي 5.
بعد حساب جميع القيم \(F(s)\) بترديد \(10^{16}\)، لا يبقى إلا تحديد أي الفهارس \(s\) هي أعداد أولية. ولهذا السبب تُجرى غربلة ثانية حتى \(S_{\max}\): هذه المرة لا نغربل أوليات الإدخال، بل نغربل فضاء المجاميع الممكنة نفسه، ثم نجمع القيم الموجودة عند الفهارس الأولية فقط.
تبدأ تطبيقات C++ وPython وJava بتشغيل غربال حتى 5000 لاستخراج جميع الأوليات الداخلة في الحساب. وفي المرور نفسه تجمع أيضًا القيمة \(S_{\max}\)، لأنها تحدد طول مصفوفة البرمجة الديناميكية.
تبدأ المصفوفة بقيمة غير صفرية واحدة فقط: هناك طريقة وحيدة للحصول على المجموع 0 قبل معالجة أي عدد أولي، وهي اختيار المجموعة الخالية. بعد ذلك يُدمج كل عدد أولي جديد عبر مرور تنازلي على المجاميع الممكنة حاليًا. فإذا كان للمجموع \(s\) عدد \(c\) من التمثيلات، فإن المجموع \(s+p\) يكتسب \(c\) تمثيلات إضافية عند إلحاق الأولي الجديد \(p\).
كل خانة تُخفَّض مباشرة بترديد \(10^{16}\)، ولذلك لا يحتاج التنفيذ أبدًا إلى حفظ الأعداد الضخمة جدًا على صورتها الدقيقة. وفي الإصدارات التي تستخدم أعدادًا ثابتة العرض، تبقى العملية مريحة وآمنة لأن كل تحديث يجمع باقيين أصغر من \(10^{16}\)، وهذا يقع بسهولة ضمن مجال 64 بت.
بعد اكتمال مصفوفة عدّ المجاميع، تُجرى غربلة أخرى على المجال من 0 إلى \(S_{\max}\). هذه الغربلة الثانية مخصّصة لمعرفة أي المجاميع نفسها أولية، لا لاستخراج أوليات الإدخال مرة أخرى. وفي المرور الخطي الأخير تُجمع فقط الخانات الواقعة عند فهارس أولية.
الحالات الصغيرة المستخدمة للتحقق متسقة بين التطبيقات: عند استخدام الأوليات الأصغر من 10 تكون النتيجة 7، وعند استخدام الأوليات الأصغر من 20 تكون النتيجة 65. وهذا يؤكد أن العلاقة العودية ومرحلة التصفية النهائية تعملان معًا كما ينبغي.
إذا كتبنا \(m=\pi(5000)=669\) و\(S_{\max}=1{,}548{,}136\)، فإن كلفة البرمجة الديناميكية هي \(O(mS_{\max})\) زمنًا و\(O(S_{\max})\) ذاكرةً. أما الغربلة النهائية على مجال المجاميع فتعمل في \(O(S_{\max}\log\log S_{\max})\)، وهي أصغر من الحد الرئيسي للبرمجة الديناميكية عند هذا الحجم.
الفكرة الحاسمة هي أن المسألة لم تعد تعدادًا أسيًا على \(2^{669}\) مجموعة جزئية، بل أصبحت عدًّا كثير الحدود على مجاميع يمكن الوصول إليها. هذا هو الاختزال الذي يجعل الحل عمليًا.