{var%20f='http://v.t.sina.com.cn/share/share.php?appkey=1515056452',u=z||d.location,p=['&url=',e(u),'&title=',e(t||d.title),'&source=',e(r),'&sourceUrl=',e(l),'&content=',c||'gb2312','&pic=',e(p||'')].join('');function%20a(){if(!window.open([f,p].join(''),'mb',['toolbar=0,status=0,resizable=1,width=440,height=430,left=',(s.width-440)/2,',top=',(s.height-430)/2].join('')))u.href=[f,p].join('');};if(/Firefox/.test(navigator.userAgent))setTimeout(a,0);else%20a();})(screen,document,encodeURIComponent,'','','https://www.xiaopingtou.cn//data/attach/topic/topicKPo7gB.jpg', '推荐 xingdong2hao 的文章《斐波那契数列的第N项（矩阵快速幂模板）》','https://www.xiaopingtou.net/article-57647.html','页面编码gb2312|utf-8默认gb2312'));){kind=link}
1242 斐波那契数列的第N项
基准时间限制：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的结果。 Input示例 11 Output示例 89
基准时间限制：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的结果。 Input示例 11 Output示例 89
#include
using namespace std;
typedef long long LL;
const int mod=1000000009;
struct mx
{
LL a[2][2];
};
mx solve(mx a,mx b)
{
mx c;
for(int i=0; i<2; i++)
for(int j=0; j<2; j++)
{
c.a[i][j]=0;
for(int k=0; k<2; k++)
{
c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j]%mod)%mod;
}
}
return c;
}
mx qpow(mx t,LL n)
{
mx ans;
ans.a[0][0]=ans.a[1][1]=1;
ans.a[0][1]=ans.a[1][0]=0;
while(n)
{
if(n&1)
ans=solve(ans,t);
n>>=1;
t=solve(t,t);
}
return ans;
}
int main()
{
LL n;
scanf("%lld",&n);
mx t= {1,1,1,0};
mx ans=qpow(t,n-1);
printf("%lld
",(ans.a[1][1]+ans.a[0][1])%mod);
return 0;
}