51nod1242【矩阵快速幂】
2024-08-21 15:04:24
基础题。。
wa在n的范围需要用long long
= =、长个记性
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=1e9+9;
struct asd{
LL a[2][2];
};
asd mul(asd x,asd y)
{
asd ans;
for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
{
ans.a[i][j]=0;
for(int k=0;k<2;k++)
{
ans.a[i][j]=ans.a[i][j]+(x.a[i][k]*y.a[k][j])%mod;
ans.a[i][j]%=mod;
}
}
}
return ans;
}
asd quickmul(LL g,asd x)
{
asd ans;
for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
{
if(i==j) ans.a[i][j]=1;
else ans.a[i][j]=0;
}
}
while(g)
{
if(g&1) ans=mul(ans,x);
x=mul(x,x);
g>>=1;
}
return ans;
}
int main()
{
LL n;
scanf("%lld",&n);
if(n==0||n==1)
{
printf("%lld\n",n);
return 0;
}
asd x,ans;
x.a[0][0]=1;x.a[0][1]=1;
x.a[1][0]=1;x.a[1][1]=0;
ans=quickmul(n-1,x);
printf("%lld\n",ans.a[0][0]);
return 0;
}
最新文章
- JavaScript权威设计--事件冒泡,捕获,事件句柄,事件源,事件对象(简要学习笔记十八)
- Play Framework 完整实现一个APP(九)
- sql例子
- github项目配置
- Python 启动本地服务
- Google Tensorflow 源码编译(三):tensorflow<;v0.5.0>;
- c#程序打包大全
- VS2013使用rtklib中需要注意的一些问题(编译)
- python登陆,注册小程序
- 【转】JS跨域(ajax跨域、iframe跨域)解决方法及原理详解(jsonp)
- iOS 8 之 新特性
- duilib基本框架
- Sqlserver将数据从一张表插入到另一张表
- github pages + Hexo + node.js 搭建属于自己的个人博客网站
- Failed to acquire lock on file .lock in /tmp/kafka-logs. A Kafka instance in another process or thread is using this directory.
- textarea 字体限制,超出部分不显示并及时显示还剩字体个数
- DirectX - dds图片格式(DDSURFACEDESC2)
- elk部署心得
- 《Windows核心编程》第五章——作业
- web常用测试点记录