牛客挑战赛32

前言

2019.9.20

我真是不知好歹参加了这个比赛。在ygt大佬的帮助下勉强推出了C题的式子，由于矩阵加速忘记了，所以没打出代码来。总结一下：准爆零qwq。

很快就要提高组比赛了，这样的水平不知道能考出几分，emm... ...

C

\(\text{ygt}\)大佬是这样说的：

把ai展开 然后把ai中含fi的降下标 就能跟ai-1,ai-2找到关系

那就让我们找找看吧

已知：

\[a[n]=\sum_{k=0}^nF[n-k]*F[k]\]

那我们将之展开就是：

\[a[i]=F[i]*F[0]+F[i-1]*F[1]+F[i-2]*F[2]+...\]

\[+F[2]*F[i-2]+F[1]*F[i-1]+F[0]*F[i]\]

\(\because F[0]=0,\therefore F[i]*F[0]=0 \therefore\)

\[a[i]=F[i-1]*F[1]+F[i-2]*F[2]+...+F[2]*F[i-2]+F[1]*F[i-1]\]

也许你已经发现了 \(a[i]\) 这个式子有一些特点，不过别急，先往下面看

不妨把\(a[i-1],a[i-2]\)也展开看看，那么就是:

\[a[i-1]=F[i-2]*F[1]+F[i-3]*F[2]+...+F[2]*F[i-3]+F[1]*F[i-2]\]

\[a[i-2]=F[i-3]*F[1]+F[i-3]*F[2]+...+F[2]+F[i-4]+F[1]*F[i-3]+F[0]*F[i-2]\]

前面已经说过 \(F[0]=0\) ,那为什么这里又把 \(F[0]*F[i-2]\) 列出来呢?

下面就是重点啦！

我们知道 \(F[i-1]=F[i-2]+F[i-3]\)，那么来观察一下\(a[i]\)，\(a[i-1]\) 和 \(a[i-2]\) 的展开式

我们发现

\(F[i-2]*F[1]+F[i-3]*F[1]=(F[i-1]+F[i-2])*F[1]=F[i-1]*F[1]\)

进而，我们可以发现\(a[i]\) 与 \(a[i-1],a[i-2]\) 的每一项均可以一一对应。

现在再理解一下

\(F[0]*F[i-2]+F[1]*F[i-2]=(F[0]+F[1])*F[i-2]=F[2]*F[i-1]\)

这样就很明白了

不过最后我们还发现一一对应后还有一个 \(F[1]*F[i-1]\) 是没有对应的，于是就推导出了这个式子：

\[a[i]=a[i-1]+a[i-2]+F[1]*F[i-1]\]

讲完完后感觉自己的智商是普及组三等奖水平

代码下午补