Exqule Forever

Nothing with me, but Forever.

二阶常系数齐次线性递推

发布于 2020-07-05 | 分类于 数学 、 生成函数 、 常系数齐次线性递推 | 9分钟 | 1562字数 | 浏览量：

二阶常系数齐次线性递推

题意

给定一个序列的线性递推式：

fn={a⋅fn−1+b⋅fn−2,n≥2f1,n=1f0,n=0f_n= \begin{cases} a\cdot f_{n-1}+b\cdot f_{n-2}&, & n\geq2 \\ f_1 & , & n=1 \\ f_0 & , & n=0 \end{cases}

多组询问，给定 n,a,b,f0,f1n,a,b,f_0,f_1，求 fnf_n 的值。

解法

毒瘤出题人的做法就是一个矩阵光速幂。

这里考虑一个通项公式\生成函数的做法：

由 fn=a⋅fn−1+b⋅fn−2f_n=a\cdot f_{n-1}+b\cdot f_{n-2} 移项得到：fn−a⋅fn−1−b⋅fn−2=0f_n-a\cdot f_{n-1}-b\cdot f_{n-2}=0。

令 g(x)=∑k=0∞fk⋅xkg(x)=\sum_{k=0}^{\infty}f_k\cdot x^k 的生成函数，那么易知：

g(x)=f0+f1⋅x1+f2⋅x2+f3⋅x3⋯a⋅x⋅g(x)=a⋅f0⋅x1+a⋅f1⋅x2+a⋅f2⋅x3+⋯b⋅x2⋅g(x)=b⋅f0⋅x2+b⋅f1⋅x3+b⋅f2⋅x4+⋯g(x)=f_0+f_1\cdot x^1+f_2\cdot x^2+f_3\cdot x^3\cdots \\ a\cdot x\cdot g(x)=a\cdot f_0\cdot x^1+ a\cdot f_1\cdot x^2+a\cdot f_2\cdot x^3+\cdots \\ b\cdot x^2\cdot g(x)=b\cdot f_0\cdot x^2+b\cdot f_1\cdot x^3+b\cdot f_2\cdot x^4+\cdots

按照套路推导，三式相加减易知：

(1−a⋅x−b⋅x2)⋅g(x)=f0+(f1−a⋅f0)⋅x+(f2−a⋅f1−b⋅f0)⋅x2+⋯(1-a\cdot x-b\cdot x^2)\cdot g(x)=f_0+(f_1-a\cdot f_0)\cdot x+(f_2-a\cdot f_1-b\cdot f_0)\cdot x^2+\cdots

观察易知对于 x2x^2 及其以后的项的系数都满足 fn−a⋅fn−1−b⋅fn−2=0f_n-a\cdot f_{n-1}-b\cdot f_{n-2}=0，那么原式可化为：

(1−a⋅x−b⋅x2)⋅g(x)=f0+(f1−a⋅f0)⋅xg(x)=f0+(f1−a⋅f0)⋅x1−a⋅x−b⋅x2(1-a\cdot x-b\cdot x^2)\cdot g(x)=f_0+(f_1-a\cdot f_0)\cdot x \\ g(x)=\frac{f_0+(f_1-a\cdot f_0)\cdot x}{1-a\cdot x-b\cdot x^2}

考虑把 g(x)g(x) 化简成 g(x)=c11−A⋅x+c21−B⋅xg(x)=\frac{c_1}{1-A\cdot x}+\frac{c_2}{1-B\cdot x} 的形式，大量的计算后得到：

A=a+a2+4⋅b2,B=a−a2+4⋅b2g(x)=c11−a+a2+4⋅b2⋅x+c21−a−a2+4⋅b2⋅xA=\frac{a+\sqrt{a^2+4\cdot b} }{2},B=\frac{a-\sqrt{a^2+4\cdot b} }{2} \\ g(x)=\frac{c_1}{1-\frac{a+\sqrt{a^2+4\cdot b} }{2}\cdot x}+\frac{c_2}{1-\frac{a-\sqrt{a^2+4\cdot b} }{2}\cdot x}

将部分分式和的形式的 g(x)g(x) 代入 (1−a⋅x−b⋅x2)⋅g(x)=f0+(f1−a⋅f0)⋅x(1-a\cdot x-b\cdot x^2)\cdot g(x)=f_0+(f_1-a\cdot f_0)\cdot x 中：

(1−a−a2+4⋅b2⋅x)⋅c1+(1−a+a2+4⋅b2⋅x)⋅c2=f0+(f1−a⋅f0)⋅x(c1+c2)+(−a−a2+4⋅b2⋅c1−a+a2+4⋅b2⋅c2)⋅x=f0+(f1−a⋅f0)⋅x(1-\frac{a-\sqrt{a^2+4\cdot b} }{2}\cdot x)\cdot c_1+(1-\frac{a+\sqrt{a^2+4\cdot b} }{2}\cdot x)\cdot c_2=f_0+(f_1-a\cdot f_0)\cdot x \\ (c_1+c_2)+(-\frac{a-\sqrt{a^2+4\cdot b} }{2}\cdot c_1-\frac{a+\sqrt{a^2+4\cdot b} }{2}\cdot c_2)\cdot x=f_0+(f_1-a\cdot f_0)\cdot x

那么又到了喜闻乐见的暴算解二元一次方程组的时候了：

{c1+c2=0−a−a2+4⋅b2⋅c1−a+a2+4⋅b2⋅c2=f1−a⋅f0\begin{cases} c_1+c_2=0 \\ -\frac{a-\sqrt{a^2+4\cdot b} }{2}\cdot c_1-\frac{a+\sqrt{a^2+4\cdot b} }{2}\cdot c_2=f_1-a\cdot f_0 \end{cases}

{c1=−a−a2+4⋅b2a2+4⋅b⋅f0+1a2+4⋅b⋅f1c2=a+a2+4⋅b2a2+4⋅b⋅f0−1a2+4⋅b⋅f1\begin{cases} c_1=-\frac{a-\sqrt{a^2+4\cdot b} }{2\sqrt{a^2+4\cdot b} }\cdot f_0+\frac{1}{\sqrt{a^2+4\cdot b} }\cdot f_1 \\ c_2=\frac{a+\sqrt{a^2+4\cdot b} }{2\sqrt{a^2+4\cdot b}}\cdot f_0-\frac{1}{\sqrt{a^2+4\cdot b} }\cdot f_1 \end{cases}

这里考虑一个生成函数的封闭形式 11−k⋅x\frac{1}{1-k\cdot x}，展开后得到：

g(x)=1+k⋅x+k2⋅x2+⋯g(x)=∑i=0∞ki⋅xig(x)=1+k\cdot x+k^2\cdot x^2+\cdots \\ g(x)=\sum_{i=0}^{\infty}k^i\cdot x^i

那么该生成函数的第 nn 项的系数为 knk^n，所以 fn=c1⋅An+c2⋅Bnf_n=c_1\cdot A^n+c_2\cdot B^n，代入 c1,c2,A,Bc_1,c_2,A,B 后得到：

fn=(−a−a2+4⋅b2a2+4⋅b⋅f0+1a2+4⋅b⋅f1)⋅(a+a2+4⋅b2)n+(a+a2+4⋅b2a2+4⋅b⋅f0−1a2+4⋅b⋅f1)⋅(a−a2+4⋅b2)nf_n=(-\frac{a-\sqrt{a^2+4\cdot b} }{2\sqrt{a^2+4\cdot b} }\cdot f_0+\frac{1}{\sqrt{a^2+4\cdot b} }\cdot f_1)\cdot(\frac{a+\sqrt{a^2+4\cdot b} }{2})^n+(\frac{a+\sqrt{a^2+4\cdot b} }{2\sqrt{a^2+4\cdot b}}\cdot f_0-\frac{1}{\sqrt{a^2+4\cdot b} }\cdot f_1)\cdot(\frac{a-\sqrt{a^2+4\cdot b} }{2})^n

例子

著名的斐波那契数列 fn=fn−1+fn−2f_n=f_{n-1}+f_{n-2}，此时 a=1,b=1,f0=0,f1=1a=1,b=1,f_0=0,f_1=1，代入通项公式得到：

fn=15(1+52)n−15(1−52)nf_n=\frac{1}{\sqrt{5} }(\frac{1+\sqrt{5} }{2})^{n}-\frac{1}{\sqrt{5} }(\frac{1-\sqrt{5} }{2})^{n}

实现

考虑模数为奇质数下的二次剩余和光速幂。如果不存在二次剩余怎么办？

这个对任意模数下求二次剩余的东西我完全不会~~（好像跟扩域有关？）~~，请教教我。

# 数学 # 生成函数 # 常系数齐次线性递推
2020-07-08 自测赛总结 上一篇
二次剩余 下一篇
0%