hdu4549 M斐波那契数列 矩阵快速幂+快速幂
2024-10-16 04:18:33
M斐波那契数列F[n]是一种整数数列,它的定义如下:
F[0] = a
F[1] = b
F[n] = F[n-1] * F[n-2] ( n > 1 )
现在给出a, b, n,你能求出F[n]的值吗?
通过简单地列出若干项 F 即可发现,某一项的值是由若干 a 和 b 相乘得到的,而他们的指数是连续的两项斐波那契数。
因此可以通过斐波那契数列的矩阵快速幂求法得到,注意需要指数的降幂公式。
#include<stdio.h>
#include<string.h>
typedef long long ll;
const int mod=;
const int mmod=;
struct mat{
int r,c;
ll m[][];
void clear(){
for(int i=;i<=r;i++)memset(m[i],,sizeof(m[i]));
}
}; int read(){
int x=;
char c=getchar();
while(c>''||c<'')c=getchar();
while(c>=''&&c<=''){
x=x*+c-'';
c=getchar();
}
return x;
} mat MatMul(mat &m1,mat &m2){
mat tmp;
tmp.r=m1.r;
tmp.c=m2.c;
int i,j,k;
for(i=;i<=tmp.r;i++){
for(j=;j<=tmp.c;j++){
ll t=;
for(k=;k<=m1.c;k++){
t=(t+(m1.m[i][k]*m2.m[k][j])%mmod)%mmod;
}
tmp.m[i][j]=t;
}
}
return tmp;
} mat MatQP(mat &a,int n){
mat ans,tmp=a;
ans.r=ans.c=a.r;
memset(ans.m,,sizeof(ans.m));
for(int i=;i<=ans.r;i++){
ans.m[i][i]=;
}
while(n){
if(n&)ans=MatMul(ans,tmp);
n>>=;
tmp=MatMul(tmp,tmp);
}
return ans;
} ll QP(ll a,ll n){
ll tmp=a,ans=;
while(n){
if(n&)ans=ans*tmp%mod;
tmp=tmp*tmp%mod;
n>>=;
}
return ans%mod;
} int main(){
int x,y,n;
mat t,tmp;
t.r=;t.c=;
t.clear();
t.m[][]=t.m[][]=t.m[][]=;
mat a;
a.r=;
a.c=;
a.m[][]=;
a.m[][]=;
ll ans;
while(scanf("%d%d%d",&x,&y,&n)!=EOF){
if(n==)printf("%d\n",x);
else{
tmp=MatQP(t,n-);
tmp=MatMul(tmp,a);
ans=QP(x,tmp.m[][])*QP(y,tmp.m[][])%mod;
printf("%lld\n",ans);
}
}
return ;
}
最新文章
- canvas贝塞尔曲线 - 1
- ubuntu-docker-consul-swarm-shipyard-portainer
- javascript篇-----函数apply()和call()
- Reflector.exe 破解注意事项
- 旅图beta版 asp.net web api 单元测试
- XCode6.0的iOS免证书真机测试方法(MAC及黑苹果均有效)
- BZOJ1590 [Usaco2008 Dec]Secret Message 秘密信息
- word wrap 解惑
- asp.net基础
- PHP学习笔记三十三【自定义错误处理器】
- [DevExpress]图表开发工具类 ChartUtils
- jquery背景动画插件使用
- Map 根据value 排序
- Memcached Client的释疑
- dataTables 使用整理
- 【FPGA学习】Verilog之加法器
- poj2083 Fractal
- ImageMagick:获取一行文字的宽与高
- Failed to auto-configure a DataSource: &#39;spring.datasource.url&#39; is not specified and no embedded datasource could be auto-configured.
- lock和Monitor(锁对象)
热门文章
- [POJ3416]Crossing
- .net core webapi 配置swagger调试界面
- 将自己的域名解析跳转到博客主页(GitHub中的gitpage跳转)
- Java基础-类和对象
- IDEA中自动生成serialVersionUID
- android 自定义命名空间 http://schemas.android.com/apk/res-auto
- WIN10-缩放与布局
- dict的items()方法于iteritems()方法的不同
- LeetCode--1、26、27、35、53 Array(Easy)
- flex 布局 出滚动条的操作