| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 642122 | Tenis0206 | Brperm (RMI20_brperm) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define int long long
//#define home
#ifndef home
#include "brperm.h"
#endif // home
using namespace std;
const int Mod = 1e9;
const int b = 27;
int n;
char c[500005];
int put[500005];
int hr[500005][25];
int h[500005][25];
int lg = 0;
int lgput(int x, int y)
{
int p = 1;
while(y)
{
if(y % 2 == 0)
{
y /= 2;
x = 1LL * x * x % Mod;
}
else
{
--y;
p = 1LL * p * x % Mod;
}
}
return p;
}
void build_hr()
{
for(int i=1;i<=n;i++)
{
hr[i][0] = (c[i] - 'a' + 1);
}
for(int k=1;k<=lg;k++)
{
for(int i=1;i<=n;i++)
{
if(i + (1<<k) - 1 > n)
{
break;
}
hr[i][k] = 1LL * (put[(1<<(lg-k))] * hr[i][k-1] + hr[i + (1<<(k-1))][k-1]) % Mod;
}
}
}
void build_h()
{
for(int k=0;k<=lg;k++)
{
for(int i=1;i<=n;i++)
{
h[i][k] = (h[i-1][k] * put[(1<<k)] + c[i] - 'a' + 1) % Mod;
}
}
}
int get_hash(int st, int k)
{
int p = lg - k;
int dr = st + (1<<k) - 1;
return (h[dr][p] - h[st-1][p] * lgput(b, (1<<p) * (dr - st + 1)) % Mod + Mod) % Mod;
}
void init(int N, const char s[])
{
n = N;
put[0] = 1;
for(int i=1;i<=n;i++)
{
put[i] = 1LL * put[i-1] * b % Mod;
}
for(int i=1;i<=n;i++)
{
c[i] = s[i-1];
}
int nr = 1;
while(nr<=n)
{
++lg;
nr = 2 * nr;
}
--lg;
build_hr();
build_h();
}
int query(int poz, int k)
{
++poz;
return (hr[poz][k]==get_hash(poz,k));
}
#ifdef home
int nn,qq;
char ss[500005];
signed main()
{
freopen("nr.in","r",stdin);
freopen("nr.out","w",stdout);
cin>>nn;
for(int i=0;i<nn;i++)
{
cin>>ss[i];
}
init(nn,ss);
cin>>qq;
for(int i=1;i<=qq;i++)
{
int poz,k;
cin>>poz>>k;
cout<<query(poz,k)<<'\n';
}
return 0;
}
#endif // home