Submission #746335

#	Time	Username	Problem	Language	Result	Execution time	Memory
746335		doowey	Brperm (RMI20_brperm)	C++14	0 / 100	25 ms	5460 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 K = 19;
const int B = 77;
vector<char> S;
int dp[N][K][K];
int pwr[N];

int make(int i, int step, int lim){
    if(dp[i][step][lim] != 0) return dp[i][step][lim];
    if(step == lim){
        //cout << i << " ";
        return S[i] - 'a' + 1;
    }
    int lef, rig;
    lef = make(i, step + 1, lim);
    rig = make(i + (1 << step), step + 1, lim);
    //cout << "merge: " << lef << " + " << rig << "\n";
    lef += (rig * 1ll * pwr[(1<<(lim-step - 1))]) % MOD;
    if(lef >= MOD) lef -= MOD;
    return dp[i][step][lim]=lef;
}

int H[N][K];

int make2(int i, int step){
    if(H[i][step] != 0) return H[i][step];
    if(step == 0){
        return S[i] - 'a' + 1;
    }
    int lef = make2(i, step - 1);
    int rig = make2(i + (1 << (step - 1)), step - 1);
    lef += (rig * 1ll * pwr[(1 << (step - 1))]) % MOD;
    if(lef >= MOD) lef -= MOD;
    return H[i][step] = lef;
}

void init(int n, const char s[]) {
    pwr[0] = 1;
    for(int i = 1; i <= n; i ++ ) pwr[i] = (pwr[i - 1] * 1ll * B) % MOD;
    for(int i = 0 ; i < n; i ++ ){
        S.push_back(s[i]);
    }
}

int query(int i, int k) {
    //int ca = make(i, 0, k);
    //int cb = make2(i, k);
    int sz = (1 << k);
    vector<char> A(sz), B(sz);
    for(int j = 0 ; j < sz; j ++ ){
        A[j] = S[i + j];
        int f = 0;
        for(int p = 0; p < k ; p ++ ){
            if((j & (1 << p))){
                f |= (1 << (k - p - 1));
            }
        }
        B[f] = S[i + j];
    }

    //cout << ca << " " << cb << " |\n";
    return (A == B);
}

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