Submission #854644

#	Time	Username	Problem	Language	Result	Execution time	Memory
854644		tibinyte	Brperm (RMI20_brperm)	C++14	0 / 100	593 ms	90916 KiB

brperm

#include <bits/stdc++.h>
using namespace std;
const int base = 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[lgmax+1][maxn+1];
Mint adam[lgmax+1][maxn+1];
Mint hashig[maxn+1];
Mint powers[maxn+1];
Mint inverses[maxn+1];
void init(int n, const char S[])
{
    string s;
    for(int i= 0 ; i < n; ++i){
        s+=S[i];
    }
    s = '$' + s;
    powers[0] = 1;
    for(int i=1; i <=n; ++i){
        powers[i] = powers[i-1] * base;
    }
    inverses[0] = 1;
    Mint invbase = powmod(base,mod-2);
    for(int i= 1; i <=n; ++i){
        inverses[i] = inverses[i-1] * invbase;
    }
    for(int i = 1; i <=n; ++i){
        hashig[i] = hashig[i-1] + powers[i-1] * (s[i]-'a'+1);
    }
    for(int i=1; i <=n; ++i){
        for(int j = 0; j <= lgmax; ++j){
            dp[j][i] = (s[i]-'a'+1);
        }
        adam[0][i] = dp[0][i];
    }
    for(int j = 1; j <= lgmax; ++j){
        for(int i = 1; i + (1<<j)-1 <= n; ++i){
            Mint mybase = base;
            for(int k = 0; k <= lgmax - j; ++k){
                dp[k][i] = dp[k+1][i] + dp[k+1][i+(1<<(j-1))] * mybase;
                mybase = mybase * mybase;
            }
            adam[j][i] = dp[0][i];
        }
    }
}
bool query(int st, int k)
{
    st++;
    int dr = st+(1<<k)-1;
    Mint x = (hashig[dr] - hashig[st-1]) * inverses[st-1];
    return x.val == adam[k][st].val;
}

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