自动搬运

查看原文

来自洛谷，原作者为

	常青藤 **

搬运于2025-08-24 21:25:38，当前版本为作者最后更新于2019-02-28 12:49:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

前言：安利一发自己的博客（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$

$......$

$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=\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$

则——

$$\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$$

其中 $i\leq 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_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