基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题
收藏
关注斐波那契数列的定义如下：
F(0) = 0
F(1) = 1
F(n) = F(n - 1) + F(n - 2) (n >= 2)
(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...)
给出n，求F(n)，由于结果很大，输出F(n) % 1000000009的结果即可。
Input
输入1个数n(1 <= n <= 10^18)。
Output
输出F(n) % 1000000009的结果。
运用矩阵乘法去做，有矩阵，可以矩阵快速幂求出转移矩阵即可得到结果。
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long LL;
int n = ;
struct mat
{
LL a[][];
};
mat mul(mat m1,mat m2)
{
mat ans;
for(int i=;i<n;i++)
for(int j=;j<n;j++)
{
LL temp = ;
for(int k=;k<n;k++)
{
temp+=m1.a[i][k]*m2.a[k][j];
}
ans.a[i][j] = temp % ;
}
return ans;
}
mat pow(mat m,LL b)
{
if(b<=)
return m;
mat temp = pow(m,b/);
if(b&)
return mul(mul(temp,temp),m);
else
return mul(temp,temp);
}
int main()
{
LL num;
mat beg;
beg.a[][]=beg.a[][]=beg.a[][]=;beg.a[][]=;
cin>>num;
cout<<pow(beg,num-).a[][]<<endl;
return ;
}
在2*N的一个长方形方格中，用一个1*2的骨牌排满方格。
问有多少种不同的排列方法。
例如：2 * 3的方格，共有3种不同的排法。（由于方案的数量巨大，只输出 Mod 10^9 + 7 的结果）
Input
输入N(N <= 1000)
Output
输出数量 Mod 10^9 + 7
Input示例
3
Output示例
3 显然,N=1时一种方法，N=2时有两种方法。
当N>2，可分为两种情况，1是竖着放，那么方法数目为前n-1个的结果，f(n-1)
2是两个横着放，这样占用了两个格子，方法数目是前n-2个结果 f(n-2)
f(n)=f(n-1)+f(n-2),f(1)=1,f(2)=2;
由上面程序略作修改
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long LL;
int n = ;
#define M 1000000007
struct mat
{
LL a[][];
};
mat mul(mat m1,mat m2)
{
mat ans;
for(int i=;i<n;i++)
for(int j=;j<n;j++)
{
LL temp = ;
for(int k=;k<n;k++)
{
temp+=m1.a[i][k]*m2.a[k][j];
}
ans.a[i][j] = temp%M;
}
return ans;
}
mat pow(mat m,LL b)
{
if(b<=)
return m;
mat temp = pow(m,b/);
if(b&)
return mul(mul(temp,temp),m);
else
return mul(temp,temp);
}
int main()
{
LL num;
mat beg;
beg.a[][]=beg.a[][]=beg.a[][]=;beg.a[][]=;
cin>>num;
mat tmp;
tmp.a[][]=,tmp.a[][]=tmp.a[][]=,tmp.a[][]=;
mat r = pow(beg,num-);
mat as=mul(tmp,r);
cout<<as.a[][]<<endl;
return ;
}
基准时间限制：1 秒 空间限制：131072 KB 分值: 10 难度：2级算法题
收藏 关注有一个序列是这样定义的：f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.
给出A，B和N，求f(n)的值。
Input
输入3个数：A,B,N。数字之间用空格分割。(-10000 <= A, B <= 10000, 1 <= N <= 10^9)
Output
输出f(n)的值。 同样思路用矩阵做，注意避免负数的出现 （ans+7）%7.只需把递归式中系数修改。
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long LL;
int n = ;
#define M 1000000007
struct mat
{
LL a[][];
};
mat mul(mat m1,mat m2)
{
mat ans;
for(int i=;i<n;i++)
for(int j=;j<n;j++)
{
LL temp = ;
for(int k=;k<n;k++)
{
temp+=m1.a[i][k]*m2.a[k][j] ;
}
ans.a[i][j] = (temp+)%;
}
return ans;
}
mat pow(mat m,LL b)
{
if(b<=)
return m;
mat temp = pow(m,b/);
if(b&)
return mul(mul(temp,temp),m);
else
return mul(temp,temp);
}
int main()
{
LL num,t1,t2;
cin>>t1>>t2>>num;
mat beg;
beg.a[][]=t1,beg.a[][]=t2,beg.a[][]=;beg.a[][]=;
mat r = pow(beg,num-);
cout<<(r.a[][]+r.a[][]+)%<<endl;
return ;
}