题解 P1487 【失落的成绩单】

· · 题解

前言：安利一发自己的博客（LaTeX挂了这边走）（正在迁移）

UPD:发现LaTeX有部分不能正常显示，在洛谷博客里还好好的，试着调了一下，并删除了一些可有可无的话，求通过

题目描述：

数列 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=\{x\mid x=(-2)^k,k\in\mathbb{N^*}\}\ ,\ B=\{x\mid x=3^k,k\in\mathbb{N^*}\}

那么，我们可以列出 A 的前几项：-2,4,-8,16,...，B 的前几项：3,9,27,81,...

将 A 代入递推式，神奇的发现——

f_1=-2 f_2=4 f_3=4+6\times(-2)=-8 f_4=-8+6\times4=16 ...... 很明显，$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=\alpha\times a^i+\beta\times b^i$ 同样满足（两式乘上系数相加即可） 接下来，我们来看一个经典的例子——斐波拉契数列 $f_i=f_{i-1}+f_{i-2}

现在我们不能像刚才那个式子“观察”出一个通解了，那么就需要我们自己进行构造

现在我们设存在一组等比数列满足这个递推式，其公比为 q ，那么我们看一下这个式子——

f_i=f_{i-1}+f_{i-2} q^2\times f_{i-2}=q\times 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{\pm\sqrt5+1}{2}的等比数列满足斐波拉契数列

那么，我们又知道了数列的前两项：f_1=f_2=1

我们设 f_i=\alpha\times(\frac{\sqrt5+1}{2})^i+\beta\times(\frac{-\sqrt5+1}{2})^i，代入f_1,f_2

则——

\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

其中 i\leq n，并且

\alpha(-\sqrt{2}-1)+\beta(\sqrt{2}-1)=a_1\\ \alpha(-\sqrt{2}-1)^n+\beta(\sqrt{2}-1)^n=a_n\\ \end{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_n\times f(m-1)+(-1)^{m-1}a_1\times f(n-m)}{f(n-1)}

好了，现在是最后一个问题——还有d呢！

观察递推式—— A_i=-2A_{i-1}+A_{i-2}+2d

我们设 A_i=a_i+p\times 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<bits/stdc++.h>
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