Submission #596569

#	Time	Username	Problem	Language	Result	Execution time	Memory
596569		CaroLinda	Brperm (RMI20_brperm)	C++14	0 / 100	682 ms	153204 KiB

brperm

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

#define ll long long

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

using namespace std;

int dp[LOG][LOG][MAXN];
ll pot[MAXN], sv[MAXN];
ll invPot[MAXN];

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[]) {
  pot[0] = 1LL;

  for(int i = 1; i <= n; i++)
    pot[i] = (pot[i-1] * PRIME) % MOD;

  for(int i = 0; i < n; i++){
    sv[i] = (i == 0) ? 0 : sv[i-1];
    sv[i] += (pot[i] * (s[i]-'a'+1))%MOD;
    sv[i] %= MOD;
  }

  invPot[0] = 1;
  invPot[1] = expo(PRIME, MOD-2);
  for(int i = 2; i <= n; i++)
    invPot[i] = (invPot[i-1] * invPot[1] ) % MOD;

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

  for(int i = 1; i < LOG; i++)
    for(int j = 0; j < LOG-1; j++)
      for(int g = 0; g+(1<<i)-1 < n; g++){
        dp[i][j][g] = dp[i-1][j+1][g];
        ll toSum = dp[i-1][j+1][g+(1<<(i-1))]*pot[(1<<j)];

        toSum %= MOD;
        dp[i][j][g] += toSum;

        if(dp[i][j][g] >= MOD)
          dp[i][j][g] -= MOD;
      }

    cout << dp[1][1][0] << endl;
}

int query(int i, int k) {
    int l = i, r = (1<<k)+l-1;
    ll hashSeq = sv[r]-( l == 0 ? 0 : sv[l-1]);
    hashSeq += MOD;
    hashSeq %= MOD;
    hashSeq *= invPot[l];
    hashSeq %= MOD;

    return hashSeq == dp[k][0][i];
}

Compilation message (stderr)

brperm.cpp: In function 'void init(int, const char*)':
brperm.cpp:53:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   53 |   for(int i = 1; i < LOG; i++)
      |   ^~~
brperm.cpp:66:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   66 |     cout << dp[1][1][0] << endl;
      |     ^~~~

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