Submission #647680

#	Time	Username	Problem	Language	Result	Execution time	Memory
647680		mircea_007	Brperm (RMI20_brperm)	C++17	0 / 100	365 ms	83384 KiB

brperm

#include "brperm.h"

#include <stdio.h>

/*

can we somehow make a hash that reorder elements of a string?

rabin karp:
  H(str) = str[0] + 26 * str[1] + 26^2 * str[2] + ... mod 1e9+7

can't change mod

can we mess with the base? modular inverse etc?
we can flip the string by using 26^-1 as a base and multiplying at the end by 26^(N-1)

can we use 26^2?

H2(str) = H(str[0]0str[1]0str[2]0str[3]0....str[N/2-1]0) + 26^N * H(str[N/2]0str[N/2+1]0....str[N-1]0)

we would like a hash that does this:

goodH(str) = goodH(str[0]0str[1]0str[2]0str[3]0...str[N/2-1]0) + goodH(0str[N/2]0str[N/2+1]0....str[N-1])


H(abcd) = (a * 1 + c * 26^2) + 26 * (b + 26^2 * d)

we can use H(ac) and H(bd) but with different bases


*/

#define magic_sauce inline __attribute__((always_inline))

using ll = long long;

const int MAXN = 5e5;
const int MAXL = 20;
const int MOD = 1e9 + 9;
const int BASE = 26;

ll pb[1 + MAXN]; // automatic conversion

int normal_hash[MAXL][MAXN];
int perm_hash[MAXL][MAXN];

void init( int n, const char s[] ){
  int i, l, k, p2;

  pb[0] = 1;
  for( i = 1 ; i <= n ; i++ )
    pb[i] = (BASE * pb[i - 1]) % MOD;
  
  for( i = 0 ; i < n ; i++ )
    normal_hash[0][i] = perm_hash[0][i] = s[i] - 'a';

  for( l = 1 ; (p2 = (1 << l)) <= n ; l++ ){
    // calculate normal hash
    for( i = 0 ; i + p2 <= n ; i++ )
      normal_hash[l][i] = (normal_hash[l - 1][i] + pb[1 << (l - 1)] * normal_hash[l - 1][i + (1 << (l - 1))]) % MOD;
    
    for( i = 0 ; i < n ; i++ )
      perm_hash[l][i] = s[i] - 'a';
      
    for( k = 1 ; k <= l ; k++ )
      for( i = 0 ; i + (1 << k) <= n ; i++ )//      vv last iteration multiplies by 26 and the coefficient squares each time we go up
        perm_hash[l][i] = (perm_hash[l][i] + pb[1 << (l - k)] * perm_hash[l][i + (1 << (k - 1))]) % MOD;
  }

  /*for( l = 0 ; (1 << l) <= n ; l++ ){
    for( i = 0 ; i + (1 << l) <= n ; i++ )
      printf( "%d ", normal_hash[l][i] );
    printf( "\n" );
  }
  for( l = 0 ; (1 << l) <= n ; l++ ){
    for( i = 0 ; i + (1 << l) <= n ; i++ )
      printf( "%d ", perm_hash[l][i] );
    printf( "\n" );
    }*/
}

int query( int i, int k ){
  return normal_hash[k][i] == perm_hash[k][i];
}

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