[深证成指鑫东财配资]稻草秸秆LOJ #10222. 「一本通 6.5 例 4」佳佳的 Fibonacci 题解

如果之前推过斐波那契数列前缀和就更好做(所以题目中给出了)。

斐波那契数列前缀和题目链接

先来推一下斐波那契数列前缀和:

\[\sum\limits_{i=1}^nf(i) \]

其中 \(f(i)\) 表示Fibonacci数列第 \(i\) 项。

直接推式子:

\(s(x)=\sum\limits_{i=1}^xf(i)\)

将右边一项项展开得出

\[f(1)=1 \]

\[f(2)=1 \]

\[f(3)=f(1)+f(2) \]

\[f(4)=f(2)+f(3) \]

\[... \]

\[f(n)=f(n-2)+f(n-1) \]

这些式子左右两边分别再加回去得出

\[s(n)=1+1+f(1)+f(n-1)+2*\sum_{i=2}^{n-2}f(i) \]

把其中一个 \(1\) 变成 \(f(1)\) 再和另一个 \(f(1)\) 加到 \(2*\sum\limits_{i=2}^{n-2}f(i)\) 里面,得出

\[s(n)=1+f(n-1)+2*\sum_{i=1}^{n-2}f(i) \]

\[s(n)=1+f(n-1)+2*s(n-2) \]

\[s(n)-s(n-2)-s(n-2)=1+f(n-1) \]

\[f(n)+f(n-1)-s(n-2)=1+f(n-1) \]

\[f(n)-s(n-2)=1 \]

\[s(n-2)=f(n)-1 \]

\(n-2\) 变成 \(n\) 可得

\(s(n)=f(n+2)-1\)

注意到 \(f\) 是可以直接矩阵快速幂求的。这个时候就可以在 \(\mathcal{O}(\log n)\) 的时间复杂度求得 \(s(n)\) 了。

这个时候回来看本题:

对于 \(T(n)\) 来说,\(f(n)\) 被计算了 \(n\) 次,\(f(n-1)\) 被计算了 \((n-1)\) 次...

\[T(n)=\sum\limits_{i=1}^n{f(i)*i} \]

可以用后缀和的形式来表示这个式子,〔 微交易鑫东财配资〕,计 \(s2(i)=\sum\limits_{i=1}^n{f(i)}\)

所以上面的式子可以进一步转化成这个后缀和的形式

\[T(n)=\sum\limits_{i=1}^n{s2(i)} \]

可是 \(n\) 又不确定,又不会推后缀和,应该怎么求呢?

不会后缀和,但是我们会前缀和啊!

\(s\) 表示上述式子即为

\[T(n)=\sum\limits_{i=1}^n{s(n)-s(i-1)} \]

\(s(n)\) 提出来:

\[T(n)=n*s(n)-\sum\limits_{i=1}^n{s(i-1)} \]

代入 \(s(i)=f(i+2)-1\)

\[T(n)=n*f(n+2)-n-\sum\limits_{i=1}^n{(f(i+1)-1)} \]

\(\sum\) 里面的 \(-1\) 提出来

\[T(n)=n*f(n+2)-n-\sum\limits_{i=1}^n{f(i+1)}+n \]

之后就很简单了。

\[T(n)=n*f(n+2)-n-\sum\limits_{i=2}^{n+1}{f(i)}+n \]

\[T(n)=n*f(n+2)-n-\sum\limits_{i=2}^{n+1}{f(i)}+f(1)-f(1)+n \]

\[T(n)=n*f(n+2)-n-\sum\limits_{i=1}^{n+1}{f(i)}-f(1)+n \]

化简一下

\[T(n)=n*f(n+2)-s(n+1)-1 \]

\[T(n)=n*f(n+2)-(f(n+3)-1)-1 \]

\[T(n)=n*f(n+2)-f(n+3)+2 \]

矩阵快速幂求 \(f(n+2)\)\(f(n+3)\) 就能 \(\mathcal{O}(\log n)\) 的时间复杂度求出 \(T(n)\) 了。

因为最后的式子里面有个减法,可以提前在减法之前加上一个 \(m\) 来防止负数取模的情况发生。

参考 \(\mathcal{Code}\)

#include<iostream> #include<cstdio> #define ll long long int n,m; struct Matrix { ll mat[3][3]; int n,m; void memset() { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) mat[i][j]=0; } }; Matrix mul(Matrix x,Matrix y) { Matrix z; z.n=x.n; z.m=y.m; z.memset(); for(int i=1;i<=z.n;i++) for(int j=1;j<=z.m;j++) for(int k=1;k<=x.m;k++) z.mat[i][j]=(z.mat[i][j]+x.mat[i][k]*y.mat[k][j])%m; return z; } Matrix qpow(Matrix base,int y) { Matrix ans; ans.n=ans.m=2; ans.memset(); for(int i=1;i<=2;i++) ans.mat[i][i]=1; while(y) { if(y&1) ans=mul(ans,base); base=mul(base,base); y>>=1; } return ans; } ll f(int n) { Matrix ans,base; ans.n=1; ans.m=2; base.n=base.m=2; ans.memset(); base.memset(); ans.mat[1][1]=1;ans.mat[1][2]=1; base.mat[1][1]=0;base.mat[1][2]=1; base.mat[2][1]=1;base.mat[2][2]=1; base=qpow(base,n-2); ans=mul(ans,base); return ans.mat[1][2]; } int main() { scanf("%d%d",&n,&m); printf("%lld",(n*f(n+2)%m-f(n+3)+m+2)%m); return 0; }