[Light OJ] 1131 - Just Two Functions

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 1131 - Just Two Functions
Source            : UVA Online Judge
Category          : Linear Algebra
Algorithm         : Matrix Exponentiation
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define For(i, n)             for (int i = 0; i < n; i++)  
#define FOR(i, n)             for (int i = 1; i <= n; i++)  
#define REP(i, a, b)          for (int i = a; i <= b; i++)  
  
#define ll                    long long int  
  
ll mod;  
ll f[4], g[4];  
ll a[2], b[2];  
ll c[2];  
  
struct Mat  
{  
      int row, col;  
      ll v[7][7];  
      Mat(int row = 0, int col = 0)  
      {  
            this->row = row;  
            this->col = col;  
            For(i, 6) For(j, 6) v[i][j] = 0;  
            v[0][0] = a[0];  
            v[0][1] = b[0];  
            v[0][5] = c[0];  
            v[1][0] = 1;  
            v[2][1] = 1;  
            v[3][2] = c[1];  
            v[3][3] = a[1];  
            v[3][4] = b[1];  
            v[4][3] = 1;  
            v[5][4] = 1;  
      }  
      inline Mat multiply(const Mat &A, const Mat &B)  
      {  
            Mat ret;  
            ret.row = A.row;  
            ret.col = B.col;  
            For(i, ret.row)  
            {  
                  For(j, ret.col)  
                  {  
                        ll sum = 0;  
                        For(k, A.col)  
                        {  
                              sum += (A.v[i][k] % mod * B.v[k][j] % mod) % mod;  
                              sum %= mod;  
                        }  
                        ret.v[i][j] = sum;  
                  }  
            }  
            return ret;  
      }  
      inline Mat modPow(Mat mat, ll p)  
      {  
            if (p == 1) return mat;  
            if (p & 1) return mat.multiply(mat, modPow(mat, p-1));  
            Mat ret = modPow(mat, p >> 1);  
            return ret.multiply(ret, ret);  
      }  
      inline void getRes()  
      {  
            ll fn = 0;  
            fn = (fn + (v[0][0] * f[2]) % mod) % mod;  
            fn = (fn + (v[0][1] * f[1]) % mod) % mod;  
            fn = (fn + (v[0][2] * f[0]) % mod) % mod;  
            fn = (fn + (v[0][3] * g[2]) % mod) % mod;  
            fn = (fn + (v[0][4] * g[1]) % mod) % mod;  
            fn = (fn + (v[0][5] * g[0]) % mod) % mod;  
  
            ll gn = 0;  
            gn = (gn + (v[3][0] * f[2]) % mod) % mod;  
            gn = (gn + (v[3][1] * f[1]) % mod) % mod;  
            gn = (gn + (v[3][2] * f[0]) % mod) % mod;  
            gn = (gn + (v[3][3] * g[2]) % mod) % mod;  
            gn = (gn + (v[3][4] * g[1]) % mod) % mod;  
            gn = (gn + (v[3][5] * g[0]) % mod) % mod;  
  
            printf("%lld %lld\n", fn, gn);  
      }  
};  
  
inline void res(int n)  
{  
      printf("%lld %lld\n", f[n] % mod, g[n] % mod);  
}  
  
int main()  
{  
      int tc;  
      scanf("%d", &tc);  
      FOR(tcase, tc)  
      {  
            scanf("%lld %lld %lld", &a[0], &b[0], &c[0]);  
            scanf("%lld %lld %lld", &a[1], &b[1], &c[1]);  
            scanf("%lld %lld %lld", &f[0], &f[1], &f[2]);  
            scanf("%lld %lld %lld", &g[0], &g[1], &g[2]);  
            scanf("%lld", &mod);  
            printf("Case %d:\n", tcase);  
            int q;  
            scanf("%d", &q);  
            FOR(_q, q)  
            {  
                  ll n;  
                  scanf("%lld", &n);  
                  if (n <= 2)  
                  {  
                        res(n);  
                        continue;  
                  }  
                  Mat mat(6, 6);  
                  mat = mat.modPow(mat, n-2);  
                  mat.getRes();  
            }  
      }  
}