浅谈分治求和法

· · 算法·理论

这个技巧是我打 dmy 选拔时 zxf 告诉我的，由于笔者找不到记录这个 trick 的文章，因此本文将其称之为“分治求和法”。

分治求和法的主要功能，是在 O(\log n) 内解决一类形如 \sum \limits_{i=1}^n f_i x^i 的求和问题，常见如等比数列，等差比数列等。

对于等比数列求和，通常我们可以直接套用公式，但那样往往需要模数下的逆元。如果题目给定的模数不是质数，就无法直接使用公式。而分治求和法则完全不依赖逆元，支持任意模数。

等比数列和

考虑等比数列和

S(n)=\sum_{i=1}^{n} x^i

按 n 的奇偶性进行讨论：

\begin{aligned} S(n)&=\sum_{i=1}^{n} x^i\\ &=x^n+\sum_{i=1}^{n-1} x^i\\ &=x^n+S(n-1) \end{aligned} \begin{aligned} S(n)&=\sum_{i=1}^{n} x^i\\ &=\sum_{i=1}^{n/2} x^i+\sum_{i=n/2+1}^{n} x^i\\ &=S(n/2)+x^{n/2} \sum_{i=1}^{n/2} x^i\\ &=\left(1+x^{n/2}\right) S(n/2) \end{aligned}

递归分治即可，复杂度 O(\log^2 n)。

P10502 Matrix Power Series

求

\sum_{i=0}^k A^i

其中 A 是一个矩阵。对给出的模数取模。

直接套上分治求和即可。

高次项求和

相信你已经理解了分治求和法的基本思想，来看看下面的扩展：

P4948 数列求和

求

S_{n}(k)=\sum_{i=1}^k i^n x^i

本来我打算把这个题放到入校测试 T2 的。结果 hwh 告诉我原了，我过了以后发现没有用分治求和做的（

仍按 k 的奇偶性进行讨论。

  1. 当 k 为奇数时，有
\begin{aligned} S_{n}(k)&=\sum_{i=1}^k i^n x^i\\ &=x +\sum_{i=2}^{k} i^n x^i\\ &=x+x\sum_{i=1}^{k-1} (i+1)^n x^i \\ &=x+x\sum_{i=1}^{k-1}x^i \sum_{j=0}^n \binom{n}{j} i^j\\ &=x+x\sum_{j=0}^n \binom{n}{j} \sum_{i=1}^{k-1} i^j x^i \\ &= x+x\sum_{j=0}^n \binom{n}{j} S_{j}(k-1) \end{aligned}
  1. 当 k 为偶数时，有
\begin{aligned} S_{n}(k)&=\sum_{i=1}^k i^n x^i\\ &=\sum_{i=1}^{k/2} i^n x^i+\sum_{i=k/2+1}^{k} i^n x^i \\ &=S_n(k/2)+x^{k/2} \sum_{i=1}^{k/2} (i+k/2)^n x^i\\ &=S_n(k/2)+x^{k/2} \sum_{i=1}^{k/2} x^i \sum_{j=0}^n \binom{n}{j} i^j (k/2)^{n-j}\\ &=S_n(k/2)+x^{k/2} \sum_{j=0}^n \binom{n}{j} (k/2)^{n-j}\sum_{i=1}^{k/2} i^j x^i \\ &=S_n(k/2)+x^{k/2} + \sum_{j=0}^n \binom{n}{j} (k/2)^{n-j} S_j(k/2) \end{aligned}

递归求解即可，边界为 k=1，此时 S_n(1)=x。

注意：偶数情况中 (k/2)^{n-j} 不能对每个 j 单独快速幂计算，否则复杂度会退化为 O(n^2 \log^2 k)。只需倒序枚举 j，并维护 k/2 的幂次，即可将复杂度优化至 O(n^2 \log k)。

如果使用杨辉三角递推组合数，该做法支持任意模数。

constexpr int N = 2005;

long long n, k;
mint x, c[N][N];

void prework() {
    for (int i = 0; i <= n; i++) c[i][0] = c[i][i] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
    }
}

vector<mint> solve(long long k) {
    if (k == 1) return vector<mint>(n + 1, x);
    vector<mint> S(n + 1);
    if (k & 1) {
        auto T = solve(k - 1);
        for (int i = 0; i <= n; i++) {
            mint cur = 0;
            for (int j = 0; j <= i; j++) cur += c[i][j] * T[j];
            S[i] = x + x * cur;
        }
        return S;
    } else {
        auto T = solve(k >> 1);
        mint p = x.pow(k >> 1);
        for (int i = 0; i <= n; i++) {
            mint cur = 0, b = k >> 1, pw = 1;
            for (int j = i; j >= 0; j--, pw *= b) cur += c[i][j] * T[j] * pw;
            S[i] = T[i] + p * cur;
        }
        return S;
    }
}

void _main() {
    cin >> k >> x >> n;
    prework();
    auto S = solve(k);
    cout << S[n];
}

P4102 [HEOI2014] 林中路径

省流：求

S(k)=\sum_{i=1}^k i^2 G^i

其中 G 为邻接矩阵。

套上上面的做法求出 S_2，你就秒了一个黑题。

P3216 [HNOI2011] 数学作业

求

C(n)=C(n-1) \times 10^{1+ \left\lfloor \lg n\right\rfloor }+n

特别地 C(1)=1。对给出的模数取模。

定义函数 f(l,r) 表示将区间 [l,r] 中所有数字依次连接形成的数（l 和 r 的位数相同）。

可以通过 O(\log n) 枚举位数得到 C(n)=\sum f(l,r)。写出 f(l,r) 的解析式

f(l,r)=\sum_{i=l}^r i \times 10^{r-i}

仿照求解 S_1(r-l) 的方法即可求出 f(l,r)，总时间复杂度 O(\log^3 n)。