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 的值
输入输出样例
输入样例#1：
5
输出样例#1：
5
输入样例#2：
10
输出样例#2：
55
说明
对于 60% 的数据： n ≤ 92
对于 100% 的数据： n在long long(INT64)范围内。
1 1
1 0
fn+1 fn
fn fn-1
注意n的范围
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
const int MOD=1e9+;
ll n;
struct mat{
ll m[][];
mat(){memset(m,,sizeof(m));}
}im,f;
void init(){
im.m[][]=im.m[][]=;
f.m[][]=f.m[][]=f.m[][]=;
}
mat mul(mat &a,mat &b){
mat c;
for(int i=;i<=;i++)
for(int k=;k<=;k++) if(a.m[i][k])
for(int j=;j<=;j++) c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]%MOD)%MOD;
return c;
}
int main(){
scanf("%lld",&n);
init();
mat ans=im;
for(;n;n>>=,f=mul(f,f))
if(n&) ans=mul(ans,f);
printf("%d",ans.m[][]);
}
P1349 广义斐波那契数列
题目描述
广义的斐波那契数列是指形如an=p*an-1+q*an-2的数列。今给定数列的两系数p和q，以及数列的最前两项a1和a2，另给出两个整数n和m，试求数列的第n项an除以m的余数。
输入输出格式
输入格式：
输入包含一行6个整数。依次是p,q,a1,a2,n,m，其中在p,q,a1,a2整数范围内，n和m在长整数范围内。
输出格式：
输出包含一行一个整数，即an除以m的余数。
输入输出样例
输入样例#1：
1 1 1 1 10 7
输出样例#1：
6
说明
数列第10项是55，除以7的余数为6。
构造矩阵
p q
1 0
求它的n-2次幂，再乘
a2
a1
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
ll p,q,a1,a2,n,MOD;
struct mat{
int r,c;
ll m[][];
mat(){r=c=;memset(m,,sizeof(m));}
}im,f;
void init(){
im.m[][]=im.m[][]=;
f.m[][]=p;f.m[][]=q;f.m[][]=;
}
mat mul(mat &a,mat &b){//printf("p\n");
mat c;
for(int i=;i<=a.r;i++)
for(int k=;k<=a.c;k++) if(a.m[i][k])
for(int j=;j<=b.c;j++) c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]%MOD)%MOD;
return c;
}
int main(){
scanf("%d%d%d%d%lld%lld",&p,&q,&a1,&a2,&n,&MOD);
init();n-=;
mat ans=im;
for(;n;n>>=,f=mul(f,f))
if(n&) ans=mul(ans,f); //printf("a %d %d %d %d\n",ans.m[1][1],ans.m[1][2],ans.m[2][1],ans.m[2][2]);
mat a;
a.r=;a.c=;
a.m[][]=a2;a.m[][]=a1;
a=mul(ans,a);
printf("%d",a.m[][]%MOD);
}
PS
gcd(fn,fm)=f(gcd(n,m))