2020-2021:teams:intrepidsword:zhongzihao:sequence_sum_v5
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:intrepidsword:zhongzihao:sequence_sum_v5 [2021/11/14 22:12] toxel fix |
2020-2021:teams:intrepidsword:zhongzihao:sequence_sum_v5 [2021/11/14 22:18] (当前版本) toxel |
||
|---|---|---|---|
| 行 17: | 行 17: | ||
| <HTML><li style="color:black"></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+1$ 次多项式。<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$ 时： $$ | <HTML><p></HTML>$k=0$ 时： $$ | ||
| \begin{aligned} | \begin{aligned} | ||
| 行 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.1636899139.txt.gz · 最后更改: 2021/11/14 22:12 由 toxel
