lightoj 1065 Number sequence

Problem link

1. 
   
2. #include <bits/stdc++.h>
3. using namespace std;
4. #define llu long long unsigned
5. llu c[2][2];
6. int MOD;
7. void mul(llu a[2][2],llu b[2][2]){
8.     memset(c, 0, sizeof(c));
9.     for(int i = 0; i <2; i++){
10.         for(int j = 0; j <2; j++){
11.             for(int k = 0; k <2; k++){
12.                 c[i][j]+= ((a[i][k]%MOD)*(b[k][j]%MOD))%MOD;
13.                 c[j][j]%=MOD;
14.             }
15.         }
16.     }
17.     for(int i = 0; i <2; i++){
18.         for(int j = 0; j <2; j++){
19.             a[i][j] = c[i][j]%MOD;
20.         }
21.     }
22. }
23. void ans(llu a[2][2], int n){
24.     llu m[2][2] = {{1, 1}, {1,0}};
25.     if(n == 1) return;
26.     ans(a, n/2);
27.     mul(a, a);
28.     if(n%2) mul(a, m);
29. }
30. int main(){
31.     int ts;
32.     scanf("%d", &ts);
33.     for(int p = 1; p <= ts; p++){
34.     llu f[2][2] = {{1, 1}, {1,0}};
35.     int a, b, n, m, answer;
36.     MOD = 1;
37.     scanf("%d%d%d%d",&a, &b, &n, &m);
38.     for(int i = 1; i<=m; i++) MOD*=10;
39.     if(n == 0) answer = a;
40.     else if(n == 1) answer  = b;
41.     else if(n>1) ans(f, n-1), answer = (b*f[0][0]+a*f[0][1])%MOD;
42.     printf("Case %d: %d\n", p,answer%MOD );
43.     }
44.     return 0;
45. }