Submission #858187

#	Time	Username	Problem	Language	Result	Execution time	Memory
858187		mircea_007	Brperm (RMI20_brperm)	C++17	0 / 100	1338 ms	19756 KiB

brperm

#include "brperm.h"

//#include <stdio.h>

using ll = long long;

const int MOD1 = 1e9 + 7;
const int MOD2 = 1e9 + 9;

const int BASE = 31;

/*

  Nlog^2N timp si memorie:

  // step, n, puteri ale lui 2
  // pare -> prima jumatate
  // impare -> a doua jumate

  hash( i, step, n, BASE ) = hash( i, step * 2, n / 2, BASE ) * BASE^(n/2) + hash( i + step, step * 2, n / 2, BASE )

  // obs: parametrul BASE ramane constant

  H( i, step, n ) = BASE^(n/2) * H( i, step * 2, n / 2 ) + H( i + step, step * 2, n / 2 )

  // step * n = 2^k constant

  pentru fiecare k:
    init: H[i] = v[i]
    for step=2^k-1..1:
      //H[i] = BASE^((2^k/step)/2) * H[i] + H[i + step]
      H[i] = BASE^(2^k-1/step) * H[i] + H[i + step]
  
*/

const int MAXN = 5e5;
const int MAXL = 18;

struct Persist {
  char ans[MAXL][MAXN];
} data;

void rev_hash( int n, int k, const char s[], int h[], const int BASE, const int MOD ){
  for( int i = 0 ; i < n ; i++ )
    h[i] = s[i] - 'a';

  if( !k )
    return;

  ll b = BASE;
  for( int step = 1 << (k - 1) ; step ; step >>= 1 ){    
    for( int i = 0 ; i + step < n ; i++ )
      h[i] = (b * h[i] + h[i + step]) % MOD;

    b = (b * b) % MOD;
  }
}

void init( int n, const char s[] ){
  int *rev_hash_1 = new int[n];
  int *rev_hash_2 = new int[n];

  for( int k = 0 ; (1 << k) <= n ; k++ ){
    rev_hash( n, k, s, rev_hash_1, BASE, MOD1 );
    rev_hash( n, k, s, rev_hash_2, BASE, MOD2 );

    int len = (1 << k);
    ll hash1 = 0, hash2 = 0;
    ll pBASE1 = MOD1 - 1, pBASE2 = MOD2 - 1;

    for( int i = 0 ; i + 1 < len ; i++ ){
      hash1 = (hash1 * BASE + (s[i] - 'a')) % MOD1;
      hash2 = (hash2 * BASE + (s[i] - 'a')) % MOD2;

      pBASE1 = (pBASE1 * BASE) % MOD1;
      pBASE2 = (pBASE2 * BASE) % MOD2;
    }

    // pBASE = -BASE^(len-1)

    for( int i = len - 1 ; i < n ; i++ ){
      hash1 = (hash1 * BASE + (s[i] - 'a')) % MOD1;
      hash2 = (hash2 * BASE + (s[i] - 'a')) % MOD2;

      // printf( "(i = %d | k = %d) mod1: %lld vs %d\n", i - len + 1, k, hash1, rev_hash_1[i - len + 1] );
      // printf( "(i = %d | k = %d) mod2: %lld vs %d\n", i - len + 1, k, hash2, rev_hash_2[i - len + 1] );

      data.ans[k][i - len + 1] = (rev_hash_1[i - len + 1] == hash1 && rev_hash_2[i - len + 1] == hash2);

      hash1 = (hash1 + pBASE1 * (s[i - len + 1] - 'a')) % MOD1;
      hash2 = (hash2 + pBASE2 * (s[i - len + 1] - 'a')) % MOD2;
    }
  }

  delete []rev_hash_1;
  delete []rev_hash_2;
}

int query( int i, int k ){
  return data.ans[k][i];
}

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