[UVa] 13298 - Fibonacci Family Formula

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 13298 - Fibonacci Family Formula
Source            : UVA Online Judge
Category          : Linear Algebra
Algorithm         : Matrix Exponentiation
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define ll         long long int  
#define mod        1000000009  
  
static const int maxn = 100 + 2;  
  
struct Mat  
{  
      int row, column;  
      ll v[maxn][maxn];  
};  
  
inline Mat multiply(const Mat &A, const Mat &B)  
{  
      Mat ret;  
      ret.row = A.row;  
      ret.column = B.column;  
      for (int i = 0; i < A.row; i++)  
      {  
            for (int j = 0; j < B.column; j++)  
            {  
                  ll sum = 0;  
                  for (int k = 0; k < A.column; k++)  
                  {  
                        sum += (A.v[i][k] * B.v[k][j]) % 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 multiply(mat, modPow(mat, p-1));  
      Mat ret = modPow(mat, p >> 1);  
      return multiply(ret, ret);  
}  
  
ll arr[maxn];  
  
inline void Array(int k)  
{  
      arr[0] = 1;  
      for (int i = 1; i < maxn; i++)  
      {  
            int temp = k;  
            arr[i] = 0;  
            for (int j = i-1; j >= 0 && temp; j--)  
            {  
                  arr[i] = (arr[i] + arr[j]) % mod;  
                  --temp;  
            }  
      }  
}  
  
int main()  
{  
      // freopen("in.txt", "r", stdin);  
      int k;  
      ll n;  
      while (scanf("%d %lld", &k, &n) == 2)  
      {  
            if (k == 0 && n == 0) break;  
            Mat mat;  
            mat.row = k;  
            mat.column = k;  
            Array(k);  
            for (int i = 0; i < k; i++)  
            {  
                  for (int j = 0; j < k; j++)  
                  {  
                        mat.v[i][j] = 0;  
                        if (i == 0) mat.v[i][j] = 1;  
                        else if (i == j + 1) mat.v[i][j] = 1;  
                  }  
            }  
            if (n <= k)  
            {  
                  printf("%lld\n", arr[n]);  
            }  
            else  
            {  
                  mat = modPow(mat, n-k+1);  
                  ll sum = 0;  
                  for (int i = 0; i < k; i++)  
                  {  
                        sum += (mat.v[0][i] * arr[k-1-i]) % mod;  
                        sum %= mod;  
                  }  
                  printf("%lld\n", sum);  
            }  
      }  
}