本题解是对 warzone 的题解的补充。
题意：求
\[\sum_{i=1}^n i^k a^i \]-
普通版：\(k\leq 2\times 10^3\)。
-
加强版：\(k\leq 10^7\)。
首先先考虑普通版。
\[\begin{aligned} \sum_{i=1}^n i^k a^i&=\sum_{i=1}^na^i\sum_{j=0}^k {k\brace j}i^{\underline{j}} \\ &=\sum_{j=0}^{k} {k\brace j}\sum_{i=1}^n a^ii^{\underline{j}} \\ &=\sum_{j=0}^{k} {k\brace j}{\sum}_1^{n+1}a^xx^{\underline{j}}\delta x \end{aligned} \]进行分类讨论。
- \(a=1\)
预处理 Stirling 数 \(\Theta(k^2)\) 或 \(\Theta(k\log k)\)，递推计算是 \(\Theta(k)\) 的。
- \(a\neq 1\)
我们有
\[\Delta uv=u\Delta v+\mathbf{E}v\Delta u \]两边同时求和，得
\[uv=\sum u\Delta v\delta x+\sum\mathbf{E}v\Delta u\delta x \]即
\[\sum u\Delta v\delta x=uv-\sum\mathbf{E}v\Delta u\delta x \]考虑求出 \(a^xx^{\underline{j}}\) 的“原和式”（不定和式）。我们不妨令 \(u=a^x\)，\(\Delta v=x^{\underline{j}}\)（则 \(v=\dfrac{x^{\underline{j+1}}}{j+1}\)）
于是 \(\sum a^xx^j\delta x=\dfrac{a^xx^{\underline{j+1}}}{j+1}-\sum (x+1)^{\underline{j}}(a-1)a^x\delta x\)
好像不可做。如果令 \(u=x^{\underline{j}}\)，\(\Delta v=a^x\)（则 \(v=\dfrac{a^x}{a-1}\)）呢？
代入得到
\(\sum a^xx^j\delta x=\dfrac{a^xx^{\underline{j}}}{a-1}-\sum \dfrac{a^{x+1}}{a-1}jx^{\underline{j-1}}\delta x\)
也就是说
\[{\sum}_0^{n+1} a^xx^j=\frac{a^xx^j}{a-1}\bigg|_{0}^{n+1}-\frac{j\cdot a}{a-1}{\sum}_0^{n+1} a^xx^{\underline{j-1}}\delta x \]边界为 \(j=0\) 时，\(\sum a^xx^j\delta x=\sum a^x\delta x=\dfrac{a^x}{a-1}\)。
预处理 \(\Theta(k^2)\) 或 \(\Theta(k\log k)\)，递推计算是 \(\Theta(k)\) 的。
综上，我们在 \(\Theta(k^2)\) 或 \(\Theta(k\log k)\) 的复杂度内解决了普通版。
那么我们考虑加强版。
考虑 \(a=1\)，其实就是 CF622F。但是本题中 \(k\leq 10^7\)，直接计算每一个数的 \(k\) 次幂可能会寄。
但是我们知道，\(n\) 个数中有 \(\Theta(\dfrac{n}{\ln n})\) 个素数。考虑到 \(\operatorname{Id}^k\) 是一个完全积性函数，于是我们只在素数处计算其 \(k\) 次幂，然后在线性筛时顺便推出其他数的幂即可，这样时间复杂度是 \(\Theta(\dfrac{k\log k}{\ln k})=\Theta(k)\) 的。
以下默认 \(a\neq 1\)。
设 \(\displaystyle f(n)={\sum}_0^n x^ka^x\delta x\)，答案即为 \(f(n+1)-f(1)\)。
注意到在普通版中我们有
\[\begin{aligned} \sum a^xx^k\delta x&=\dfrac{\textcolor{red}{a^x}x^{\underline{k}}}{a-1}-\frac{a\cdot k}{a-1}\textcolor{red}{a^{x}}\sum x^{\underline{k-1}}\delta x \\ &=a^x\left(\frac{x^{\underline{k}}}{a-1}-\frac{a\cdot k}{a-1}\sum x^{\underline{k-1}}\right) \end{aligned} \]\(a^x\) 右边的那一包东西显然是一个 \(k\) 次多项式，不妨设为 \(g(x)\)。则我们有
\[{\sum}_l^r a^xx^k\delta x=a^rg(r)-a^lg(l) \]则
\[f(n)=a^ng(n)-a^0g(0) \]如果我们能知道 \(g(0),g(1),\cdots,g(n)\) 的点值，就不难应用 Lagrange 插值法在 \(\Theta(k)\) 内求出 \(g(n+1)\)。那么问题转化为如何求 \(g(0),g(1),\cdots,g(n)\)。
我们考虑到
\[f(n)=a^ng(n)-a^0g(0) \]即
\[g(n)=\frac{f(n)+g(0)}{a^{n}} \]\(f(0),f(1),\cdots,f(k)\) 可以 \(\Theta(k)\) 递推。那么现在的当务之急就是求出 \(g(0)\) 了。
我们知道 \(\deg g=k\)，这意味着 \(\Delta^{k+1} g=0\)。
于是
\[\sum_{i=0}^{k+1}{k+1\choose i}(-1)^{k+1-i}\mathbf{E}^{i}g(0)=0 \]\[\sum_{i=0}^{k+1}{k+1\choose i}(-1)^{k+1-i}g(i)=0 \]\[\sum_{i=0}^{k+1}{k+1\choose i}(-1)^{k+1-i}a^{-i}[f(i)+g(0)]=0 \]\[\sum_{i=0}^{k+1}{k+1\choose i}(-1)^{k+1-i}a^{-i}f(i)+\sum_{i=0}^{k+1}{k+1\choose i}(-1)^{k+1-i}a^{-i}g(0)=0 \]\[\sum_{i=0}^{k+1}{k+1\choose i}(-1)^{k+1-i}a^{-i}f(i)+(a^{-1}-1)^{k+1}g(0)=0 \]\[g(0)=-(a^{-1}-1)^{-(k+1)}\sum_{i=0}^{k+1}{k+1\choose i}(-1)^{k+1-i}a^{-i}f(i) \]不难 \(\Theta(k)\) 求出。综上我们在 \(\Theta(k)\) 的时间复杂度内解决了本题。
答案即为 \(a^{n+1}g(n+1)-a\cdot g(1)\)
顺便讲一下如何 \(\Theta(k)\) 插值。
注意到我们只需要算 \(g(n+1)\)。
我们有
\[g(n+1)=\sum_{i=0}^{k}g(i)\frac{\prod_{j\neq i}(n+1-j)}{\prod_{j\neq i}(i-j)}\]分母就是
\[i(i-1)\cdots 2\cdot 1\cdot (-1)\cdot (-2)\cdots (i-k) \]即为
\[(-1)^{k-i}i!(k-i)! \]分子就是
\[\frac{(n+1-0)(n+1-1)\cdots(n+1-k)}{n+1-i} \]所以分式即为
\[(-1)^{k-i}\frac{(n+1-0)(n+1-1)\cdots(n+1-k)}{(n+1-i)i!(k-i)!} \]可以前后缀预处理做到严格 \(\Theta(k)\)。
标签：数列,求和,题解,sum,Delta,xx,delta,Theta,underline From： https://www.cnblogs.com/Starrykiller/p/18009867/sol-p5904-p4948