洛谷P1962
题目背景
大家都知道,斐波那契数列是满足如下性质的一个数列:
• f(1) = 1
• f(2) = 1
• f(n) = f(n-1) + f(n-2) (n ≥ 2 且 n 为整数)
题目描述
请你求出 f(n) mod 1000000007 的值。
输入输出格式
输入格式:
·第 1 行:一个整数 n
输出格式:
第 1 行: f(n) mod 1000000007 的值
输入输出样例
5
5
10
55
说明
对于 60% 的数据: n ≤ 92
对于 100% 的数据: n在long long(INT64)范围内。
矩阵的模板并不难,主要就是如何画出有用的矩阵
另外,还需特别记住一点:矩阵乘法不满足交换律,但满足结合律。
1 #include<bits/stdc++.h>
2 #define ll long long
3 using namespace std;
4 const int mod=1e9+7;
5 struct matrix
6 {
7 ll m[11][11];
8 }a,b,ans;
9 ll n;
10
11 inline matrix mul(matrix a,matrix b)
12 {
13 matrix ans;
14 for(int i=1;i<=2;i++)
15 for(int j=1;j<=2;j++)
16 {
17 ans.m[i][j]=0;
18 for(int k=1;k<=2;k++)
19 ans.m[i][j]=(ans.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
20 }
21 return ans;
22 }
23 inline matrix matpow(matrix a,ll k)
24 {
25 matrix base=a,ans=a;k--;
26 while(k)
27 {
28 if(k&1) ans=mul(ans,base);
29 base=mul(base,base);
30 k>>=1;
31 }
32 return ans;
33 }
34 int main()
35 {
36 scanf("%lld",&n);
37 if(n<=2){printf("1\n");return 0;}
38 a.m[1][1]=1;a.m[1][2]=1;a.m[2][1]=1;a.m[2][2]=0;
39 b.m[1][1]=1;b.m[2][1]=1;//前面的是f(2) 后面的是f(1);
40 a=matpow(a,n-1);
41 ans=mul(a,b);
42 cout<<ans.m[2][1]<<endl;//输出的是下面的f(n) 上面的是f(n+1)
43 return 0;
44 }
原文链接: https://www.cnblogs.com/Slager-Z/p/7771738.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/262501
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!