P2044 [NOI2012] 随机数生成器

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
ll mod , a , c , x , n , g;
namespace ksc{
    ll ksc ( ll x , ll y )
    {
        ll res=0;
        while ( y )
        {
            if ( y & 1 )
                res = res + x , res %= mod;
            x <<= 1;
            x%=mod;
            y >>= 1;
        }
        return res;
    }
}
struct jz
{
    ll matix [ 3 ] [ 3 ] ;
    ll n,m;
    jz(){memset ( matix , 0 , sizeof ( matix ) ); n = m = 0 ; }
    void init ()
    {
        matix [ 1 ] [ 1 ] = matix [ 2 ] [ 2 ] = 1;
        n = m = 2;
    }
};
namespace jzcf
{
    jz cf ( jz x , jz y )
    {
        jz z;
        for ( int i = 1; i <= x.n; i ++ )
        for ( int j = 1; j <= y.m; j ++ )
        {
            for ( int k = 1; k <= x.m; k ++ )
                z . matix [ i ] [ j ] += ksc :: ksc ( x . matix [ i ] [ k ] , y . matix [ k ] [ j ] ),z . matix [ i ] [ j ] %=mod;
        }
        z . n = x . n;
        z . m = y . m;
        return z;
    }
    jz ksm ( jz x , ll y )
    {
        jz z;
        z . init();
        while ( y )
        {
            if ( y & 1 ) z = cf ( x , z );
            x = cf ( x , x );
            y >>= 1;
        }
        return z;
    }
}
int main()
{
    //freopen ( "text.in" , "r" , stdin );
    cin >> mod >> a >> c >> x >> n >> g ;
    jz ans , basic;
    ans . matix [ 1 ] [ 1 ] = x;
    ans . matix [ 1 ] [ 2 ] = c;
    basic . matix [ 1 ] [ 1 ] = a;
    basic . matix [ 1 ] [ 2 ] = 0;
    basic . matix [ 2 ] [ 1 ] = 1;
    basic . matix [ 2 ] [ 2 ] = 1;
    ans . n = 1;
    ans . m = 2;
    basic . n = basic . m = 2;
    basic = jzcf :: ksm( basic , n ) ;
    ans = jzcf :: cf ( ans , basic );
    cout << ans . matix [ 1 ] [ 1 ] % g << endl;
    return 0;
}