【佳佳的斐波那契】

本文主要是介绍【佳佳的斐波那契】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

---

思路

我们的目标是T[n]： ${\sum }_{1<=i<=n}if[i]$


我们的迭代目标是： $T[n]\to T[n+1]$


为了达成迭代目标，我们需要引入： $T[n+1]-T[n]=(n+1)\cdot f[n+1]$


不失一般性，我们把引入的对象看成: $(n+2)\cdot f[n+2]$


为了引入这个，我们引入 nf[n] 和 (n+1)f[n+1]，就有：

$n\cdot f[n]+2f[n]+(n+1)\cdot f[n+1]+f[n+1]=(n+2)f[n+2]$

由此我们确定了需要引入的几个式子：
$[f[n],f[n+1],nf[n],(n+1)f[n+1],T[n]]$

其中，几个公式构成的子矩阵本身是可迭代的：
$$\begin{array}{r}[f[n],f[n+1]]\\ [f[n],f[n+1],n\cdot f[n],(n+1)\cdot f[n+1]]\end{array}$$

---

代码

#pragma GCC optimize(3)
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;const int N = 5;
int n, m;
void mul(int c[][N], int a[][N], int b[][N])
{int temp[N][N] = {0};for(int i = 0; i < N; i++){for(int j = 0; j < N; j++){for(int k = 0; k < N; k++){temp[i][j] = (temp[i][j] + 1LL * a[i][k] * b[k][j]) % m;}}}memcpy(c, temp, sizeof temp);
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m;int a[N][N] = {1, 1, 1, 2, 1};int b[N][N] = {{0,1,0,2,0},{1,1,0,1,0},{0,0,0,1,0},{0,0,1,1,1},{0,0,0,0,1}};int x = n-1;while (x){if(x & 1) mul(a, a, b);mul(b, b, b);x >>= 1;}cout << a[0][4] % m;return 0;
}

这篇关于【佳佳的斐波那契】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---