Submission #647619

#	Time	Username	Problem	Language	Result	Execution time	Memory
647619		mircea_007	Brperm (RMI20_brperm)	C++17	0 / 100	374 ms	85896 KiB

brperm

#include "brperm.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


*/

using ll = long long;

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

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

char str[MAXN];
int N;

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

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

  N = n;

  p26[0] = 1;
  for( i = 1 ; i <= N ; i++ )
    p26[i] = (26 * p26[i - 1]) % MOD;
  
  for( i = 0 ; i < N ; i++ )
    normal_hash[0][i] = perm_hash[0][i] = str[i] = s[i] - 'a';

  for( l = 1 ; l <= MAXL ; l++ ){
    p2 = (1 << l);

    if( p2 <= n ){
      for( i = 0 ; i < n ; i++ )
        normal_hash[l][i] = (normal_hash[l - 1][i] + p26[1 << (l - 1)] * normal_hash[l - 1][i + (1 << (l - 1))]) % MOD;
      for( i = 0 ; i < n ; i++ )
        perm_hash[l][i] = str[i];
      
      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] + p26[1 << (l - k)] * perm_hash[l][i + (1 << (k - 1))]) % MOD;
    }
  }
}

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