2020-2021:teams:legal_string:王智彪:常系数齐次线性递推
|
2020-2021:teams:legal_string:王智彪:常系数齐次线性递推 [2021/08/13 21:44] 王智彪 创建 |
2020-2021:teams:legal_string:王智彪:常系数齐次线性递推 [2021/08/13 21:44] (当前版本) 王智彪 |
||
|---|---|---|---|
| 行 11: | 行 11: | ||
| 比如求斐波那契数列的第五项 $fib_{5}$ ，于是我们相当于 $0x^{0}+0x^{1}+…+1x^{5}$。 | 比如求斐波那契数列的第五项 $fib_{5}$ ，于是我们相当于 $0x^{0}+0x^{1}+…+1x^{5}$。 | ||
| - | 我们先把 $x^{5}$ 的系数减一，再把 $x^{4}$ 和 $x_{3}$ 系数都加一，从而变成 $0x^{0}+0x^{1}+…+1x^{3}+1x^{4}+0x^{5}$ 。相当于对于 $x^{2}-x-1$ 取模。剩下依次类推。 | + | 我们先把 $x^{5}$ 的系数减一，再把 $x^{4}$ 和 $x^{3}$ 系数都加一，从而变成 $0x^{0}+0x^{1}+…+1x^{3}+1x^{4}+0x^{5}$ 。相当于对于 $x^{2}-x-1$ 取模。剩下依次类推。 |
| 于是原题相当于求出多项式 $x^{n}$ 对多项式 $x_{k}-p_{1}x_{k-1}-p_{2}x_{k-1}-…-p_{k}$ 取模。 | 于是原题相当于求出多项式 $x^{n}$ 对多项式 $x_{k}-p_{1}x_{k-1}-p_{2}x_{k-1}-…-p_{k}$ 取模。 | ||
2020-2021/teams/legal_string/王智彪/常系数齐次线性递推.1628862244.txt.gz · 最后更改: 2021/08/13 21:44 由 王智彪
