Submission #854655

#	Time	Username	Problem	Language	Result	Execution time	Memory
854655		tibinyte	Brperm (RMI20_brperm)	C++14	100 / 100	1121 ms	167460 KiB

brperm

#include <bits/stdc++.h>
#include "brperm.h"
using namespace std;
ifstream fin("brperm.in");
ofstream fout("brperm.out");
vector<int> bases = {31,29};
const int mod = 1e9 + 7;
const int lgmax = 18;
const int maxn = 5e5;
struct Mint
{
    int val;
    Mint(int x = 0)
    {
        val = x % mod;
    }
    Mint(long long x)
    {
        val = x % mod;
    }
    Mint operator +(Mint oth)
    {
        return val + oth.val;
    }
    Mint operator -(Mint oth)
    {
        return val - oth.val + mod;
    }
    Mint operator *(Mint oth)
    {
        return 1ll * val * oth.val;
    }
};
Mint powmod(int a, int b)
{
    if(b==0)
    {
        return 1;
    }
    if(b%2==1)
    {
        return powmod(a,b-1) * a;
    }
    Mint P = powmod(a,b/2);
    return P * P;
}
Mint dp[2][lgmax+1][maxn+1];
Mint adam[2][lgmax+1][maxn+1];
Mint hashig[2][maxn+1];
Mint powers[2][maxn+1];
Mint inverses[2][maxn+1];
void init(int n, const char S[])
{
    string s;
    for(int i= 0 ; i < n; ++i)
    {
        s+=S[i];
    }
    s = '$' + s;
    for(int t = 0; t < 2; ++t)
    {
        powers[t][0] = 1;
        for(int i=1; i <=n; ++i)
        {
            powers[t][i] = powers[t][i-1] * bases[t];
        }
        inverses[t][0] = 1;
        Mint invbase = powmod(bases[t],mod-2);
        for(int i= 1; i <=n; ++i)
        {
            inverses[t][i] = inverses[t][i-1] * invbase;
        }
        for(int i = 1; i <=n; ++i)
        {
            hashig[t][i] = hashig[t][i-1] + powers[t][i-1] * (s[i]-'a'+1);
        }
    }
    for(int t = 0; t < 2; ++t)
    {
        for(int i=1; i <=n; ++i)
        {
            for(int j = 0; j <= lgmax; ++j)
            {
                dp[t][j][i] = (s[i]-'a'+1);
            }
            adam[t][0][i] = dp[t][0][i];
        }
        for(int j = 1; j <= lgmax; ++j)
        {
            for(int i = 1; i + (1<<j)-1 <= n; ++i)
            {
                Mint mybase = bases[t];
                for(int k = 0; k <= lgmax - j; ++k)
                {
                    dp[t][k][i] = dp[t][k+1][i] + dp[t][k+1][i+(1<<(j-1))] * mybase;
                    mybase = mybase * mybase;
                }
                adam[t][j][i] = dp[t][0][i];
            }
        }
    }
}
int query(int st, int k)
{
    st++;
    int dr = st+(1<<k)-1;
    for(int t = 0; t < 2; ++t){
        Mint x = (hashig[t][dr] - hashig[t][st-1]) * inverses[t][st-1];
        if(x.val != adam[t][k][st].val){
            return false;
        }
    }
    return true;
}

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