CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== 序列求和V5学习及拓展 ======

首先膜鎕~~

问题很简单，求 $\sum_{i=1}^{n}i^{k}b^{i}$。原问题是对一个质数取模，这里我们拓展为对一个质数的幂 $p^{e}$ 取模。下面分为三类讨论：

<HTML><ul></HTML>
<HTML><li style="color:black"></HTML><HTML><p></HTML>若 $b\equiv0\pmod{p}$，那么我们至多只需要求前 $e$ 项即可。<HTML></p></HTML><HTML></li></HTML>
<HTML><li style="color:black"></HTML><HTML><p></HTML>若 $b\equiv1\pmod{p}$，设 $b=up+1$，那么原式等于 $$
\begin{aligned}
&\sum_{i=1}^{n}i^{k}(up+1)^{i}\\
=&\sum_{i=1}^{n}i^{k}\sum_{j=0}^{i}{i\choose j}(up)^{j}\\
=&\sum_{i=1}^{n}i^{k}\sum_{j=0}^{e-1}{i\choose j}(up)^{j}\\
=&\sum_{j=0}^{e-1}(up)^{j}\sum_{i=1}^{n}i^{k}{i\choose j}
\end{aligned}
$$ 注意到 ${i\choose j}$ 是一个关于 $i$ 的 $j$ 次多项式，因此上式是一个关于 $i$ 的 $k+e$ 次多项式。使用插值计算即可。时间复杂度 $\mathcal{O}(k+e+\log_{p}x)$。<HTML></p></HTML><HTML></li></HTML>
<HTML><li style="color:black"></HTML><HTML><p></HTML>其它情况（以下做法来源于[[http://www.51nod.com/onlineJudge/problemSolution.html#!problemId=1342|tls的题解]]）：<HTML></p></HTML>
<HTML><p></HTML>记所求式子为 $f(n)$。<HTML></p></HTML>
<HTML><p></HTML>首先我们证明：原式可被表示为 $f(n)=b^{n}F(n)-F(0)$，其中 $F$ 是关于 $n$ 的某个 $k$ 次多项式。<HTML></p></HTML>
<HTML><p></HTML>$k=0$ 时： $$
  \begin{aligned}
  f(n)&=\sum_{i=1}^{n}b^{i}\\
  &=\frac{b^{n+1}-b}{b-1}\\
  &=b^{n}\cdot\frac{b}{b-1}-\frac{b}{b-1}
  \end{aligned}
  $$ 显然成立。<HTML></p></HTML>
<HTML><p></HTML>$k\ge1$ 时： $$
  \begin{aligned}
  bf(n)-f(n)&=\sum_{i=1}^{n}i^{k}b^{i+1}-\sum_{i=1}^{n}i^{k}b^{i}\\
  &=n^{k}b^{n+1}+\sum_{i=1}^{n}b^{i}\left[(i-1)^{k}-i^{k}\right]\\
  &=n^{k}b^{n+1}+\sum_{j=0}^{k-1}(-1)^{j}{i\choose j}\sum_{i=1}^{n}i^{j}b^{i}\\
  &=n^{k}b^{n+1}+\sum_{j=0}^{k-1}(-1)^{j}{i\choose j}\left[b^{n}F_{j}(n)-F_{j}(0)\right]\\
  &=b^{n}\left(bn^{k}+\sum_{j=0}^{k-1}(-1)^{j}{i\choose j}F_{j}(n)\right)-\sum_{j=0}^{k-1}(-1)^{j}{i\choose j}F_{j}(0)
  \end{aligned}
  $$ 也成立。这意味着 $F_{k}(n)=bn^{k}+\sum_{j=0}^{k-1}(-1)^{j}{i\choose j}F_{j}(n)$。<HTML></p></HTML>

<HTML><p></HTML>现在我们只需要求出 $F(0),\cdots,F(k)$，即可插值求出 $f(n)$。设 $F(0)=x$，那么我们很容易用 $x$ 来表示 $F$：$F(n)=\frac{f(n)+x}{b^{n}}$。下面我们证明，$\sum_{i=0}^{k+1}(-1)^{i}{k+1\choose i}F(i)=0$ 对于任何 $k$ 次多项式都成立。这样我们就得到了一个一次方程，可以解出 $x$。<HTML></p></HTML>
<HTML><p></HTML>首先证明一个引理：对任意 $0\le j\le k$，$\sum_{i=0}^{k+1}(-1)^{i}{k+1\choose i}{i\choose j}=0$： $$
  \begin{aligned}
  &=\sum_{i=0}^{k+1}(-1)^{i}{k+1\choose j}{k+1-j\choose i-j}\\
  &={k+1\choose j}\sum_{i=0}^{k+1-j}(-1)^{i+j}{k+1-j\choose i}\\
  &=0
  \end{aligned}
  $$ 而 $F(i)$ 可以表示为 ${i\choose 0},{i\choose 1},\cdots,{i\choose k}$ 的线性组合，那么之前的结论是显然的。<HTML></p></HTML>
<HTML><p></HTML>另外注意到这个一次方程的未知数的系数是 $\sum_{i=0}^{k+1}(-1)^{i}{k+1\choose i}\left(\frac{1}{b}\right)^{i}=\left(\frac{b-1}{b}\right)^{k+1}$，而 $b$ 模 $p$ 不为 $0$ 或 $1$，因此这个方程是有唯一解的。<HTML></p></HTML>
<HTML><p></HTML>时间复杂度 $\mathcal{O}(k+\log_{p}x)$。<HTML></p></HTML><HTML></li></HTML><HTML></ul></HTML>

<del>时间复杂度不一定准确</del>
CVBB ACM Team

用户工具

站点工具

页面工具
