【luogu 1939】【模板】矩阵加速(数列)
2018-06-17 21:46:47来源:未知 阅读 ()
题目描述
a[1]=a[2]=a[3]=1
a[x]=a[x-3]+a[x-1] (x>3)
求a数列的第n项对1000000007(10^9+7)取余的值。
输入输出格式
输入格式:
第一行一个整数T,表示询问个数。
以下T行,每行一个正整数n。
输出格式:
每行输出一个非负整数表示答案。
输入输出样例
3 6 8 10
4 9 19
说明
对于30%的数据 n<=100;
对于60%的数据 n<=2*10^7;
对于100%的数据 T<=100,n<=2*10^9;
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #define ll long long 6 #define Mod 1000000007 7 using namespace std; 8 int t;ll n; 9 struct matrix{ll m[5][5];}a; 10 matrix multiply(matrix a,matrix b){ 11 matrix t; 12 for(int i=1;i<=3;i++) 13 for(int j=1;j<=3;j++){ 14 t.m[i][j]=0; 15 for(int k=1;k<=3;k++) 16 t.m[i][j]=(t.m[i][j]+a.m[i][k]*b.m[k][j])%Mod; 17 } 18 return t; 19 } 20 matrix fast(matrix a,ll k){ 21 matrix ans=a;k--; 22 while(k>0){ 23 if(k&1) ans=multiply(ans,a); 24 a=multiply(a,a); 25 k>>=1; 26 } 27 return ans; 28 } 29 int main(){ 30 a.m[1][3]=a.m[2][1]=a.m[3][2]=a.m[3][3]=1; 31 scanf("%d",&t); 32 for(int i=1;i<=t;i++){ 33 scanf("%lld",&n); 34 matrix tmp=fast(a,n); 35 printf("%d\n",tmp.m[3][2]); 36 } 37 return 0; 38 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++冒泡排序 (基于函数模板实现) 2020-05-31
- C++ 模板类vector 2020-05-31
- C++ 模板类array 2020-05-31
- C++ 模板类vector 2020-05-30
- 单调队列模板【附例题】 2020-05-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash