1065 - Number Sequence &&1070 - Algebraic Problem
2024-10-18 09:02:07
1065 - Number Sequence
| Time Limit: 2 second(s) | Memory Limit: 32 MB |
Let's define another number sequence, given by the following function:
f(0) = a
f(1) = b
f(n) = f(n-1) + f(n-2), n > 1
When a = 0 and b = 1, this sequence gives the Fibonacci sequence. Changing the values of a and b, you can get many different sequences. Given the values of a, b, you have to find the last m digits of f(n).
Input
Input starts with an integer T (≤ 10000), denoting the number of test cases.
Each test case consists of a single line containing four integers a b n m. The values of a and b range in [0,100], value of n ranges in [0, 109] and value of m ranges in [1, 4].
Output
For each case, print the case number and the last m digits of f(n). However, do NOT print any leading zero.
Sample Input |
Output for Sample Input |
|
4 0 1 11 3 0 1 42 4 0 1 22 4 0 1 21 4 |
Case 1: 89 Case 2: 4296 Case 3: 7711 Case 4: 946 |
Special Thanks: Jane Alam Jan (Solution, Dataset)
矩阵快速幂水题
1 #include<stdio.h>
2 #include<algorithm>
3 #include<iostream>
4 #include<string.h>
5 #include<stdlib.h>
6 #include<queue>
7 #include<math.h>
8 #include<vector>
9 using namespace std;
10 typedef long long LL;
11 typedef struct pp
12 {
13 LL m[4][4];
14 pp()
15 {
16 memset(m,0,sizeof(m));
17 }
18 } maxtr;
19 maxtr E()
20 {
21 maxtr ans;
22 int i,j;
23 for(i=0; i<4; i++)
24 {
25 for(j=0; j<4; j++)
26 {
27 if(i==j)
28 {
29 ans.m[i][j]=1;
30 }
31 else ans.m[i][j]=0;
32 }
33 }
34 return ans;
35 }
36 void Init (maxtr *p)
37 { int i,j;
38 for(i=0; i<2; i++)
39 {
40 for(j=0; j<2; j++)
41 {
42 if(i==1&&j==1)
43 {
44 p->m[i][j]=0;
45 }
46 else p->m[i][j]=1;
47 }
48 }
49 }
50 maxtr quick(maxtr ans ,int m,int mod)
51 {
52 maxtr ak=E();
53 int i,j;
54 while(m)
55 {
56 if(m&1)
57 {
58 maxtr cc;
59 for(i=0; i<2; i++)
60 {
61 for(j=0; j<2; j++)
62 {
63 for(int s=0; s<2; s++)
64 {
65 cc.m[i][j]=(cc.m[i][j]+ans.m[i][s]*ak.m[s][j]%mod)%mod;
66 }
67 }
68 }
69 ak=cc;
70 }
71 maxtr cc;
72 for(i=0; i<2; i++)
73 {
74 for(j=0; j<2; j++)
75 {
76 for(int s=0; s<2; s++)
77 {
78 cc.m[i][j]=(cc.m[i][j]+ans.m[i][s]*ans.m[s][j]%mod)%mod;
79 }
80 }
81 }
82 ans=cc;
83 m/=2;
84 }
85 return ak;
86 }
87 int main(void)
88 {
89 int i,j,k;
90 int s;
91 scanf("%d",&k);
92 int a,b,n,m;
93 for(s=1; s<=k; s++)
94 {
95 scanf("%d %d %d %d",&a,&b,&n,&m);
96 printf("Case %d: ",s);
97 if(n==0)
98 {
99 printf("%d\n",a%m);
100 }
101 else if(n==1)
102 {
103 printf("%d\n",b%m);
104 }
105 else
106 {
107 maxtr ak;
108 Init(&ak);
109 int mod=1;
110 for(i=1;i<=m;i++)
111 mod*=10;
112 ak=quick(ak,n-1,mod);
113 LL ask=ak.m[0][0]*b+ak.m[0][1]*a;
114 ask%=mod;
115 printf("%lld\n",ask);
116 }
117 }
118 return 0;
119 }
1065
1 #include<stdio.h>
2 #include<algorithm>
3 #include<iostream>
4 #include<string.h>
5 #include<stdlib.h>
6 #include<queue>
7 #include<math.h>
8 #include<vector>
9 using namespace std;
10 typedef unsigned long long LL;
11 typedef long long L;
12 typedef struct pp
13 {
14 LL m[4][4];
15 pp()
16 {
17 memset(m,0,sizeof(m));
18 }
19 } maxtr;
20 maxtr E()
21 {
22 int i,j;
23 maxtr ans;
24 for(i=0; i<=3; i++)
25 {
26 for(j=0; j<=3; j++)
27 {
28 if(i==j)
29 ans.m[i][j]=1;
30 else ans.m[i][j]=0;
31 }
32 }
33 return ans;
34 }
35 void Init(maxtr *p,LL x,LL y)
36 {
37 int i,j;
38 memset(p->m,0,sizeof(p->m));
39 p->m[0][0]=x;
40 p->m[0][1]=-y;
41 p->m[1][0]=1;
42 }
43 maxtr quick(maxtr ak,LL m)
44 {
45 int i,j,s;
46 maxtr ac=E();
47
48 while(m)
49 {
50 if(m&1)
51 {
52 maxtr cc;
53 for(i=0; i<2; i++)
54 {
55 for(j=0; j<2; j++)
56 {
57 for(s=0; s<2; s++)
58 {
59 cc.m[i][j]=(cc.m[i][j]+ak.m[i][s]*ac.m[s][j]);
60 }
61 }
62 }
63 ac=cc;
64 }
65 maxtr cc;
66 for(i=0; i<2; i++)
67 {
68 for(j=0; j<2; j++)
69 {
70 for(s=0; s<2; s++)
71 {
72 cc.m[i][j]=(cc.m[i][j]+ak.m[i][s]*ak.m[s][j]);
73 }
74 }
75 }
76 ak=cc;
77 m/=2;
78 }
79 return ac;
80 }
81 int main(void)
82 {
83 int i,j,k;
84 scanf("%d",&k);
85 int s;
86 for(s=1; s<=k; s++)
87 {
88 LL x,y,z;
89 scanf("%llu %llu %llu",&x,&y,&z);
90 LL f1=1;
91 LL f2=x;
92 LL f3=x*x-2*y;
93 maxtr ans;
94 Init(&ans,x,y);
95 printf("Case %d: ",s);
96 if(z==1)
97 {
98 printf("%llu\n",x);
99 }
100 else if(z==2)
101 {
102 printf("%llu\n",f3);
103 }
104 else if(z==0)
105 {
106 printf("2\n");
107 }
108 else
109 {
110 ans= quick(ans,z-2);
111 LL ak=ans.m[0][0]*f3+ans.m[0][1]*f2;
112 printf("%llu\n",ak);
113 }
114 }
115 return 0;
116 }
1070
最新文章
- Intellij IDEA 13.1.3 字体,颜色,风格设置
- 微软How old do I Look——初体验
- 解决 nginx https反向代理http协议 302重定向localtion到http问题
- [置顶] Android开发之serviceManager分析
- 利用Azure Backup备份和恢复虚拟机(2)
- Cramfs、JFFS2、YAFFS2的全面对比
- PHP - 验证类
- UTF8国际通用为什么还要用GBK？
- Pig项目&Spring Boot&Spring Cloud学习
- IntelliJ IDEA 2017版 spring-boot 2.03 去除控制台logo;去除springboot 图标;去除springboot 图
- python基础班-淘宝-目录.txt
- java 集合stream操作
- dll（动态链接库）的编写
- Mac 安装tensorflow
- 为什么要设置Java环境变量（详解）[转]
- Ansible 小手册系列 十八（Lookup 插件）
- 5月15日上课笔记-js中 location对象的属性、document对象、js内置对象、Date事件对象、
- MVC4 路由解析 同名Controller的解决方案
- TCP/IP学习笔记（3）-IP、ARP、RARP协议
- HTML学习-02