首页 > 分享 > 洛谷 P1487 失落的成绩单

洛谷 P1487 失落的成绩单

花匠小妙招
2024-12-09 10:18

传送门：洛谷 P1487 失落的成绩单
题目描述：

数列 (a) 满足

[A_i=frac{A_{i-1}-A_{i+1}}{2}+d ]

给出：首项 (A_1)、末项 (A_n)、(d)、(m)，求(A_m)

算法分析：
矩阵快速幂？还没学，所以我们就用数(mo)学(fa)来解决这道题。
预备知识：特征方程

我们以这个式子为例—— (f_i=f_{i-1}+6f_{i-2})
首先我们来看两个数集
(A={xmid x=(-2)^k,kinmathbb{N^*}} , B={xmid x=3^k,kinmathbb{N^*}})
那么，我们可以列出 (A) 的前几项：(-2,4,-8,16,...)，(B) 的前几项：(3,9,27,81,...)
将 (A) 代入递推式，神奇的发现——
(f_1=-2)
(f_2=4)
(f_3=4+6times(-2)=-8)
(f_4=-8+6times4=16)
(......)
(A) 中的数都满足上述的递推式，同样的，(B) 也满足。
很明显，(f_i=(-2)^k) 和 (f_i=3^k) 都是上述递推式的通项公式
下面我们来看两个引理——

1、若 (f_i=a^i) 是某一递推式的通项公式，那么，(f_i=lambda a^i) 同样满足递推式（两边同乘上系数即可）

2、若 (f_i=a^i) 和 (f_i=b^i) 都满足递推式，那么，(f_i=alphatimes a^i+betatimes b^i) 同样满足（两式乘上系数相加即可）

接下来，我们来看一个经典的例子——斐波拉契数列 (f_i=f_{i-1}+f_{i-2})
现在我们不能像刚才那个式子“观察”出一个通解了，那么就需要我们自己进行构造（自己动手，丰衣足食）
现在我们设存在一组等比数列满足这个递推式（不是等比怎么约分啊），其公比为 (q) ，那么我们看一下这个式子——

[f_i=f_{i-1}+f_{i-2} ]

[q^2times f_{i-2}=qtimes f_{i-2}+f_{i-2} ]

[q^2=q+1 ]

[q^2-q-1=0 ]

这就是斐波拉契数列的特征方程
把它解出来，可以得到—— (q_1=frac{sqrt5+1}{2},q_2=frac{-sqrt5+1}{2})
那么，我们就知道了——公比为(frac{pmsqrt5+1}{2})的等比数列满足斐波拉契数列
那么，我们又知道了数列的前两项：(f_1=f_2=1)
我们设 (f_i=alphatimes(frac{sqrt5+1}{2})^i+betatimes(frac{-sqrt5+1}{2})^i)，代入(f_1,f_2)
则——

[begin{cases} alpha(frac{sqrt5+1}{2})+beta(frac{-sqrt5+1}{2})=f_1=1\ alpha(frac{sqrt5+1}{2})^2+beta(frac{-sqrt5+1}{2})^2=f_2=1\ end{cases} ]

得 (alpha=frac{sqrt5}{5},beta=-frac{sqrt5}{5})，这样，我们就求出了通项公式
回到之前的递推数列——(f_i=f_{i-1}+6f_{i-2})，怎么得出其通解的？
其实很简单。我们设等比数列公比为 (q)，就可以得到特征方程—— (q^2-q-6=0 Rightarrow q_1=-2,q_2=3)

进入正题，首先来膜改一下式子：

[A_i=frac{A_{i-1}-A_{i+1}}{2}+d ]

[2A_i=A_{i-1}-A_{i+1}+2d ]

[A_{i+1}=-2A_{i}+A_{i-1}+2d ]

这是 (A) 的递推式，我们将 (i) 减 (1)：

[A_{i}=-2A_{i-1}+A_{i-2}+2d ]

现在我们得出了答案 —— (A_{i}=-2A_{i-1}+A_{i-2}+2d)
那么我们先将 (2d) 放在一边，设数列 (a) 满足 (a_{i}=-2a_{i-1}+a_{i-2})
设此数列公比为 (q)，现在代入——

[q^2a_{i-2}=-2qa_{i-2}+a_{i-2} ]

[q^2+2q-1=0 ]

这就是上述递推式的特征方程
现在解一下这个方程，可以得到—— (q_1=-sqrt{2}-1,q_2=sqrt{2}-1)
那么我们就可以得到这个数列的通项公式——

[a_i=alpha(-sqrt{2}-1)^i+beta(sqrt{2}-1)^i ]

其中 (ileq n)，并且

[begin{cases} alpha(-sqrt{2}-1)+beta(sqrt{2}-1)=a_1\ alpha(-sqrt{2}-1)^n+beta(sqrt{2}-1)^n=a_n\ end{cases} ]

将上面的方程解出来，我们可以得到——

[begin{cases} alpha=frac{a_1(sqrt{2}-1)^{n-1}-a_n}{(-sqrt{2}-1)(sqrt{2}-1)^{n-1}-(-sqrt{2}-1)^n}\ \ beta=frac{a_1(-sqrt{2}-1)^{n-1}-a_n}{(sqrt{2}-1)(-sqrt{2}-1)^{n-1}-(sqrt{2}-1)^n}\ end{cases} ]

代入通项公式并整理——

[a_m=frac{a_n[(sqrt{2}-1)^{m-1}-(-1)^{m-1}(sqrt{2}+1)^{m-1}]+(-1)^{m-1}a_1[(sqrt{2}-1)^{n-m}-(-sqrt{2}-1)^{n-m}]}{(sqrt{2}-1)^{n-1}-(-1)^{n-1}(sqrt{2}+1)^{n-1}} ]

设(f(x)=(sqrt2-1)^x-(-1)^x(sqrt2+1)^x)，可得

[a_m=frac{a_ntimes f(m-1)+(-1)^{m-1}a_1times f(n-m)}{f(n-1)} ]

好了，现在是最后一个问题——还有(d)呢！
其实很容(kun)易(nan)，观察递推式—— (A_i=-2A_{i-1}+A_{i-2}+2d)
我们设 (A_i=a_i+ptimes d)，代入——

[A_i=-2A_{i-1}+A_{i-2}+2d ]

[a_i+pd=-2a_{i-1}-2pd+a_{i-2}+pd+2d ]

我们又有 (a_{i}=-2a_{i-1}+a_{i-2})，那么两边约去，可得——

[pd=-2pd+pd+2d Rightarrow p=1 ]

故 (A_i=a_i+d)
那么，根据题意，我们来膜改一下式子——

[A_m=frac{(A_n-d)times f(m-1)+(-1)^{m-1}(A_1-d)times f(n-m)}{f(n-1)}+d ]

这样，我们就得到了数列的通项公式，代码就很好写了（没用龟(kuai)速幂，数据太弱QwQ）

#include<iostream> #include<cstdio> #include<cmath> using namespace std; const double p=sqrt(2)-1; int n,m; double d,a1,an; double c(int op) {return (op&1)?-1:1;} double f(int x) {return pow(p,x)-c(x)*pow(p+2,x);} int main() { scanf("%d%d%lf%lf%lf",&n,&m,&d,&a1,&an); if(m==0) printf("0.000"); else printf("%.3lf",((an-d)*f(m-1)+c(m-1)*(a1-d)*f(n-m))/f(n-1)+d); return 0; } 完结撒花QwQ