lightoj 1096 nth term

Problem link

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