Submission #401723

#	Time	Username	Problem	Language	Result	Execution time	Memory
401723		rama_pang	Brperm (RMI20_brperm)	C++17	100 / 100	453 ms	76684 KiB

brperm

#include "brperm.h"

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
const int MAX = 500005;
const int LOG = 19;

// Solution:
// B = Base
// StraightHash(B, L, K) = \sum_{i = L}^{L + 2^K - 1} B^{i - L} x_i
// BrPermHash(B, L, K) = BrPermHash(B^2, L, K - 1) + B * BrPermHash(B^2, L + 2^{K - 1}, K - 1)

int N;
string S;

int Base[LOG];
int BrPermHash[MAX][LOG];
int StraightHash[MAX][LOG];

void init(int n, const char s[]) {
  N = n, S = s;

  Base[LOG - 1] = 37;
  for (int i = LOG - 2; i >= 0; i--) {
    Base[i] = 1ll * Base[i + 1] * Base[i + 1] % MOD;
  }

  for (int L = N - 1; L >= 0; L--) {
    BrPermHash[L][0] = (S[L] - 'a' + 1);
    for (int K = 1; K < LOG; K++) {
      BrPermHash[L][K] = BrPermHash[L][K - 1];
      if (L + (1 << (K - 1)) <= N) {
        BrPermHash[L][K] += 1ll * Base[K] * BrPermHash[L + (1 << (K - 1))][K - 1] % MOD;
        BrPermHash[L][K] %= MOD;
      }
    }
  }

  for (int L = N - 1; L >= 0; L--) {
    for (int K = 0; K < LOG; K++) {
      StraightHash[L][K] = ((S[L] - 'a' + 1) + 1ll * Base[K] * StraightHash[L + 1][K]) % MOD;
    }
  }

  for (int K = 0; K < LOG; K++) {
    int power = 1;
    for (int i = 0; i < (1 << K); i++) {
      power = 1ll * power * Base[K] % MOD;
    }
    for (int L = 0; L < N; L++) {
      if (L + (1 << K) <= N) {
        StraightHash[L][K] += MOD - (1ll * power * StraightHash[L + (1 << K)][K] % MOD);
        StraightHash[L][K] %= MOD;
      }
    }
  }
}

int query(int i, int k) {
  return (i + (1 << k) <= N) && StraightHash[i][k] == BrPermHash[i][k];
}

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