Consider the sequence
$$a_i=i^i\qquad(1\le i\le N),$$
with \(N=250250\) in the main problem. We must count the non-empty subsets \(S\subseteq\{1,\dots,N\}\) such that
$$\sum_{i\in S} a_i \equiv 0 \pmod{250},$$
and report the result modulo
$$M=10^{16}.$$
The direct search space has size \(2^N-1\), so brute force is impossible. The key observation is that divisibility by \(250\) depends only on residue classes modulo \(250\), not on the full size of the numbers \(i^i\).
Let
$$r_i=a_i\bmod 250=i^i\bmod 250.$$
Then for any subset \(S\),
$$\sum_{i\in S} a_i \equiv \sum_{i\in S} r_i \pmod{250}.$$
So the original problem is equivalent to counting subsets whose residue sum is \(0\) modulo \(250\).
The congruence rule
$$x\equiv y\pmod{250}\quad\Longrightarrow\quad x+z\equiv y+z\pmod{250}$$
shows that divisibility of a sum by \(250\) depends only on each summand's class in \(\mathbb{Z}/250\mathbb{Z}\). Therefore the gigantic integers \(i^i\) never need to be stored explicitly. Only the 250 possible residues matter.
For \(k=0,1,\dots,N\), define
$$dp_k(t)=\#\left\{S\subseteq\{1,\dots,k\}:\sum_{i\in S} r_i\equiv t\pmod{250}\right\}.$$
The desired count is \(dp_N(0)-1\), because \(dp_N(0)\) includes the empty subset.
Before processing any terms, there is exactly one subset of \(\{1,\dots,0\}\): the empty subset. Its sum is \(0\). Hence
$$dp_0(0)=1,\qquad dp_0(t)=0\quad(1\le t\le 249).$$
When we process residue \(r_k\), every old subset has two possibilities:
1. Exclude \(k\): its residue class stays the same.
2. Include \(k\): its residue class shifts by \(r_k\) modulo \(250\).
Therefore
$$dp_k(t)=dp_{k-1}(t)+dp_{k-1}(t-r_k)\pmod{M},$$
where \(t-r_k\) is interpreted modulo \(250\).
The code implements the same recurrence in forward form with a temporary array next:
$$next[t]=dp[t],$$
$$next[(t+r_k)\bmod 250]\leftarrow next[(t+r_k)\bmod 250]+dp[t]\pmod{M}.$$
Using a second array is important: it guarantees 0/1 behavior. If we updated dp in place, a newly created subset could be reused in the same iteration, which would incorrectly allow the same element to be chosen multiple times.
The same recurrence can be written as a product of polynomials modulo \(x^{250}-1\):
$$F_N(x)=\prod_{i=1}^{N}\left(1+x^{r_i}\right)\pmod{x^{250}-1}.$$
The coefficient of \(x^t\) in \(F_N(x)\) counts subsets whose residue sum is \(t\) modulo \(250\). The dynamic program is simply a coefficient-update algorithm for this product.
The code uses repeated squaring to compute
$$r_i=i^i\bmod 250$$
in \(O(\log i)\) time. This is the standard modular exponentiation recurrence:
$$b^{2m}\equiv (b^2)^m\pmod{250},\qquad b^{2m+1}\equiv b\cdot (b^2)^m\pmod{250}.$$
Because multiplication is reduced modulo \(250\) at every step, intermediate numbers stay small.
For \(N=10\), the residues are
$$1^1,2^2,\dots,10^{10}\equiv 1,4,27,6,125,156,43,216,239,0 \pmod{250}.$$
The checkpoint in the code states that the answer is \(5\). Indeed, the non-empty divisible subsets are:
$$\{1,3,4,8\},\qquad \{1,2,4,9\},\qquad \{10\},$$
$$\{1,3,4,8,10\},\qquad \{1,2,4,9,10\}.$$
For example,
$$1^1+3^3+4^4+8^8\equiv 1+27+6+216=250\equiv 0\pmod{250},$$
and since \(10^{10}\equiv 0\pmod{250}\), appending the 10th term preserves divisibility. Hence there are exactly \(5\) valid non-empty subsets.
The DP starts from the empty subset, so \(dp_N(0)\) counts all subsets with residue \(0\), including
$$S=\varnothing.$$
Since the problem asks only for non-empty subsets, the final answer is
$$\boxed{(dp_N(0)-1)\bmod M.}$$
There are \(N\) iterations, and each iteration updates all \(250\) residue classes. Hence the dynamic-programming work is
$$O(N\cdot 250)=O(ND).$$
The memory usage is \(O(250)\), since only the current and next DP rows are stored. Modular exponentiation adds \(O(\log i)\) work per term, so the full cost is \(O(ND+N\log N)\); for fixed \(D=250\), this is still easily practical.
The C++ solution initializes dp[0]=1 and all other states to zero. For each \(i\) from \(1\) to limit, it computes residue = powmod_int(i, i, divisor), copies dp into next, applies the include-transition to every residue class, and then swaps the arrays. After the loop, dp[0] contains the number of divisible subsets including the empty one, so the code returns (dp[0] + modulo - 1) % modulo. The Python and Java versions implement the same recurrence.
Betrachte die Folge
$$a_i=i^i\qquad(1\le i\le N),$$
wobei im Hauptproblem \(N=250250\) gilt. Gesucht ist die Anzahl aller nichtleeren Teilmengen \(S\subseteq\{1,\dots,N\}\) mit
$$\sum_{i\in S} a_i \equiv 0 \pmod{250},$$
wobei das Ergebnis modulo
$$M=10^{16}$$
ausgegeben wird. Eine brute-force Suche über \(2^N-1\) Teilmengen ist unmöglich; entscheidend ist, dass nur die Restklassen modulo \(250\) zählen.
Setze
$$r_i=a_i\bmod 250=i^i\bmod 250.$$
Dann gilt für jede Teilmenge \(S\):
$$\sum_{i\in S} a_i \equiv \sum_{i\in S} r_i \pmod{250}.$$
Damit reduziert sich das Problem auf das Zählen von Teilmengen, deren Restklassensumme \(0\) modulo \(250\) ist.
Aus
$$x\equiv y\pmod{250}\quad\Longrightarrow\quad x+z\equiv y+z\pmod{250}$$
folgt, dass die Teilbarkeit einer Summe durch \(250\) nur von den Restklassen der Summanden abhängt. Die oft riesigen Zahlen \(i^i\) müssen also nie vollständig berechnet werden.
Für \(k=0,1,\dots,N\) definieren wir
$$dp_k(t)=\#\left\{S\subseteq\{1,\dots,k\}:\sum_{i\in S} r_i\equiv t\pmod{250}\right\}.$$
Gesucht ist also \(dp_N(0)-1\), weil \(dp_N(0)\) auch die leere Menge enthält.
Vor der Verarbeitung eines Elements gibt es genau eine Teilmenge, nämlich die leere Menge. Ihre Summe ist \(0\). Daher:
$$dp_0(0)=1,\qquad dp_0(t)=0\quad(1\le t\le 249).$$
Beim Verarbeiten von \(r_k\) gibt es für jede bisherige Teilmenge zwei Möglichkeiten:
1. \(k\) nicht nehmen: die Restklasse bleibt gleich.
2. \(k\) nehmen: die Restklasse verschiebt sich um \(r_k\) modulo \(250\).
Daraus folgt
$$dp_k(t)=dp_{k-1}(t)+dp_{k-1}(t-r_k)\pmod{M},$$
wobei \(t-r_k\) modulo \(250\) gelesen wird.
Der Code benutzt dieselbe Rekursion in Vorwärtsrichtung mit einem Hilfsarray next:
$$next[t]=dp[t],$$
$$next[(t+r_k)\bmod 250]\leftarrow next[(t+r_k)\bmod 250]+dp[t]\pmod{M}.$$
Das zweite Array ist wichtig: Nur so bleibt die Wahl wirklich 0/1. Ein In-place-Update würde neu erzeugte Zustände sofort wiederverwenden und damit ein Element mehrfach zählen.
Äquivalent dazu kann man das Produkt
$$F_N(x)=\prod_{i=1}^{N}(1+x^{r_i})\pmod{x^{250}-1}$$
betrachten. Der Koeffizient von \(x^t\) zählt dann genau die Teilmengen mit Summenrest \(t\) modulo \(250\). Die DP ist also eine Koeffizientenaktualisierung dieser erzeugenden Funktion.
Die Implementierung berechnet
$$r_i=i^i\bmod 250$$
mittels binärer Exponentiation in \(O(\log i)\) Zeit. Dabei nutzt man
$$b^{2m}\equiv (b^2)^m\pmod{250},\qquad b^{2m+1}\equiv b\cdot (b^2)^m\pmod{250}.$$
Da nach jeder Multiplikation sofort modulo \(250\) reduziert wird, bleiben alle Zwischenwerte klein.
Für \(N=10\) erhält man die Restklassen
$$1,4,27,6,125,156,43,216,239,0 \pmod{250}.$$
Der Checkpoint im Code besagt, dass die Anzahl gültiger nichtleerer Teilmengen gleich \(5\) ist. Diese Teilmengen sind:
$$\{1,3,4,8\},\qquad \{1,2,4,9\},\qquad \{10\},$$
$$\{1,3,4,8,10\},\qquad \{1,2,4,9,10\}.$$
Zum Beispiel gilt
$$1^1+3^3+4^4+8^8\equiv 1+27+6+216=250\equiv 0\pmod{250}.$$
Außerdem ist \(10^{10}\equiv 0\pmod{250}\), daher verdoppelt das Hinzufügen des 10. Terms jede bereits gültige Teilmenge.
\(dp_N(0)\) zählt auch die leere Menge
$$S=\varnothing,$$
deren Summe ebenfalls \(0\) ist. Daher lautet die gesuchte Zahl
$$\boxed{(dp_N(0)-1)\bmod M.}$$
In jedem der \(N\) Schritte werden alle \(250\) Restklassen aktualisiert. Damit kostet die DP
$$O(N\cdot 250)=O(ND).$$
Der Speicherverbrauch ist \(O(250)\), weil nur zwei Arrays der Länge \(250\) gehalten werden. Die modulare Exponentiation fügt \(O(\log i)\) Arbeit pro Term hinzu, insgesamt also \(O(ND+N\log N)\), was für festes \(D=250\) problemlos praktikabel ist.
Die C++-Lösung setzt zunächst dp[0]=1. Für jedes \(i\) von \(1\) bis limit berechnet sie mit powmod_int(i, i, divisor) den Rest \(r_i\), kopiert dp nach next, addiert die Einbezieh-Übergänge in alle Zielrestklassen und vertauscht anschließend die Arrays. Nach der letzten Iteration enthält dp[0] die Anzahl aller durch \(250\) teilbaren Teilmengen einschließlich der leeren Menge; deshalb gibt der Code (dp[0] + modulo - 1) % modulo zurück. Python und Java folgen exakt derselben Logik.
Şu diziyi ele alalım:
$$a_i=i^i\qquad(1\le i\le N).$$
Ana problemde \(N=250250\)'dir. Amaç, \(\{1,\dots,N\}\) içindeki boş olmayan alt kümelerden,
$$\sum_{i\in S} a_i \equiv 0 \pmod{250}$$
koşulunu sağlayanların sayısını bulmak ve sonucu
$$M=10^{16}$$
modunda vermektir. Doğrudan arama uzayı \(2^N-1\) boyutunda olduğu için kaba kuvvet yaklaşımı imkânsızdır. Kritik gözlem, 250 ile bölünebilirliğin yalnızca mod 250 kalıntılarına bağlı olmasıdır.
Her terim için
$$r_i=a_i\bmod 250=i^i\bmod 250$$
tanımlayalım. O zaman herhangi bir \(S\) alt kümesi için
$$\sum_{i\in S} a_i \equiv \sum_{i\in S} r_i \pmod{250}$$
olur. Yani asıl problem, kalıntıları toplayıp toplamı \(0\) mod \(250\) olan alt kümeleri sayma problemine indirgenir.
Çünkü
$$x\equiv y\pmod{250}\quad\Longrightarrow\quad x+z\equiv y+z\pmod{250}$$
özelliği geçerlidir. Dolayısıyla \(i^i\) sayıları çok büyük olsa bile, alt küme toplamının 250'ye bölünüp bölünmediğini belirlemek için yalnızca 250 farklı kalıntı sınıfı önemlidir.
\(k=0,1,\dots,N\) için
$$dp_k(t)=\#\left\{S\subseteq\{1,\dots,k\}:\sum_{i\in S} r_i\equiv t\pmod{250}\right\}$$
şeklinde tanımlayalım. Aradığımız şey \(dp_N(0)-1\)'dir; çünkü \(dp_N(0)\) içinde boş küme de sayılır.
Hiç terim işlenmeden önce yalnızca bir alt küme vardır: boş küme. Onun toplamı \(0\)'dır. Bu yüzden
$$dp_0(0)=1,\qquad dp_0(t)=0\quad(1\le t\le 249).$$
\(r_k\) kalıntısını işlerken her eski alt küme için iki seçenek vardır:
1. \(k\)'yı alma: toplam kalıntısı değişmez.
2. \(k\)'yı al: toplam kalıntısı \(r_k\) kadar kayar.
Bu nedenle
$$dp_k(t)=dp_{k-1}(t)+dp_{k-1}(t-r_k)\pmod{M}$$
olur; burada \(t-r_k\) ifadesi mod 250 yorumlanır.
Kod bunu ileri yönde şu biçimde uygular:
$$next[t]=dp[t],$$
$$next[(t+r_k)\bmod 250]\leftarrow next[(t+r_k)\bmod 250]+dp[t]\pmod{M}.$$
Geçici next dizisi kullanmak önemlidir. Eğer aynı dizi yerinde güncellenseydi, yeni oluşturulan durumlar aynı turda yeniden kullanılabilir ve bu da tek bir elemanın birden fazla kez seçilmiş gibi sayılmasına yol açardı.
Aynı fikir kombinatorik olarak
$$F_N(x)=\prod_{i=1}^{N}(1+x^{r_i})\pmod{x^{250}-1}$$
şeklinde de yazılabilir. Burada \(x^t\)'nin katsayısı, kalıntı toplamı \(t\) mod 250 olan alt kümelerin sayısını verir. Dinamik program, aslında bu çarpımın katsayılarını adım adım güncellemektedir.
Kod,
$$r_i=i^i\bmod 250$$
değerini hızlı üs alma ile \(O(\log i)\) zamanda hesaplar. Temel özdeşlikler şunlardır:
$$b^{2m}\equiv (b^2)^m\pmod{250},\qquad b^{2m+1}\equiv b\cdot (b^2)^m\pmod{250}.$$
Her çarpımdan sonra mod alındığı için ara değerler küçük kalır; devasa sayılar oluşturmaya gerek yoktur.
\(N=10\) için kalıntılar şunlardır:
$$1,4,27,6,125,156,43,216,239,0 \pmod{250}.$$
Koddaki checkpoint'e göre cevap \(5\)'tir. Gerçekten de geçerli boş olmayan alt kümeler şunlardır:
$$\{1,3,4,8\},\qquad \{1,2,4,9\},\qquad \{10\},$$
$$\{1,3,4,8,10\},\qquad \{1,2,4,9,10\}.$$
Örneğin
$$1^1+3^3+4^4+8^8\equiv 1+27+6+216=250\equiv 0\pmod{250}.$$
Ayrıca \(10^{10}\equiv 0\pmod{250}\) olduğundan, 10. terimi eklemek mevcut her geçerli alt kümeyi kalıntıyı değiştirmeden bir kez daha üretir.
DP, başlangıçta boş kümeyi içererek başlar. Bu yüzden \(dp_N(0)\) değeri içinde
$$S=\varnothing$$
de vardır. Problem yalnızca boş olmayan alt kümeleri istediği için sonuç
$$\boxed{(dp_N(0)-1)\bmod M}$$
olur.
Her \(i\) için 250 kalıntı sınıfı güncellendiğinden DP kısmı
$$O(N\cdot 250)=O(ND)$$
zaman alır. Bellek tüketimi \(O(250)\)'dir; çünkü yalnızca mevcut ve sonraki DP satırı tutulur. Hızlı üs alma her terim için \(O(\log i)\) iş ekler; dolayısıyla toplam süre \(O(ND+N\log N)\) olur ve \(D=250\) sabit olduğu için gayet uygulanabilirdir.
C++ çözümü önce dp[0]=1 yapar. Sonra \(1\)'den limit'e kadar her \(i\) için powmod_int(i, i, divisor) ile kalıntıyı bulur, dp'yi next'e kopyalar, "elemanı alma" durumunu zaten kopyada korur, "elemanı alma" durumunu ise \((r+\text{residue})\bmod 250\) hedeflerine ekler. Tur bitince dp.swap(next) ile yeni durumlar aktif hale gelir. Döngü sonunda dp[0] bölünebilen tüm alt kümeleri boş küme dahil saydığı için kod (dp[0] + modulo - 1) % modulo döndürür. Python ve Java sürümleri aynı mantığı izler.
Consideremos la sucesión
$$a_i=i^i\qquad(1\le i\le N),$$
con \(N=250250\) en el problema principal. Debemos contar los subconjuntos no vacíos \(S\subseteq\{1,\dots,N\}\) tales que
$$\sum_{i\in S} a_i \equiv 0 \pmod{250},$$
y dar la respuesta módulo
$$M=10^{16}.$$
El espacio de búsqueda directo tiene tamaño \(2^N-1\), así que la fuerza bruta es imposible. La observación decisiva es que la divisibilidad por \(250\) depende solo de las clases residuales módulo \(250\), no del tamaño completo de los números \(i^i\).
Definimos
$$r_i=a_i\bmod 250=i^i\bmod 250.$$
Entonces, para cualquier subconjunto \(S\),
$$\sum_{i\in S} a_i \equiv \sum_{i\in S} r_i \pmod{250}.$$
Por tanto, el problema original equivale a contar los subconjuntos cuya suma de residuos es \(0\) módulo \(250\).
La regla de congruencias
$$x\equiv y\pmod{250}\quad\Longrightarrow\quad x+z\equiv y+z\pmod{250}$$
muestra que la divisibilidad de una suma por \(250\) depende únicamente de la clase residual de cada sumando en \(\mathbb{Z}/250\mathbb{Z}\). Por eso nunca hace falta almacenar los enormes enteros \(i^i\); bastan sus 250 residuos posibles.
Para \(k=0,1,\dots,N\), definimos
$$dp_k(t)=\#\left\{S\subseteq\{1,\dots,k\}:\sum_{i\in S} r_i\equiv t\pmod{250}\right\}.$$
La cantidad buscada es \(dp_N(0)-1\), porque \(dp_N(0)\) también incluye el subconjunto vacío.
Antes de procesar ningún término existe exactamente un subconjunto de \(\{1,\dots,0\}\): el subconjunto vacío. Su suma es \(0\). Luego
$$dp_0(0)=1,\qquad dp_0(t)=0\quad(1\le t\le 249).$$
Al procesar el residuo \(r_k\), cada subconjunto anterior tiene dos posibilidades:
1. Excluir \(k\): la clase residual no cambia.
2. Incluir \(k\): la clase residual se desplaza en \(r_k\) módulo \(250\).
Por consiguiente,
$$dp_k(t)=dp_{k-1}(t)+dp_{k-1}(t-r_k)\pmod{M},$$
donde \(t-r_k\) se interpreta módulo \(250\).
El código implementa la misma recurrencia en forma directa con un arreglo temporal next:
$$next[t]=dp[t],$$
$$next[(t+r_k)\bmod 250]\leftarrow next[(t+r_k)\bmod 250]+dp[t]\pmod{M}.$$
Usar un segundo arreglo es esencial: garantiza el comportamiento 0/1. Si actualizáramos dp in situ, un subconjunto recién creado podría reutilizarse en la misma iteración y eso contaría el mismo elemento varias veces.
La misma idea puede escribirse como un producto de polinomios módulo \(x^{250}-1\):
$$F_N(x)=\prod_{i=1}^{N}\left(1+x^{r_i}\right)\pmod{x^{250}-1}.$$
El coeficiente de \(x^t\) en \(F_N(x)\) cuenta los subconjuntos cuya suma residual es \(t\) módulo \(250\). El programa dinámico no es más que un algoritmo para actualizar esos coeficientes.
El código usa exponenciación binaria para calcular
$$r_i=i^i\bmod 250$$
en tiempo \(O(\log i)\). La recurrencia estándar es
$$b^{2m}\equiv (b^2)^m\pmod{250},\qquad b^{2m+1}\equiv b\cdot (b^2)^m\pmod{250}.$$
Como se reduce módulo \(250\) tras cada multiplicación, los valores intermedios permanecen pequeños.
Para \(N=10\), los residuos son
$$1^1,2^2,\dots,10^{10}\equiv 1,4,27,6,125,156,43,216,239,0 \pmod{250}.$$
El checkpoint del código afirma que la respuesta es \(5\). En efecto, los subconjuntos no vacíos divisibles son:
$$\{1,3,4,8\},\qquad \{1,2,4,9\},\qquad \{10\},$$
$$\{1,3,4,8,10\},\qquad \{1,2,4,9,10\}.$$
Por ejemplo,
$$1^1+3^3+4^4+8^8\equiv 1+27+6+216=250\equiv 0\pmod{250},$$
y como \(10^{10}\equiv 0\pmod{250}\), añadir el décimo término conserva la divisibilidad. Por eso hay exactamente \(5\) subconjuntos válidos.
La DP arranca desde el subconjunto vacío, así que \(dp_N(0)\) cuenta todos los subconjuntos con residuo \(0\), incluido
$$S=\varnothing.$$
Como el problema pide solo subconjuntos no vacíos, la respuesta final es
$$\boxed{(dp_N(0)-1)\bmod M.}$$
Hay \(N\) iteraciones y en cada una se actualizan las \(250\) clases residuales. Por tanto, el coste de la DP es
$$O(N\cdot 250)=O(ND).$$
El uso de memoria es \(O(250)\), porque solo se almacenan la fila actual y la siguiente. La exponenciación modular añade \(O(\log i)\) trabajo por término, así que el coste total es \(O(ND+N\log N)\); con \(D=250\) fijo, sigue siendo completamente manejable.
La solución en C++ inicializa dp[0]=1 y el resto a cero. Para cada \(i\) entre \(1\) y limit, calcula residue = powmod_int(i, i, divisor), copia dp en next, aplica la transición de inclusión a todas las clases residuales y después intercambia ambos arreglos. Al final del bucle, dp[0] contiene el número de subconjuntos divisibles incluyendo el vacío, de modo que el código devuelve (dp[0] + modulo - 1) % modulo. Las versiones en Python y Java siguen exactamente la misma recurrencia.
考虑数列
$$a_i=i^i\qquad(1\le i\le N),$$
在原题中 \(N=250250\)。我们要统计所有非空子集 \(S\subseteq\{1,\dots,N\}\)，使得
$$\sum_{i\in S} a_i \equiv 0 \pmod{250},$$
并将结果对
$$M=10^{16}$$
取模。直接枚举的搜索空间大小为 \(2^N-1\)，显然不可行。关键在于：是否能被 \(250\) 整除，只取决于每一项的模 \(250\) 余数，而不取决于 \(i^i\) 的完整数值。
记
$$r_i=a_i\bmod 250=i^i\bmod 250.$$
那么对任意子集 \(S\)，都有
$$\sum_{i\in S} a_i \equiv \sum_{i\in S} r_i \pmod{250}.$$
因此原问题等价于统计“余数和为 \(0\) 模 \(250\)”的子集个数。
因为同余满足
$$x\equiv y\pmod{250}\quad\Longrightarrow\quad x+z\equiv y+z\pmod{250}.$$
所以一个和是否被 \(250\) 整除，只由各个加数在 \(\mathbb{Z}/250\mathbb{Z}\) 中的类决定。巨大的整数 \(i^i\) 完全没有必要显式构造，只需要 250 个可能的余数。
对 \(k=0,1,\dots,N\)，定义
$$dp_k(t)=\#\left\{S\subseteq\{1,\dots,k\}:\sum_{i\in S} r_i\equiv t\pmod{250}\right\}.$$
最终想要的答案是 \(dp_N(0)-1\)，因为 \(dp_N(0)\) 把空集也算进去了。
在还没有处理任何元素时，\(\{1,\dots,0\}\) 只有一个子集，就是空集，它的和为 \(0\)。因此
$$dp_0(0)=1,\qquad dp_0(t)=0\quad(1\le t\le 249).$$
处理第 \(k\) 个余数 \(r_k\) 时，每个旧子集都有两种选择：
1. 不选 \(k\)：余数类不变。
2. 选 \(k\)：余数类增加 \(r_k\)（模 250）。
于是有
$$dp_k(t)=dp_{k-1}(t)+dp_{k-1}(t-r_k)\pmod{M},$$
其中 \(t-r_k\) 按模 \(250\) 理解。
代码使用一个临时数组 next，以前向形式实现同样的递推：
$$next[t]=dp[t],$$
$$next[(t+r_k)\bmod 250]\leftarrow next[(t+r_k)\bmod 250]+dp[t]\pmod{M}.$$
这里必须使用第二个数组，才能保证 0/1 选择。如果原地更新 dp，同一轮中新生成的状态会被再次利用，相当于把同一个元素选了多次。
同样的过程也可以写成模 \(x^{250}-1\) 的多项式乘积：
$$F_N(x)=\prod_{i=1}^{N}\left(1+x^{r_i}\right)\pmod{x^{250}-1}.$$
其中 \(x^t\) 的系数恰好等于“余数和为 \(t\) 模 \(250\)”的子集数。动态规划本质上就是逐步更新这个乘积的系数。
代码使用二分快速幂计算
$$r_i=i^i\bmod 250$$
其时间复杂度为 \(O(\log i)\)。使用的基本递推是
$$b^{2m}\equiv (b^2)^m\pmod{250},\qquad b^{2m+1}\equiv b\cdot (b^2)^m\pmod{250}.$$
由于每一步乘法后都立即取模 \(250\)，中间数始终很小。
当 \(N=10\) 时，余数为
$$1^1,2^2,\dots,10^{10}\equiv 1,4,27,6,125,156,43,216,239,0 \pmod{250}.$$
代码中的 checkpoint 表明答案是 \(5\)。确实，满足条件的非空子集是：
$$\{1,3,4,8\},\qquad \{1,2,4,9\},\qquad \{10\},$$
$$\{1,3,4,8,10\},\qquad \{1,2,4,9,10\}.$$
例如
$$1^1+3^3+4^4+8^8\equiv 1+27+6+216=250\equiv 0\pmod{250}.$$
又因为 \(10^{10}\equiv 0\pmod{250}\)，所以把第 10 项附加到任何已满足条件的子集上，仍然保持可整除性。因此总数正好是 \(5\)。
DP 从空集开始，所以 \(dp_N(0)\) 统计了所有余数为 0 的子集，其中包括
$$S=\varnothing.$$
而题目只要求非空子集，因此最终答案为
$$\boxed{(dp_N(0)-1)\bmod M.}$$
共有 \(N\) 轮，每一轮都要更新 250 个余数类，因此 DP 的主成本是
$$O(N\cdot 250)=O(ND).$$
空间复杂度为 \(O(250)\)，因为只保存当前和下一行两个数组。快速幂还会带来每项 \(O(\log i)\) 的工作量，所以总复杂度为 \(O(ND+N\log N)\)；在 \(D=250\) 固定时，这仍然完全可行。
C++ 实现先令 dp[0]=1，其他状态为 0。随后对每个 \(i=1,2,\dots,\texttt{limit}\)，先通过 powmod_int(i, i, divisor) 求出余数 \(r_i\)，再把 dp 复制到 next，然后把“选择该元素”产生的贡献加到所有目标余数类上，最后交换两个数组。循环结束后，dp[0] 就是所有和可被 250 整除的子集数（包含空集），于是代码返回 (dp[0] + modulo - 1) % modulo。Python 和 Java 版本实现的是同一递推。
Рассмотрим последовательность
$$a_i=i^i\qquad(1\le i\le N),$$
где в основной задаче \(N=250250\). Нужно посчитать число непустых подмножеств \(S\subseteq\{1,\dots,N\}\), для которых
$$\sum_{i\in S} a_i \equiv 0 \pmod{250},$$
и вывести ответ по модулю
$$M=10^{16}.$$
Прямой перебор невозможен, поскольку пространство поиска имеет размер \(2^N-1\). Ключевое наблюдение состоит в том, что делимость на \(250\) зависит только от остатков по модулю \(250\), а не от самих огромных чисел \(i^i\).
Обозначим
$$r_i=a_i\bmod 250=i^i\bmod 250.$$
Тогда для любого подмножества \(S\) выполняется
$$\sum_{i\in S} a_i \equiv \sum_{i\in S} r_i \pmod{250}.$$
Следовательно, исходная задача эквивалентна подсчёту подмножеств, у которых сумма остатков сравнима с нулём по модулю \(250\).
Свойство сравнений
$$x\equiv y\pmod{250}\quad\Longrightarrow\quad x+z\equiv y+z\pmod{250}$$
показывает, что делимость суммы на \(250\) определяется только классами её слагаемых в \(\mathbb{Z}/250\mathbb{Z}\). Поэтому числа \(i^i\) не нужно вычислять целиком; достаточно знать один из 250 возможных остатков.
Для \(k=0,1,\dots,N\) определим
$$dp_k(t)=\#\left\{S\subseteq\{1,\dots,k\}:\sum_{i\in S} r_i\equiv t\pmod{250}\right\}.$$
Тогда искомое количество равно \(dp_N(0)-1\), поскольку \(dp_N(0)\) считает также пустое подмножество.
До обработки элементов существует ровно одно подмножество множества \(\{1,\dots,0\}\): пустое. Его сумма равна нулю. Поэтому
$$dp_0(0)=1,\qquad dp_0(t)=0\quad(1\le t\le 249).$$
При обработке остатка \(r_k\) у каждого старого подмножества есть два варианта:
1. Не брать \(k\): остаток суммы не меняется.
2. Взять \(k\): остаток суммы сдвигается на \(r_k\) по модулю \(250\).
Отсюда следует рекурсия
$$dp_k(t)=dp_{k-1}(t)+dp_{k-1}(t-r_k)\pmod{M},$$
где \(t-r_k\) понимается по модулю \(250\).
В коде та же формула записана в прямом виде с временным массивом next:
$$next[t]=dp[t],$$
$$next[(t+r_k)\bmod 250]\leftarrow next[(t+r_k)\bmod 250]+dp[t]\pmod{M}.$$
Второй массив обязателен: он сохраняет 0/1-характер выбора. При обновлении на месте новые состояния могли бы использоваться повторно в той же итерации, что эквивалентно многократному выбору одного и того же элемента.
Ту же идею можно записать как произведение полиномов по модулю \(x^{250}-1\):
$$F_N(x)=\prod_{i=1}^{N}\left(1+x^{r_i}\right)\pmod{x^{250}-1}.$$
Коэффициент при \(x^t\) в \(F_N(x)\) равен числу подмножеств, у которых сумма остатков даёт \(t\) по модулю \(250\). Динамика программы просто обновляет эти коэффициенты.
Для вычисления
$$r_i=i^i\bmod 250$$
используется бинарное возведение в степень за \(O(\log i)\). Применяются стандартные тождества
$$b^{2m}\equiv (b^2)^m\pmod{250},\qquad b^{2m+1}\equiv b\cdot (b^2)^m\pmod{250}.$$
После каждого умножения сразу берётся остаток по модулю \(250\), поэтому промежуточные значения остаются маленькими.
При \(N=10\) получаем остатки
$$1^1,2^2,\dots,10^{10}\equiv 1,4,27,6,125,156,43,216,239,0 \pmod{250}.$$
Проверка в коде утверждает, что ответ равен \(5\). Действительно, подходящие непустые подмножества таковы:
$$\{1,3,4,8\},\qquad \{1,2,4,9\},\qquad \{10\},$$
$$\{1,3,4,8,10\},\qquad \{1,2,4,9,10\}.$$
Например,
$$1^1+3^3+4^4+8^8\equiv 1+27+6+216=250\equiv 0\pmod{250}.$$
Кроме того, \(10^{10}\equiv 0\pmod{250}\), поэтому добавление десятого члена сохраняет делимость. Отсюда и получается ровно \(5\) допустимых подмножеств.
DP стартует с пустого подмножества, поэтому \(dp_N(0)\) считает все подмножества с остатком \(0\), включая
$$S=\varnothing.$$
Так как задача спрашивает только непустые подмножества, окончательный ответ равен
$$\boxed{(dp_N(0)-1)\bmod M.}$$
Имеется \(N\) итераций, и на каждой обновляются все 250 классов остатков. Следовательно, основная стоимость DP равна
$$O(N\cdot 250)=O(ND).$$
Память составляет \(O(250)\), так как хранятся только текущая и следующая строки DP. Модульное возведение в степень добавляет \(O(\log i)\) на каждый член, так что полный расход времени равен \(O(ND+N\log N)\); при фиксированном \(D=250\) это вполне практично.
Реализация на C++ сначала устанавливает dp[0]=1. Затем для каждого \(i\) от \(1\) до limit вычисляется residue = powmod_int(i, i, divisor), массив dp копируется в next, после чего в next добавляются все переходы, соответствующие включению текущего элемента. Затем массивы меняются местами. После завершения цикла значение dp[0] равно числу всех подмножеств, сумма которых делится на \(250\), включая пустое, поэтому функция возвращает (dp[0] + modulo - 1) % modulo. Версии на Python и Java реализуют ту же самую рекурсию.
لننظر إلى المتتالية
$$a_i=i^i\qquad(1\le i\le N),$$
وفي المسألة الأصلية يكون \(N=250250\). المطلوب هو عدّ جميع المجموعات الجزئية غير الفارغة \(S\subseteq\{1,\dots,N\}\) التي تحقق
$$\sum_{i\in S} a_i \equiv 0 \pmod{250},$$
مع إعطاء النتيجة بترديد
$$M=10^{16}.$$
البحث المباشر غير ممكن لأن عدد المجموعات الجزئية يساوي \(2^N-1\). الفكرة الأساسية هي أن قابلية القسمة على \(250\) تعتمد فقط على البواقي modulo \(250\)، لا على القيم الكاملة للأعداد \(i^i\).
لنعرّف
$$r_i=a_i\bmod 250=i^i\bmod 250.$$
عندئذٍ لأي مجموعة جزئية \(S\) لدينا
$$\sum_{i\in S} a_i \equiv \sum_{i\in S} r_i \pmod{250}.$$
إذن تتحول المسألة الأصلية إلى عدّ المجموعات الجزئية التي يكون مجموع بواقيها مساويًا للصفر modulo \(250\).
لأن خاصية التطابق
$$x\equiv y\pmod{250}\quad\Longrightarrow\quad x+z\equiv y+z\pmod{250}$$
تعني أن قابلية قسمة المجموع على \(250\) تتحدد فقط من فئة كل حد في \(\mathbb{Z}/250\mathbb{Z}\). لذلك لا نحتاج إلى بناء الأعداد الضخمة \(i^i\) نفسها، بل يكفي العمل مع 250 باقيًا ممكنًا فقط.
لكل \(k=0,1,\dots,N\) نعرّف
$$dp_k(t)=\#\left\{S\subseteq\{1,\dots,k\}:\sum_{i\in S} r_i\equiv t\pmod{250}\right\}.$$
وعندها تكون القيمة المطلوبة هي \(dp_N(0)-1\)، لأن \(dp_N(0)\) يشمل المجموعة الفارغة أيضًا.
قبل معالجة أي عنصر يوجد بالضبط مجموعة جزئية واحدة من \(\{1,\dots,0\}\)، وهي المجموعة الفارغة، ومجموعها يساوي \(0\). لذا
$$dp_0(0)=1,\qquad dp_0(t)=0\quad(1\le t\le 249).$$
عند معالجة الباقي \(r_k\)، يملك كل اختيار سابق حالتين:
1. عدم أخذ العنصر \(k\): يبقى الباقي كما هو.
2. أخذ العنصر \(k\): ينتقل الباقي بمقدار \(r_k\) modulo \(250\).
ومن ثم نحصل على
$$dp_k(t)=dp_{k-1}(t)+dp_{k-1}(t-r_k)\pmod{M},$$
حيث يُفهم \(t-r_k\) بترديد \(250\).
ينفذ الكود الصيغة نفسها باستخدام مصفوفة مؤقتة next:
$$next[t]=dp[t],$$
$$next[(t+r_k)\bmod 250]\leftarrow next[(t+r_k)\bmod 250]+dp[t]\pmod{M}.$$
استخدام مصفوفة ثانية مهم جدًا، لأنه يضمن سلوك 0/1 الصحيح. أما التحديث في المكان نفسه فسيجعل الحالات الجديدة تُستخدم مرة أخرى في الدورة ذاتها، وكأن العنصر نفسه اختير أكثر من مرة.
يمكن كتابة الفكرة نفسها على شكل جداء كثيرات حدود modulo \(x^{250}-1\):
$$F_N(x)=\prod_{i=1}^{N}\left(1+x^{r_i}\right)\pmod{x^{250}-1}.$$
معامل \(x^t\) في \(F_N(x)\) يساوي عدد المجموعات الجزئية التي يكون مجموع بواقيها \(t\) modulo \(250\). أي إن البرمجة الديناميكية هي في الحقيقة تحديث لمعاملات هذا الجداء.
يستخدم الكود الرفع السريع لحساب
$$r_i=i^i\bmod 250$$
في زمن \(O(\log i)\). وتعتمد الطريقة على العلاقتين
$$b^{2m}\equiv (b^2)^m\pmod{250},\qquad b^{2m+1}\equiv b\cdot (b^2)^m\pmod{250}.$$
وبما أن الاختزال modulo \(250\) يتم بعد كل عملية ضرب، تبقى القيم الوسيطة صغيرة دائمًا.
عندما \(N=10\) تكون البواقي
$$1^1,2^2,\dots,10^{10}\equiv 1,4,27,6,125,156,43,216,239,0 \pmod{250}.$$
التحقق الموجود في الكود يقول إن الجواب يساوي \(5\). وبالفعل فإن المجموعات الجزئية غير الفارغة الموافقة هي:
$$\{1,3,4,8\},\qquad \{1,2,4,9\},\qquad \{10\},$$
$$\{1,3,4,8,10\},\qquad \{1,2,4,9,10\}.$$
فعلى سبيل المثال
$$1^1+3^3+4^4+8^8\equiv 1+27+6+216=250\equiv 0\pmod{250}.$$
وبما أن \(10^{10}\equiv 0\pmod{250}\)، فإن إضافة الحد العاشر لا تغيّر قابلية القسمة. لذلك يوجد بالضبط \(5\) مجموعات صحيحة.
لأن البرمجة الديناميكية تبدأ من المجموعة الفارغة، فإن \(dp_N(0)\) يحسب كل المجموعات ذات الباقي \(0\)، بما فيها
$$S=\varnothing.$$
وبما أن المسألة تطلب المجموعات غير الفارغة فقط، فالإجابة النهائية هي
$$\boxed{(dp_N(0)-1)\bmod M.}$$
هناك \(N\) خطوة، وفي كل خطوة تُحدَّث جميع فئات البواقي وعددها 250. لذلك كلفة البرمجة الديناميكية هي
$$O(N\cdot 250)=O(ND).$$
أما الذاكرة فهي \(O(250)\) فقط، لأننا نحتفظ بصفّين لا أكثر. ويضيف الرفع السريع \(O(\log i)\) لكل حد، ومن ثم فالكلفة الكلية هي \(O(ND+N\log N)\)، وهي عملية جدًا عندما يكون \(D=250\) ثابتًا.
تبدأ نسخة C++ بتعيين dp[0]=1 وباقي الحالات إلى الصفر. ثم لكل \(i\) من \(1\) إلى limit تحسب powmod_int(i, i, divisor) للحصول على الباقي \(r_i\)، وتنسخ dp إلى next، ثم تضيف انتقالات حالة “أخذ العنصر” إلى جميع البواقي الهدف، وبعد ذلك تبدّل المصفوفتين. بعد انتهاء الحلقة تصبح dp[0] مساوية لعدد جميع المجموعات الجزئية التي يكون مجموعها قابلًا للقسمة على \(250\) مع احتساب المجموعة الفارغة، ولذلك يعيد الكود (dp[0] + modulo - 1) % modulo. وتطبق نسختا Python وJava العودية نفسها.