#include "function.h"
/*
F(N,M)=1 if M <= N,
F(N,M)=F(N,M-1)+F(N,M-2)+...+F(N,M-N) if M > N
let M(n) be the matrix defined by M(n)_i,j=
1 if j=i+1 for all i from 0 to N-2
0 else
Then, M(N)[F(N,m) F(N,m+1)...F(N,m+N)]^T=[F(N,m+1) F(N,m+2)...F(N,m+N+1)]^T
M(N)[F(N,0) F(N,1)...F(N,N)]^T=[F(N,1) F(N,2)...F(N,N+1)]^T for m=0
M(N)^(M-N)[F(N,0) F(N,1)...F(N,N)]^T=[F(N,M-N) F(N,2)...F(N,M)]^T
M(N)^(M-N)[1 1...1]^T=[F(N,M-N) F(N,2)...F(N,M)]^T
F(N,M)=row_(N-1)(M(N)^(M-N))dot([1 1...1])
F(N,M)=M(N)^(M-N)_(N-1),0+M(N)^(M-N)_(N-1),1+...M(N)^(M-N)_(N-1),(N-1)
*/
Matrix::~Matrix(){    //沒有錯
    for(int i=0;i<n;i++)
        delete matrix[i];
    delete matrix;
}
Matrix::Matrix(int n):n(n){
    matrix=new long long* [n];
    for(int i=0;i<n;i++)
        matrix[i]=new long long [n];
    toZero();
}
long long& Matrix::operator()(const int& row, const int& column) const{return matrix[row][column];}
Matrix::Matrix(const Matrix& ref){
    n = ref.n;
    matrix = new long long*[n];
    for(int i=0; i<n; i++)
        matrix[i] = new long long[n];
    //matrix = ref.matrix; 

    //讓this.matrix=ref.matrix，代表讓兩者指向相同位址，共用同一個空間
    //應該讓兩者有各自獨立的空間，才不會互相影響
    //此處的錯誤會導致destructor正確釋放空間反而讓code無法AC
    //以下才是正確寫法

    for(int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            matrix[i][j] = ref.matrix[i][j];
        }
    }
}

Matrix& Matrix::operator=(const Matrix& ref){
    n = ref.n;
    for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        matrix[i][j] = ref.matrix[i][j];
    return *this;
}
void Matrix::toIdentity(){//toIdentity won't literally let a matrix be a identity matrix  
    for(int i=0;i<n-1;i++)//this is just a trick for partial judge
        matrix[i][i+1]=1;
    for(int j=0;j<n;j++)
        matrix[n-1][j]=1;
}
Matrix Matrix::operator*(const Matrix& rhs)const{
    Matrix product(n);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            for(int k=0;k<n;k++){
                product(i,j)+=(*this)(i,k)*rhs(k,j);
                product(i,j)%=mod;
            }
    return product;
}
Matrix Matrix::power(int k)const{
    if(k==1) return *this;    //沒有錯
    Matrix temp=power(k/2);
    temp=temp*temp;
    if(k%2) return *this*temp;
    return temp;
}
Matrix constructMatrix(int n){
    Matrix M(n);
    M.toIdentity();
    return M;
}

//Matrix::Matrix(const Matrix& ref){*this=ref;}

//此為錯誤寫法，*this=ref代表兩者指向的位址相同，共用相同的空間
//此處copy contructor的目的是建立一個全新的物件，這個全新的物件相當於已存在物件的副本
//新的物件和舊的物件，兩者的空間應該要是獨立的