Cod sursa(job #1683889)

Utilizator arhivamanArhiva Man arhivaman Data 10 aprilie 2016 17:10:49
Problema Rsir Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <fstream>

#define modMax 7005
using namespace std;
ifstream fin("rsir.in");
ofstream fout("rsir.out");
int A, B, X, Y, Z, MOD;
long long n;
int mod1[modMax], mod2[modMax];
pair<int, int> getNext(pair<int, int> state)
{
    pair<int, int> ans;

    ans.second=mod1[state.first]+mod2[state.second];
    if(ans.second>=MOD)
        ans.second-=MOD;
    ans.first=state.second;

    return ans;
}
int main()
{
    pair<int, int> initialState;
    pair<int, int> stateA, stateB;

    fin>>initialState.first>>initialState.second>>A>>B>>X>>Y>>Z>>MOD>>n;
    initialState.first%=MOD;
    initialState.second%=MOD;

    for(int i=0;i<MOD;i++)
    {
        mod1[i]=1LL*(A * i * i + X * i + Z)%MOD;
        mod2[i]=1LL*(B * i * i + Y * i)%MOD;
    }

    stateA=stateB=initialState;

    for(int j=1;j<n;j++)
    {
        stateA=getNext(stateA);
        stateB=getNext(getNext(stateB));

        if(stateA!=stateB)
            continue;

        stateA=getNext(stateA);
        int cycleLen=1;

        while(stateA!=stateB)
        {
            cycleLen++;
            stateA=getNext(stateA);
        }

        stateA=stateB=initialState;
        for(int i=1;i<=cycleLen;i++)
            stateA=getNext(stateA);

        int tailLen=0;
        while(stateA!=stateB)
        {
            tailLen++;
            stateA=getNext(stateA);
            stateB=getNext(stateB);
        }

        n-=tailLen;
        n--;

        n%=cycleLen;

        stateA=initialState;

        for(int i=1;i<=n;i++)
            stateA=getNext(stateA);

        fout<<stateA.second;
        return 0;
    }
    fout<<stateA.second;
    return 0;
}