Submission #746982

#	Time	Username	Problem	Language	Result	Execution time	Memory
746982		doowey	Brperm (RMI20_brperm)	C++14	100 / 100	345 ms	83580 KiB

brperm

#include <bits/stdc++.h>
#include "brperm.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

const int MOD = (int)1e9 + 9;
const int N = (int)5e5 + 10;
const int B = 77;
const int K = 20;
const int M = (1 << K) + 1;
int pwr[M];
int F[K][N];
int G[K][N];

int powr(int m, int k){
    if(k == 0) return 1;
    int p = powr(m, k / 2);
    p = (p * 1ll * p) % MOD;
    if(k % 2 == 1) p = (p * 1ll * m) % MOD;
    return p;
}

int mult(int x, int y){
    return (x * 1ll * y) % MOD;
}

int add(int x, int y){
    x += y;
    if(x >= MOD) x -= MOD;
    else if(x < 0) x += MOD;
    return x;
}

int n;

void init(int _n, const char s[]) {
    pwr[0] = 1;
    n = _n;
    for(int i = 1; i <= (1 << K); i ++ ){
        pwr[i] = (pwr[i - 1] * 1ll * B) % MOD;
    }
    int chum;
    for(int i = 0 ; i < K; i ++ ){
        if((1 << i) <= n){
            chum = 0;
            for(int j = n - 1; j >= 0 ; j -- ){
                chum = mult(chum, pwr[(1 << (K - i))]);
                chum = add(chum, s[j] - 'a' + 1);
                F[i][j] = chum;
            }
            if(i == 0){
                for(int j = 0 ; j < n; j ++ ){
                    G[i][j] = s[j] - 'a' + 1;
                }
            }
            else{
                for(int j = 0; j + (1 << i) - 1 < n; j ++ ){
                    G[i][j] = add(G[i - 1][j], mult(G[i - 1][j + (1 << (i - 1))], pwr[(1 << (K - i))]));
                }
            }
        }
    }
}

int calcF(int i, int k){
    return add(F[k][i],-mult(F[k][i+(1<<k)],powr(pwr[(1<<(K-k))], (1 << k))));
}

int query(int i, int k) {
    if(i + (1 << k) - 1 >= n) return 0;
    return (G[k][i] == calcF(i, k));
}

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