NOI12 Day 1 Random Number Generator ( Fast Matrix Multiplication + Fast Multiplication )

PEG Judge - NOI '12 - Random Number Generator
www.2cto.com
See the formulae here. What's particularly interesting in this problem is that it might cause overflow when calculating the product for some long long integers. However, here again we could apply fast multiplication and mod along to get the correct result.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXV = 1e18 + 8;

typedef vector< ll > vec;
typedef vector< vec > mat;

ll m, a, c, x0, n, g;

ll fastmul(ll x, ll y){ // to avoid overflow
    ll res = 0;
    while( y ){
        if( y & 1LL ) ( res += x ) %= m;
        ( x += x ) %= m;
        y >>= 1LL;
    }
    return res;
}

mat mul(const mat &e, const mat &f){
    assert( e[ 0 ].size() == f.size() );
    mat h( e.size(), vec( f[ 0 ].size() ) );
    for(int i = 0; i < e.size(); ++i)
        for(int j = 0; j < f[ 0 ].size(); ++j)
            for(int k = 0; k < f.size(); ++k)
                ( h[ i ][ j ] += fastmul( e[ i ][ k ], f[ k ][ j ] ) ) %= m;
    return h;
}

mat fastpow(mat e, ll p){
    mat f( e.size(), vec( e[ 0 ].size() ) );
    for(int i = 0; i < e.size(); ++i)
        f[ i ][ i ] = 1;
    while( p > 0 ){
        if( p & 1LL ) f = mul( f, e );
        p >>= 1LL;
        e = mul( e, e );
    }
    return f;
}

void solve(){
    mat t( 2, vec( 2 ) );
    t = { { a, c }, { 0, 1 } };
    mat x( 2, vec( 1 ) );
    x = { { x0 }, { 1 } };
    x = mul( fastpow( t, n ), x );
    printf("%lld\n", ( x[ 0 ][ 0 ] % g + g ) % g);
}

int main(){
    scanf("%lld%lld%lld%lld%lld%lld", &m, &a, &c, &x0, &n, &g);
    solve();
    return 0;
}