Problem 250: 250250

Mathematical Foundation

Theorem 1 (Residue reduction). For divisibility of a sum by $250$, only the residues $r_i = i^i \bmod 250$ matter. That is, a subset $T \subseteq \{1, \ldots, 250250\}$ has $\sum_{i \in T} i^i \equiv 0 \pmod{250}$ if and only if $\sum_{i \in T} r_i \equiv 0 \pmod{250}$.

Proof. For any integers $a_i$, $\sum a_i \equiv \sum (a_i \bmod m) \pmod{m}$. Apply with $m = 250$ and $a_i = i^i$. $\square$

Theorem 2 (DP on residue classes). Let $dp[j]$ denote the number of subsets (including the empty set) of $\{1^1, \ldots, N^N\}$ whose element sum is congruent to $j \pmod{250}$, reduced modulo $M = 10^{16}$. The recurrence

processed for $i = 1, 2, \ldots, N$ correctly computes $dp[j]$ for all $0 \le j < 250$.

Proof. Induction on the number of elements processed. Initially, $dp[0] = 1$ (empty set), $dp[j] = 0$ for $j \ne 0$.

For element $i$ with residue $r_i$: every subset of $\{1, \ldots, i\}$ either excludes $i$ (counted by old $dp[j]$) or includes $i$ (counted by old $dp[(j - r_i) \bmod 250]$, since including $i$ adds $r_i$ to the residue). We must update all 250 entries simultaneously (using a temporary copy or in-place with a fresh array) to avoid double-counting.

By induction, after processing all $N$ elements, $dp[j]$ equals (mod $M$) the number of subsets with sum $\equiv j \pmod{250}$. $\square$

Lemma 1 (Periodicity of residues). The sequence $r_i = i^i \bmod 250$ has period dividing $500$.

Proof. By CRT, $250 = 2 \times 125$. We show periodicity modulo each factor:

• Mod 2: $i^i \bmod 2$ depends only on $i \bmod 2$, period 2.
• Mod 125: Write $i = 125q + r$. For $\gcd(i, 125) = 1$, $i^i \bmod 125$ depends on $i \bmod 125$ (for the base) and $i \bmod \varphi(125) = i \bmod 100$ (for the exponent). Since $\text{lcm}(125, 100) = 500$, the period divides 500. For $5 \mid i$, similar analysis via lifting-the-exponent gives the same bound.
• Combined: $\text{lcm}(2, 500) = 500$. $\square$

Theorem 3 (Final answer). The number of non-empty subsets with sum divisible by 250 is

where $dp[0]$ counts all subsets (including empty) with sum $\equiv 0$.

Proof. $dp[0]$ includes the empty subset, which has sum 0. Subtracting 1 excludes it. $\square$

Editorial

.., 250250^250250} with sum divisible by 250. DP on residue classes mod 250. Answer mod 10^16. Key: Only need i^i mod 250 for each element. DP array of size 250. We use fast modular exponentiation. We then dP on residue classes. Finally, subtract empty subset.

Pseudocode

Compute residues r_i = i^i mod 250
Use fast modular exponentiation
DP on residue classes
Subtract empty subset

Complexity Analysis

• Time: $O(N \times 250) = O(250250 \times 250) \approx 6.25 \times 10^7$ modular additions. Computing $r_i$ takes $O(N \log N)$ via modular exponentiation ($O(\log i)$ per element). Total: $O(N \cdot 250)$ dominates.
• Space: $O(250)$ for the DP array.

Answer

#include <bits/stdc++.h>
using namespace std;

int main() {
    const long long MOD = 10000000000000000LL; // 10^16
    const int N = 250250;
    const int M = 250;

    vector<long long> dp(M, 0);
    dp[0] = 1;

    for (int i = 1; i <= N; i++) {
        // Compute i^i mod 250
        long long base = i % M;
        long long exp = i;
        long long r = 1;
        long long b = base;
        long long e = exp;
        while (e > 0) {
            if (e & 1) r = (r * b) % M;
            b = (b * b) % M;
            e >>= 1;
        }
        int ri = (int)r;

        // Update dp
        vector<long long> ndp(M);
        for (int j = 0; j < M; j++) {
            ndp[j] = (dp[j] + dp[((j - ri) % M + M) % M]) % MOD;
        }
        dp = ndp;
    }

    // Answer: dp[0] - 1 (exclude empty subset)
    long long answer = (dp[0] - 1 + MOD) % MOD;
    cout << answer << endl;
    return 0;
}

"""
Problem 250: 250250

Find non-empty subsets of {1^1, 2^2, ..., 250250^250250} with sum divisible by 250.
DP on residue classes mod 250. Answer mod 10^16.

Key: Only need i^i mod 250 for each element. DP array of size 250.
"""

def solve(N=250250, M=250, MOD=10**16):
    """DP on residues mod M. O(N * M) time."""
    dp = [0] * M
    dp[0] = 1
    for i in range(1, N + 1):
        ri = pow(i, i, M)
        ndp = dp.copy()
        for j in range(M):
            ndp[(j + ri) % M] = (ndp[(j + ri) % M] + dp[j]) % MOD
        dp = ndp
    return (dp[0] - 1) % MOD

def solve_brute(N=20, M=250):
    """Brute force for small N: enumerate all subsets."""
    residues = [pow(i, i, M) for i in range(1, N + 1)]
    count = 0
    for mask in range(1, 1 << N):
        s = sum(residues[i] for i in range(N) if mask & (1 << i))
        if s % M == 0:
            count += 1
    return count

# Cross-check
dp_small = solve(20, 250, 10**18)
bf_small = solve_brute(20, 250)
assert dp_small == bf_small, f"Mismatch: {dp_small} vs {bf_small}"

answer = solve()
assert answer == 1425480602091519, f"Expected 1425480602091519, got {answer}"
print(answer)