This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "brperm.h"
#include <bits/stdc++.h>
using namespace std;
int n;
const long long MOD = 1e9+9;
long long p[530005],invp[530005];
long long put(long long a, long long exp)
{
if(exp==0)
return 1;
if(exp%2==0)
return put(a*a%MOD,exp/2);
else
return put(a*a%MOD,exp/2)*a%MOD;
}
int rev(int x, int k)
{
int aux=0;
for(int i=0;i<k;i++)
if(((1<<i)&x))
aux += (1<<(k-i-1));
return aux;
}
long long hsh[500005][19];
long long normal[500005][19];
long long sump[500005];
void init(int copn, const char s[])
{
n=copn;
p[0]=1;
p[1]=31;
for(int i=2;i<=(1<<19);i++)
p[i] = (p[i-1]*p[1])%MOD;
for(int i=0;i<=(1<<19);i++)
invp[i] = put(p[i],MOD-2);
for(int i=0;i<n;i++)
{
hsh[i][0] = normal[i][0] = s[i];
}
for(int k=1;k<19;k++)
{
for(int i=0;i+(1<<k)-1<n;i++)
{
hsh[i][k] = (hsh[i][k-1] + hsh[i+(1<<(k-1))][k-1]*p[(1<<(18-k))])%MOD;
//for(int j=0;j<(1<<k);j++) normal[i][k] = (normal[i][k] + s[i+j]*p[j*(1<<(18-k))])%MOD;
}
long long pref=0;
long long prod=1;
for(int i=0;i<n;i++)
{
pref = (pref + 1LL*s[i]*prod)%MOD;
sump[i] = pref;
prod = prod*p[(1<<(18-k))]%MOD;
}
prod=1;
for(int i=0;i+(1<<k)-1<n;i++)
{
normal[i][k] = sump[i+(1<<k)-1];
if(i>0) normal[i][k] = (normal[i][k] + MOD - sump[i-1])%MOD;
normal[i][k] = normal[i][k]*prod%MOD;
prod = prod * invp[(1<<(18-k))]%MOD;
}
}
}
int query(int i, int k)
{
if(i+(1<<k)-1 >= n)
return 0;
return hsh[i][k] == normal[i][k];
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |