本文主要是介绍【矩阵乘法】幼儿园数学题I(ssl 2513),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
幼儿园数学题I
ssl 2513
题目大意
定义 f n = ( 5 + 1 2 ) n − 1 f_n=\left ( \frac{\sqrt{5}+1}{2}\right )^{n-1} fn=(25+1)n−1,求前n项的和,(对 1 0 9 + 7 10^9+7 109+7取模)(题目貌似出了些问题,实际上 f f f等价于斐波那契数列)
输入样例#1
1
输出样例#1
1
输入样例#2
2
输出样例#2
2
数据范围
1 ⩽ n ⩽ 2 31 − 1 1\leqslant n\leqslant2^{31}-1 1⩽n⩽231−1
解题思路
通过打表可以发现 f f f等价于斐波那契数列,那题目就是求斐波那契数列前 n n n项的和
n十分大,不能直接递推
考虑矩阵乘法
设矩阵 [ f i − 2 f i − 1 s i − 2 ] \begin{bmatrix}f_{i-2} & f_{i-1} & s_{i-2}\end{bmatrix} [fi−2fi−1si−2]
在通过乘矩阵 [ 0 1 0 1 1 1 0 0 1 ] \begin{bmatrix}0 & 1 & 0\\ 1 & 1 & 1\\ 0 & 0 & 1\end{bmatrix} ⎣⎡010110011⎦⎤来递推
然后快速幂即可
代码
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define wyc 1000000007
using namespace std;
ll n;
struct matrix
{ll n, m, a[10][10];matrix operator *(const matrix &b) const{matrix c;c.n = n;c.m = b.m;for (int i = 1; i <= c.n; ++i)for (int j = 1; j <= c.m; ++j)c.a[i][j] = 0;for (int i = 1; i <= c.n; ++i)for (int k = 1; k <= m; ++k)for (int j = 1; j <= c.m; ++j)c.a[i][j] = (c.a[i][j] + a[i][k] * b.a[k][j] % wyc) % wyc;return c;}
}A, B;
void Counting(ll x)
{while(x){if (x&1) A = A * B;B = B * B;x>>=1;}
}
int main()
{scanf("%lld", &n);A.n = 1;A.m = B.n = B.m = 3;A.a[1][1] = 1, A.a[1][2] = 1, A.a[1][3] = 1;//初始状态B.a[1][1] = 0, B.a[1][2] = 1, B.a[1][3] = 0;//相乘的矩阵B.a[2][1] = 1, B.a[2][2] = 1, B.a[2][3] = 1;B.a[3][1] = 0, B.a[3][2] = 0, B.a[3][3] = 1;Counting(n - 1);printf("%lld", A.a[1][3]);return 0;
}
这篇关于【矩阵乘法】幼儿园数学题I(ssl 2513)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!