HR Find the Seed ( DP + Matrix Inverse - Gauss Elimination )

https://www.hackerrank.com/challenges/find-the-seed
F( n ) = c( 1 ) * F( n - 1 ) + c( 2 ) * F( n - 2 ) .. + c( n ) * F( 0 ) =>
c( n ) * F( 0 ) = F( n ) - c( 1 ) * F( n - 1 ) - c( 2 ) * F( n - 2 ) .. - c( n - 1 ) * F( 1 ) =>
F( 0 ) = inverse( c( n ) ) * ( F( n ) - c( 1 ) * F( n - 1 ) - c( 2 ) * F( n - 2 ) .. - c( n - 1 ) * F( 1 ) ) => ( let z = inv( c( n ) ) )
F( 0 ) = z * F( n ) - z * c( 1 ) * F( n - 1 ) - z * c( 2 ) * F( n - 2 ) .. - z * c( n - 1 ) * F( 1 )
Keep iterating with this matrix, and the answer will be found.
However, the official solution is to find the matrix inverse.
I took the source code of Gauss-Jordan elimination for matrix inverse from this site :
2 実際のプログラム(手取り足取り), which indeed helped a lot with understanding the algorithm as well.
Another thing to mention is that, when the determinant of a matrix is 0, it shows that some rows are parallel in vector ( meaning at least one row in the matrix is a multiple of another row in the matrix ), and will not have an inverse ( somewhat like having infinitely many solutions to some simultaneous equations. However, for the matrix in this problem, the first row will have all elements greater than 0, and each other row has only 1 in a unique position, therefore no rows will be equivalent ( parallel ) to another, thus no need to worry of having no inverse.

// NO MATRIX INVERSE
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50 + 2;
const int MAXK = 1e9 + 9;
const int MOD = 1e9 + 7;

void printmat( const vector< vector< int > > &mat ){ // for debug
    for( int i = 0; i < mat.size(); ++i, puts( "" ) )
        for( int j = 0; j < mat[ i ].size(); ++j )
            printf( "%d ", mat[ i ][ j ] );
}

int N, K;
int F[ MAXN ];
int C[ MAXN ];

int fastpow( int v, int p ){
    int res = 1;
    while( p ){
        if( p & 1 ) res = 1LL * res * v % MOD;
        p >>= 1;
        v = 1LL * v * v % MOD;
    }
    return res;
}

int inv( int n ){
    return fastpow( n, MOD - 2 );
}

vector< vector< int> > matmul( const vector< vector< int > > &a, const vector< vector< int > > &b ){
    assert( a[ 0 ].size() == b.size() );
    vector< vector< int > > res( a.size(), vector< int >( b[ 0 ].size() ) );
    for( int i = 0; i < a.size(); ++i )
        for( int j = 0; j < b[ 0 ].size(); ++j )
            for( int k = 0; k < a[ 0 ].size(); ++k )
                ( res[ i ][ j ] += 1LL * a[ i ][ k ] * b[ k ][ j ] % MOD ) %= MOD;
    return res;
}

vector< vector< int > > matpow( vector< vector< int > > a, int p ){
    assert( a.size() == a[ 0 ].size() );
    vector< vector< int > > res( a.size(), vector< int >( a[ 0 ].size() ) );
    for( int i = 0; i < a.size(); ++i )
        res[ i ][ i ] = 1;
    while( p ){
        if( p & 1 ) res = matmul( res, a );
        p >>= 1;
        a = matmul( a, a );
    }
    return res;
}

void solve(){
    vector< vector< int > > tmat( N, vector< int >( N ) );
    int z = inv( C[ N - 1 ] );
    for( int i = 0; i < N - 1; ++i )
        tmat[ 0 ][ i ] = ( ( 1LL * z * -C[ N - 2 - i ] % MOD ) + MOD ) % MOD;
    tmat[ 0 ][ N - 1 ] = z;
    for( int i = 0; i < N - 1; ++i )
        tmat[ i + 1 ][ i ] = 1;
    vector< vector< int > > f( N, vector< int >( 1 ) );
    for( int i = 0; i < N; ++i )
        f[ i ][ 0 ] = F[ N - 1 - i ];
    vector< vector< int > > ans = matmul( matpow( tmat, K - N + 1 ), f );
    for( int i = N - 1; i >= 0; --i )
        printf( "%d%c", ans[ i ][ 0 ], i == 0 ? '\n' : ' ' );
}

int main(){
    scanf( "%d%d", &N, &K );
    for( int i = 0; i < N; ++i )
        scanf( "%d", F + i );
    for( int i = 0; i < N; ++i )
        scanf( "%d", C + i );
    solve();
    return 0;
}

// MATRIX INVERSE
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50 + 2;
const int MAXK = 1e9 + 9;
const int MOD = 1e9 + 7;

int N, K;
int F[ MAXN ];
int C[ MAXN ];

int intPow( int v, int p ){
    int res = 1;
    while( p ){
        if( p & 1 ) res = 1LL * res * v % MOD;
        p >>= 1;
        v = 1LL * v * v % MOD;
    }
    return res;
}

int intInv( int v ){
    return intPow( v, MOD - 2 );
}

vector< vector< int > > matMul( const vector< vector< int > > &a, const vector< vector< int > > &b ){
    assert( a[ 0 ].size() == b.size() );
    vector< vector< int > > res( a.size(), vector< int >( b[ 0 ].size() ) );
    for( int i = 0; i < a.size(); ++i )
        for( int j = 0; j < b[ 0 ].size(); ++j )
            for( int k = 0; k < a[ 0 ].size(); ++k )
                ( res[ i ][ j ] += 1LL * a[ i ][ k ] * b[ k ][ j ] % MOD ) %= MOD;
    return res;
}

vector< vector< int > > matPow( vector< vector< int > > a, int p ){
    assert( a.size() == a[ 0 ].size() );
    vector< vector< int > > res( a.size(), vector< int >( a[ 0 ].size() ) );
    for( int i = 0; i < a.size(); ++i )
        res[ i ][ i ] = 1;
    while( p ){
        if( p & 1 ) res = matMul( res, a );
        p >>= 1;
        a = matMul( a, a );
    }
    return res;
}

vector< vector< int > > matInv( vector< vector< int > > a ){
    assert( a.size() == a[ 0 ].size() );
    vector< vector< int > > res( a.size(), vector< int >( a[ 0 ].size() ) );
    for( int i = 0; i < a.size(); ++i )
        res[ i ][ i ] = 1;
    vector< int > row( a.size() ), b( a.size() );
    for( int ipv = 0; ipv < a.size(); ++ipv ){
        int maxv = 0; // finding maximum value
        int pivot_row = -1;
        for( int i = ipv; i < a.size(); ++i )
            if( a[ i ][ ipv ] > maxv )
                maxv = a[ i ][ ipv ],
                pivot_row = i;
        assert( maxv != 0 );
        row[ ipv ] = pivot_row; // exchanging rows
        if( ipv != pivot_row ){
            for( int i = 0; i < a.size(); ++i )
                swap( a[ ipv ][ i ], a[ pivot_row ][ i ] ),
                swap( res[ ipv ][ i ], res[ pivot_row ][ i ] );
            swap( b[ ipv ], b[ pivot_row ] );
        }
        int inv_pivot = intInv( a[ ipv ][ ipv ] ); // 對角成分 = 1 pivotの処理
        for( int j = 0; j < a.size(); ++j )
            a[ ipv ][ j ] = 1LL * a[ ipv ][ j ] * inv_pivot % MOD,
            res[ ipv ][ j ] = 1LL * res[ ipv ][ j ] * inv_pivot % MOD;
        for( int i = 0; i < a.size(); ++i ) // pivot column = 0, !pivot
            if( i != ipv ){
                int tmp = a[ i ][ ipv ];
                for( int j = 0; j < a.size(); ++j )
                    ( ( ( a[ i ][ j ] -= 1LL * tmp * a[ ipv ][ j ] % MOD ) %= MOD ) += MOD ) %= MOD,
                    ( ( ( res[ i ][ j ] -= 1LL * tmp * res[ ipv ][ j ] % MOD ) %= MOD ) += MOD ) %= MOD;
                ( ( ( b[ i ] -= 1LL * tmp * b[ ipv ] % MOD ) %= MOD ) += MOD ) %= MOD;
            }
    }
    return res;
}

void solve(){
    vector< vector< int > > tmat( N, vector< int >( N ) );
    for( int i = 0; i < N; ++i )
        tmat[ 0 ][ i ] = C[ i ];
    for( int i = 0; i < N - 1; ++i )
        tmat[ i + 1 ][ i ] = 1;
    vector< vector< int > > inv = matInv( tmat );
    vector< vector< int > > f( N, vector< int >( 1 ) );
    for( int i = 0; i < N; ++i )
        f[ i ][ 0 ] = F[ i ];
    vector< vector< int > > ans = matMul( matPow( inv, K - N + 1 ), f );
    for( int i = 0; i < N; ++i )
        printf( "%d%c", ans[ i ][ 0 ], i == N - 1 ? '\n' : ' ' );
}

int main(){
    scanf( "%d%d", &N, &K );
    for( int i = 0; i < N; ++i )
        scanf( "%d", F + i );
    for( int i = 0; i < N; ++i )
        scanf( "%d", C + i );    solve();
    return 0;