2020-2021:teams:intrepidsword:zhongzihao:sequence_sum_v5
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:intrepidsword:zhongzihao:sequence_sum_v5 [2020/06/15 02:00] admin 创建 |
2020-2021:teams:intrepidsword:zhongzihao:sequence_sum_v5 [2021/11/14 22:18] (当前版本) toxel |
||
|---|---|---|---|
| 行 6: | 行 6: | ||
| <HTML><ul></HTML> | <HTML><ul></HTML> | ||
| - | <HTML><li></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\equiv0\pmod{p}$，那么我们至多只需要求前 $e$ 项即可。<HTML></p></HTML><HTML></li></HTML> |
| - | <HTML><li></HTML><HTML><p></HTML>若 $b\equiv1\pmod{p}$，设 $b=up+1$，那么原式等于 $$ | + | <HTML><li style="color:black"></HTML><HTML><p></HTML>若 $b\equiv1\pmod{p}$，设 $b=up+1$，那么原式等于 $$ |
| \begin{aligned} | \begin{aligned} | ||
| &\sum_{i=1}^{n}i^{k}(up+1)^{i}\\ | &\sum_{i=1}^{n}i^{k}(up+1)^{i}\\ | ||
| 行 15: | 行 15: | ||
| \end{aligned} | \end{aligned} | ||
| $$ 注意到 ${i\choose j}$ 是一个关于 $i$ 的 $j$ 次多项式，因此上式是一个关于 $i$ 的 $k+e$ 次多项式。使用插值计算即可。时间复杂度 $\mathcal{O}(k+e+\log_{p}x)$。<HTML></p></HTML><HTML></li></HTML> | $$ 注意到 ${i\choose j}$ 是一个关于 $i$ 的 $j$ 次多项式，因此上式是一个关于 $i$ 的 $k+e$ 次多项式。使用插值计算即可。时间复杂度 $\mathcal{O}(k+e+\log_{p}x)$。<HTML></p></HTML><HTML></li></HTML> | ||
| - | <HTML><li></HTML><HTML><p></HTML>其它情况（以下做法来源于[[http://www.51nod.com/onlineJudge/problemSolution.html#!problemId=1342|tls的题解]]）：<HTML></p></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)$。<HTML></p></HTML> | ||
| <HTML><p></HTML>首先我们证明：原式可被表示为 $f(n)=b^{n}F(n)-F(0)$，其中 $F$ 是关于 $n$ 的某个 $k$ 次多项式。<HTML></p></HTML> | <HTML><p></HTML>首先我们证明：原式可被表示为 $f(n)=b^{n}F(n)-F(0)$，其中 $F$ 是关于 $n$ 的某个 $k$ 次多项式。<HTML></p></HTML> | ||
| 行 25: | 行 25: | ||
| \end{aligned} | \end{aligned} | ||
| $$ 显然成立。<HTML></p></HTML> | $$ 显然成立。<HTML></p></HTML> | ||
| - | <HTML><p></HTML>$k>1$ 时： $$ | + | <HTML><p></HTML>$k\ge1$ 时： $$ |
| \begin{aligned} | \begin{aligned} | ||
| bf(n)-f(n)&=\sum_{i=1}^{n}i^{k}b^{i+1}-\sum_{i=1}^{n}i^{k}b^{i}\\ | bf(n)-f(n)&=\sum_{i=1}^{n}i^{k}b^{i+1}-\sum_{i=1}^{n}i^{k}b^{i}\\ | ||
| 行 33: | 行 33: | ||
| &=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) | &=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} | \end{aligned} | ||
| - | $$ 也成立。<HTML></p></HTML> | + | $$ 也成立。这意味着 $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>现在我们只需要求出 $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$： $$ | <HTML><p></HTML>首先证明一个引理：对任意 $0\le j\le k$，$\sum_{i=0}^{k+1}(-1)^{i}{k+1\choose i}{i\choose j}=0$： $$ | ||
2020-2021/teams/intrepidsword/zhongzihao/sequence_sum_v5.1592157627.txt.gz · 最后更改: 2020/06/15 02:00 由 admin
