제출 #642131

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
642131		Tenis0206	Brperm (RMI20_brperm)	C++14	0 / 100	458 ms	201816 KiB

brperm

#include <bits/stdc++.h>

//#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];

long long put[500005];
long long hr[500005][25];
long long h[500005][25];

int lg = 0;

long long lgput(int x, int y)
{
    long long 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 * (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] = (1LL * 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] - 1LL * h[st-1][p] * lgput(b, (1LL<<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

• Subtask 1: 0 / 13
• Subtask 2: 0 / 37
• Subtask 3: 0 / 17
• Subtask 4: 0 / 33