题解：自然幂和模 $2^{64}$

问题分析

我们需要计算：

$$S(m, n) = \sum_{k=0}^{n-1} k^m \pmod{2^{64}}$$

其中：

• $0 \le m \le 10^7$
• $1 \le n \le 10^{18}$
• 在 unsigned long long 自然溢出下计算

---

难点分析

1. $n$ 极大：$n$ 可达 $10^{18}$，不能直接枚举
2. $m$ 较大：$m$ 可达 $10^7$，需要高效算法
3. 模 $2^{64}$：可以利用数论性质优化

---

核心思路：伯努利数公式

自然幂和可以用伯努利数表示为：

$$\sum_{k=0}^{n-1} k^m = \frac{1}{m+1} \sum_{k=0}^m \binom{m+1}{k} B_k n^{m+1-k} $$

其中 $B_k$ 是伯努利数。

但在模 $2^{64}$ 下，除法需要特殊处理。

---

模 $2^{64}$ 的特殊性质

由于模数是 $2$ 的幂，我们需要考虑：

1. 除法的处理：在 $\bmod 2^{64}$ 下，奇数有逆元，偶数需要特殊处理
2. 伯努利数的 $2$-adic 性质：伯努利数 $B_k$ 在 $k \ge 1$ 且 $k$ 为奇数时，$B_k = 0$（除了 $B_1 = -\frac12$）
3. Von Staudt–Clausen 定理：$B_k + \sum_{p-1|k} \frac1p$ 是整数

---

算法设计

方法：利用多项式插值

对于固定的 $m$，$S(m, n)$ 是关于 $n$ 的 $m+1$ 次多项式（当 $m \ge 1$）。

我们可以：

1. 计算 $S(m, 0), S(m, 1), \dots, S(m, m+1)$
2. 使用拉格朗日插值得到多项式
3. 代入 $n$ 计算答案

但 $m$ 可达 $10^7$，直接插值不可行。

---

正解：利用 $2$-adic 分析

在模 $2^{64}$ 下，有重要性质：

定理：当 $m \ge 1$ 时，$S(m, n)$ 可以表示为：

$$S(m, n) = \frac{n^{m+1}}{m+1} + \frac{n^m}{2} + \sum_{k=1}^{\lfloor m/2 \rfloor} \frac{B_{2k}}{2k} \binom{m}{2k-1} n^{m-2k+1} $$

其中 $B_{2k}$ 是伯努利数。

由于我们工作在模 $2^{64}$ 下，只需要计算有限项。

---

关键优化

1. 项数有限：当 $2k > \nu_2(m!) + 63$ 时（$\nu_2$ 是 $2$-adic 估值），后面的项模 $2^{64}$ 为 $0$
2. 伯努利数计算：只需要计算前 $O(\log m)$ 个伯努利数
3. 组合数计算：利用质因数分解和勒让德公式

---

具体算法步骤

步骤1：预处理阶乘的 $2$-adic 估值

使用勒让德公式：

$$\nu_2(m!) = m - s_2(m)$$

其中 $s_2(m)$ 是 $m$ 的二进制表示中 $1$ 的个数。

步骤2：确定求和上界

我们需要找到最大的 $K$ 使得对任意 $k \le K$：

$$\nu_2\left(\frac{B_{2k}}{2k} \binom{m}{2k-1} n^{m-2k+1}\right) < 64 $$

实际上，$K \le 32$ 就足够了（因为 $2^{32}$ 已经很大）。

步骤3：计算伯努利数模 $2^{64}$

使用递归公式：

$$\sum_{k=0}^m \binom{m+1}{k} B_k = 0$$

从 $B_0 = 1$ 开始计算。

注意在模 $2^{64}$ 下，$B_1 = -1/2$ 需要特殊处理（即 $2^{63} \cdot (2^{64}-1)$）。

步骤4：计算答案

对于 $m = 0$：$S(0, n) = n$

对于 $m \ge 1$：

uint64_t ans = 0;
// 第一项：n^(m+1)/(m+1)
// 第二项：n^m/2  
// 其余项：求和
for k in 1 to min(K, m/2):
    term = B[2k] * binom(m, 2k-1) * power(n, m-2k+1) / (2k)
    ans += term

---

实现细节

1. 大数幂模 $2^{64}$

使用快速幂，由于自然溢出，直接乘即可。

2. 组合数模 $2^{64}$

需要处理分母的 $2$ 的因子：

uint64_t binom(uint64_t n, uint64_t k) {
    if (k < 0 || k > n) return 0;
    // 计算 C(n,k) 模 2^64，考虑2的因子
    uint64_t res = 1;
    int cnt2 = 0;
    for (uint64_t i = 1; i <= k; i++) {
        uint64_t num = n - k + i;
        uint64_t den = i;
        // 提取2的因子
        while (num % 2 == 0) {
            num /= 2;
            cnt2++;
        }
        while (den % 2 == 0) {
            den /= 2;
            cnt2--;
        }
        res = res * num * inv(den);  // inv(den) 是模2^64逆元
    }
    res = res * (1ULL << cnt2);  // 补回2的因子
    return res;
}

3. 伯努利数计算

vector<uint64_t> B(m+2);
B[0] = 1;
for (int i = 1; i <= m+1; i++) {
    uint64_t sum = 0;
    for (int j = 0; j < i; j++) {
        sum += binom(i+1, j) * B[j];
    }
    B[i] = -sum * inv(i+1);  // 需要处理2的因子
}

---

复杂度分析

• 伯努利数计算：$O(m^2)$ 但只需要前 $O(\log m)$ 项
• 组合数计算：$O(K)$，$K \le 32$
• 总复杂度：$O(m + K^2)$，在 $m \le 10^7$ 时可行

---

样例验证

样例1：$m=5, n=3$

$$S = 0^5 + 1^5 + 2^5 = 0 + 1 + 32 = 33$$

样例2：$m=10, n=5$

$$S = 0^{10} + 1^{10} + 2^{10} + 3^{10} + 4^{10} = 0 + 1 + 1024 + 59049 + 1048576 = 1108650 $$

与题目输出一致。

---

代码框架

#include <iostream>
#include <vector>
using namespace std;

typedef unsigned long long ull;

// 快速幂模2^64
ull pow_mod(ull a, ull b) {
    ull res = 1;
    while (b) {
        if (b & 1) res *= a;
        a *= a;
        b >>= 1;
    }
    return res;
}

// 计算逆元（针对奇数）
ull inv(ull x) {
    // 使用扩展欧几里得或牛顿迭代
    // 这里简化为：x^(2^63-1) mod 2^64 对于奇数x
    ull res = 1;
    for (int i = 0; i < 63; i++) {
        if ((1ULL << i) & ( (1ULL << 63) - 1)) {
            res *= x;
        }
        x *= x;
    }
    return res;
}

int main() {
    ull m, n;
    cin >> m >> n;
    
    if (m == 0) {
        cout << n << endl;
        return 0;
    }
    
    // 计算伯努利数（前K项）
    int K = min(32, (int)m/2);
    vector<ull> B(K+1);
    // ... 实现伯努利数计算
    
    ull ans = 0;
    // 实现求和公式
    // ...
    
    cout << ans << endl;
    return 0;
}

---

总结

本题的关键在于：

1. 理解模 $2^{64}$ 下的特殊数论性质
2. 利用伯努利数公式但只计算有效项
3. 处理 $2$-adic 估值和除法
4. 优化组合数和幂的计算

这是一个数论+组合数学的难题，考察对特殊模数下计算技巧的掌握。