HDU 1005 Number Sequence(矩阵)
2018-06-17 22:01:34来源:未知 阅读 ()
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 177761 Accepted Submission(s):
44124
f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.
Given A, B, and n, you are to calculate the value of f(n).
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 using namespace std; 5 const int MAXN=1001; 6 inline void read(int &n){char c='+';bool flag=0;n=0; 7 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar(); 8 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;} 9 struct matrix 10 { 11 int m[3][3];matrix(){memset(m,0,sizeof(m));} 12 }; 13 matrix ma; 14 int limit=2; 15 const int mod=7; 16 matrix mul(matrix a,matrix b) 17 { 18 matrix c; 19 for(int k=0;k<limit;k++) 20 for(int i=0;i<limit;i++) 21 for(int j=0;j<limit;j++) 22 c.m[i][j]=(c.m[i][j]+(a.m[i][k]*b.m[k][j]))%mod; 23 return c; 24 } 25 matrix fast_martix_pow(matrix ma,int p) 26 { 27 matrix bg; 28 bg.m[0][0]=1;bg.m[1][1]=1; 29 bg.m[0][1]=0;bg.m[1][0]=0; 30 /*for(int i=0;i<limit;i++) 31 { 32 for(int j=0;j<limit;j++) 33 cout<<bg.m[i][j]<<" "; 34 cout<<endl; 35 }*/ 36 37 while(p) 38 { 39 if(p&1) bg=mul(bg,ma); 40 ma=mul(ma,ma); 41 p>>=1; 42 } 43 return bg; 44 } 45 int main() 46 { 47 int a,b,n; 48 while(scanf("%d%d%d",&a,&b,&n)&&(a!=0&&b!=0&&n!=0)) 49 { 50 ma.m[0][0]=a;ma.m[0][1]=b; 51 ma.m[1][0]=1;ma.m[1][1]=0; 52 if(n<3) 53 { 54 printf("1\n"); 55 continue; 56 } 57 matrix ans=fast_martix_pow(ma,n-2); 58 printf("%d\n",(ans.m[0][1]+ans.m[0][0])%mod); 59 } 60 return 0; 61 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:[最短路]P1078 文化之旅
下一篇:P3389 【模板】高斯消元法
- HDU-2955-Robberies(0-1背包) 2020-03-30
- hdu1455 拼木棍(经典dfs) 2020-02-29
- anniversary party_hdu1520 2020-02-16
- hdu1062 text reverse 2020-01-27
- hdu4841 2020-01-26
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