这个技巧是我打 dmy 选拔时 zxf 告诉我的，由于笔者找不到记录这个 trick 的文章，因此本文将其称之为“分治求和法”。
分治求和法的主要功能，是在
O ( log n ) O(\log n) O ( log n ) 内解决一类形如
∑ i = 1 n f i x i \sum \limits_{i=1}^n f_i x^i i = 1 ∑ n f i x i 的求和问题，常见如等比数列，等差比数列等。
对于等比数列求和，通常我们可以直接套用公式，但那样往往需要模数下的逆元。如果题目给定的模数不是质数，就无法直接使用公式。而分治求和法则完全不依赖逆元，支持任意模数。
等比数列和 考虑等比数列和
S ( n ) = ∑ i = 1 n x i S(n)=\sum_{i=1}^{n} x^i S ( n ) = i = 1 ∑ n x i S ( n ) = ∑ i = 1 n x i = x n + ∑ i = 1 n − 1 x i = x n + S ( n − 1 ) \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} S ( n ) = i = 1 ∑ n x i = x n + i = 1 ∑ n − 1 x i = x n + S ( n − 1 ) S ( n ) = ∑ i = 1 n x i = ∑ i = 1 n / 2 x i + ∑ i = n / 2 + 1 n x i = S ( n / 2 ) + x n / 2 ∑ i = 1 n / 2 x i = ( 1 + x n / 2 ) S ( n / 2 ) \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} S ( n ) = i = 1 ∑ n x i = i = 1 ∑ n /2 x i + i = n /2 + 1 ∑ n x i = S ( n /2 ) + x n /2 i = 1 ∑ n /2 x i = ( 1 + x n /2 ) S ( n /2 ) 递归分治即可，复杂度
O ( log 2 n ) O(\log^2 n) O ( log 2 n ) 。
求
∑ i = 0 k A i \sum_{i=0}^k A^i i = 0 ∑ k A i n ≤ 30 , k ≤ 10 9 n \le 30, k\le 10^9 n ≤ 30 , k ≤ 1 0 9 。1 秒，512 MB。
直接套上分治求和即可。
高次项求和 相信你已经理解了分治求和法的基本思想，来看看下面的扩展：
求
S n ( k ) = ∑ i = 1 k i n x i S_{n}(k)=\sum_{i=1}^k i^n x^i S n ( k ) = i = 1 ∑ k i n x i n ≤ 2000 n \le 2000 n ≤ 2000 ，
k ≤ 10 18 k \le 10^{18} k ≤ 1 0 18 ，1 秒，512 MB。
本来我打算把这个题放到入校测试 T2 的。结果 hwh 告诉我原了，我过了以后发现没有用分治求和做的（
当 k k k
S n ( k ) = ∑ i = 1 k i n x i = x + ∑ i = 2 k i n x i = x + x ∑ i = 1 k − 1 ( i + 1 ) n x i = x + x ∑ i = 1 k − 1 x i ∑ j = 0 n ( n j ) i j = x + x ∑ j = 0 n ( n j ) ∑ i = 1 k − 1 i j x i = x + x ∑ j = 0 n ( n j ) S j ( k − 1 ) \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} S n ( k ) = i = 1 ∑ k i n x i = x + i = 2 ∑ k i n x i = x + x i = 1 ∑ k − 1 ( i + 1 ) n x i = x + x i = 1 ∑ k − 1 x i j = 0 ∑ n ( j n ) i j = x + x j = 0 ∑ n ( j n ) i = 1 ∑ k − 1 i j x i = x + x j = 0 ∑ n ( j n ) S j ( k − 1 )
当 k k k
S n ( k ) = ∑ i = 1 k i n x i = ∑ i = 1 k / 2 i n x i + ∑ i = k / 2 + 1 k i n x i = S n ( k / 2 ) + x k / 2 ∑ i = 1 k / 2 ( i + k / 2 ) n x i = S n ( k / 2 ) + x k / 2 ∑ i = 1 k / 2 x i ∑ j = 0 n ( n j ) i j ( k / 2 ) n − j = S n ( k / 2 ) + x k / 2 ∑ j = 0 n ( n j ) ( k / 2 ) n − j ∑ i = 1 k / 2 i j x i = S n ( k / 2 ) + x k / 2 + ∑ j = 0 n ( n j ) ( k / 2 ) n − j S j ( k / 2 ) \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} S n ( k ) = i = 1 ∑ k i n x i = i = 1 ∑ k /2 i n x i + i = k /2 + 1 ∑ k i n x i = S n ( k /2 ) + x k /2 i = 1 ∑ k /2 ( i + k /2 ) n x i = S n ( k /2 ) + x k /2 i = 1 ∑ k /2 x i j = 0 ∑ n ( j n ) i j ( k /2 ) n − j = S n ( k /2 ) + x k /2 j = 0 ∑ n ( j n ) ( k /2 ) n − j i = 1 ∑ k /2 i j x i = S n ( k /2 ) + x k /2 + j = 0 ∑ n ( j n ) ( k /2 ) n − j S j ( k /2 ) 递归求解即可，边界为
k = 1 k=1 k = 1 ，此时
S n ( 1 ) = x S_n(1)=x S n ( 1 ) = x 。
注意 ：偶数情况中
( k / 2 ) n − j (k/2)^{n-j} ( k /2 ) n − j 不能对每个
j j j 单独快速幂计算，否则复杂度会退化为
O ( n 2 log 2 k ) O(n^2 \log^2 k) O ( n 2 log 2 k ) 。只需倒序枚举
j j j ，并维护
k / 2 k/2 k /2 的幂次，即可将复杂度优化至
O ( n 2 log k ) O(n^2 \log k) O ( n 2 log k ) 。
如果使用杨辉三角递推组合数，该做法支持任意模数。
CPP 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];
}
省流：求
S ( k ) = ∑ i = 1 k i 2 G i S(k)=\sum_{i=1}^k i^2 G^i S ( k ) = i = 1 ∑ k i 2 G i
套上上面的做法求出
S 2 S_2 S 2 ，你就秒了一个黑题。
求
C ( n ) = C ( n − 1 ) × 10 1 + ⌊ lg n ⌋ + n C(n)=C(n-1) \times 10^{1+ \left\lfloor \lg n\right\rfloor }+n C ( n ) = C ( n − 1 ) × 1 0 1 + ⌊ l g n ⌋ + n 特别地
C ( 1 ) = 1 C(1)=1 C ( 1 ) = 1 。对给出的模数取模。
n ≤ 10 18 n \le 10^{18} n ≤ 1 0 18 ，1 秒，512 MB。
定义函数
f ( l , r ) f(l,r) f ( l , r ) 表示将区间
[ l , r ] [l,r] [ l , r ] 中所有数字依次连接形成的数（
l l l 和
r r r 的位数相同）。
可以通过
O ( log n ) O(\log n) O ( log n ) 枚举位数得到
C ( n ) = ∑ f ( l , r ) C(n)=\sum f(l,r) C ( n ) = ∑ f ( l , r ) 。写出
f ( l , r ) f(l,r) f ( l , r ) 的解析式
f ( l , r ) = ∑ i = l r i × 10 r − i f(l,r)=\sum_{i=l}^r i \times 10^{r-i} f ( l , r ) = i = l ∑ r i × 1 0 r − i 仿照求解
S 1 ( r − l ) S_1(r-l) S 1 ( r − l ) 的方法即可求出
f ( l , r ) f(l,r) f ( l , r ) ，总时间复杂度
O ( log 3 n ) O(\log^3 n) O ( log 3 n ) 。
P10502 Matrix Power Series