题目描述
快速求出下面式子的值：
\[\left(\sum\limits_{k=1}^{N}k^{x}x^{k}\right)\bmod M
\]
其中 \(1 ≤ N, M ≤ 2\times 10^9\), 并且 \(1 ≤ x ≤ 50\)。
题解 (solution)
对于该类题目，\(N\) 很大，而 \(x\) 很小，考虑矩阵快速幂优化。
对于每一个 \(N\) 的答案，我们用 \(f(N)\) 来表示，于是有（忽略取模运算）：
\[f(n+1)=f(n)+(n+1)^{x}x^{n+1}
\]
因为 \(x\) 很小，而我们所希望的递推式是不包含项数的，所以把 \((n+1)^{x}\) 用二项式定理暴力拆开，于是有：
\[f(n+1)=f(n)+x\sum\limits_{i=0}^{x}\binom{x}{i}n^{i}x^{n}
\]
所以最后答案为：
\[\begin{align}
f(n)&=x\sum\limits_{i=1}^{n}{\sum\limits_{j=0}^{x}\binom{x}{j}(i-1)^{j}x^{i-1}}\\
&=x\sum\limits_{i=0}^{n-1}{\sum\limits_{j=0}^{x}\binom{x}{j}i^{j}x^{i}}\\
&=x\sum\limits_{i=0}^{x}{\binom{x}{i}\sum\limits_{j=0}^{n-1}j^{i}x^{j}}
\end{align}
\]
观察到式子后面一坨与原式相似，于是定义 \(g(n,y)\) 表示 \(\sum\limits_{i=1}^{n}i^{y}x^{i}\)，则递推式为
\[g(n,y)=x\sum\limits_{i=0}^{y}\binom{y}{i}(g(n-1,i)+[i=0])
\]
直接矩阵快速幂求出 \(g(n,x)\) 即可。