struct SequenceHash

{

vector<long long> prefixHash, powers;

SequenceHash(const vector<int>& seq)

{

int L = seq.size();

prefixHash.resize(L+1); powers.resize(L+1);

prefixHash[0] = 0LL; powers[0] = 1LL;

for(int i = 1; i <= L;i++)

{

prefixHash[i] = prefixHash[i-1] * 31LL + seq[i-1];

powers[i] = powers[i-1] * 31LL;

}

}

long long hash(int a, int b) // Returns hash code for seq[a..b], both endpoints inclusive

{

return prefixHash[b+1] - prefixHash[a] * powers[b-a+1];

}

};

int main()

{

//Example usage

int A[] = { 1, 2, 3, 1, 2, 3};

SequenceHash sh(VI(A)); // Just instantiate the SequenceHash

assert( sh.hash(0,2) == sh.hash(3,5));

}