LimitedMemorySeries2.cpp

long long a, b;

long long next_(long long x)
{
    return ((x^a)+b) & ((1LL<<50)-1);
}

long long back_(long long x)
{
    return ((x+(1LL<<50)-b)^a) & ((1LL<<50)-1);
}

class LimitedMemorySeries2{public:
int getSum( int n, long long x0, long long a, long long b )
{
    ::a = a;
    ::b = b;
    long long ans = 0;
    long long x = x0;

    for (int i=0; i<n; i++)
    {
        int k = 0;
        long long xl = x;
        long long xr = x;
        while (0<=i-k && i+k<n && (k==0 || (x>xl && x>xr)))
        {
            xl = back_(xl);
            xr = next_(xr);
            k++;
        }
        ans += k-1;
        x = next_(x);
    }
    return (int)(ans%1000000007);
}};