1065 - Number Sequence

 

PDF (English)

Statistics

Forum

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
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
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
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
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