Submission #596605

#	Time	Username	Problem	Language	Result	Execution time	Memory
596605		CaroLinda	Brperm (RMI20_brperm)	C++14	0 / 100	225 ms	231440 KiB

brperm

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

#define all(x) (x.begin(),x.end())
#define ll long long

const ll PRIME = 37LL;
const ll MOD = 1e9+7;
const int LOG = 20;
const int MAXN = 5e5+10;

using namespace std;

int dp[LOG][MAXN];
ll invPot[LOG][MAXN], sv[LOG][MAXN], pot2[LOG][LOG];
int token;
int N;

ll expo(ll b, ll e){
  if(e == 0)
    return 1LL;

  ll aux = expo(b, e>>1LL);
  aux = (aux*aux) % MOD;

  if(e&1){
    aux = (aux*b) % MOD;
  }

  return aux;
}

void init(int n, const char s[]) {

  N = n;

  for(int i = 0; i < n; i++)
    dp[0][i] = s[i]-'a'+1;

  token = 0;
  while((1<<token) <= n)
    token++;

  token--;

  pot2[0][0] = PRIME;
  for(int i = 1; i <= token; i++)
    pot2[i][0] = (pot2[i-1][0]*pot2[i-1][0])%MOD;

  for(int i = 0; i <= token; i++){
    for(int j = 1; j < LOG; j++)
      pot2[i][j] = (pot2[i][j-1] * pot2[i][0]) % MOD;
  }

  for(int i = 0; i < LOG; i++){
    for(int j= n-1; j >= 0; j--){
      sv[i][j] = sv[i][j+1]*pot2[i][0];
      sv[i][j] %= MOD;
      sv[i][j] += s[j]-'a'+1;
    }
  }

  for(int i = 1; i <= token; i++)
    for(int j= 0; j+(1<<i)-1 < N; j++){
      dp[i][j] = dp[i-1][j];
      ll toSum = dp[i-1][j+(1<<(i-1))]*pot2[token-i][0];
      toSum %= MOD;
      dp[i][j] += toSum;
      if(dp[i][j] >= MOD)
        dp[i][j] -= MOD;
    }

}

int query(int i, int k) {
    
    int l = i, r = (1<<k)+l-1;

    ll hashSeq = sv[token-k][l]-(sv[token-k][r+1]*pot2[token-k][r-l])%MOD;
    hashSeq %= MOD;
    hashSeq += MOD;
    hashSeq %= MOD;

    return hashSeq == dp[k][l];
}

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