CFR 450 B. Jzzhu and Sequences ( Adhoc or Fast matrix multiplication )

Problem - B - Codeforces
Well, though it did not take me much time, it is really silly that I did not realize the sequence will eventually become periodic, thus it is possible to write a solution in less then 10 lines with O( 1 ) time complexity.

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;

typedef vector<int> vec;
typedef vector<vec> mat;

mat mul(mat &a, mat &b){
    assert( a[ 0 ].size() == b.size() );
    mat c( a.size(), vec( b[ 0 ].size() ) );
    for(int k = 0; k < a[ 0 ].size(); ++k)
        for(int i = 0; i < a.size(); ++i)
            for(int j = 0; j < b[ 0 ].size(); ++j)
                ( c[ i ][ j ] += a[ i ][ k ] * b[ k ][ j ] ) %= MOD;
    return c;
}

mat po(mat a, int p){
    mat b( a.size(), vec( a[ 0 ].size() ) );
    for(int i = 0; i < b.size(); ++i)
        b[ i ][ i ] = 1;
    for(int i = p; i > 0; i >>= 1){
        if( i & 1 ) b = mul( b, a );
        a = mul( a, a );
    }
    return b;
}

int x, y, n;

int main(){
    scanf("%d%d%d", &x, &y, &n);
    if( n == 1 ){
        printf("%d\n", ( x + MOD ) % MOD);
        return 0;
    } else if( n == 2 ){
        printf("%d\n", ( y + MOD ) % MOD);
        return 0;
    }
    
    mat t( 2, vec( 2 ) );
    t[ 0 ][ 0 ] = 1, t[ 0 ][ 1 ] = -1;
    t[ 1 ][ 0 ] = 1, t[ 1 ][ 1 ] = 0;
    t = po( t, n - 2 );

    /*
    for(int i = 0; i < 2; ++i)
        for(int j = 0; j < 2; ++j)
            printf("%d%c", t[ i ][ j ], j == 1 ? '\n' : ' ');
    */
    
    mat f( 2, vec( 1 ) );
    f[ 0 ][ 0 ] = y;
    f[ 1 ][ 0 ] = x;
    f = mul( t, f );

    printf("%d\n", ( f[ 0 ][ 0 ] % MOD + MOD ) % MOD );

    return 0;
}