In this post, we will solve HackerRank Gridland Provinces Problem Solution.
The Kingdom of Gridland contains P provinces. Each province is defined as a 2 x N grid where each cell in the grid represents a city. Every cell in the grid contains a single lowercase character denoting the first character of the city name corresponding to that cell. From a city with the coordinates (i, j), it is possible to move to any of the following cells in 1 unit of time (provided that the destination cell is within the confines of the grid):
- (i-1, j)
- (i+1, j)
- (i, j 1)
- (i, j+1)
A knight wants to visit all the cities in Gridland. He can start his journey in any city and immediately stops his journey after having visited each city at least once. Moreover, he always plans his journey in such a way that the total time required to complete it is minimum.
After completing his tour of each province, the knight forms a string by concatenating the characters of all the cells in his path. How many distinct strings can he form in each province?
Input Format
The first line contains a single integer, P, denoting the number of provinces. The 3. P subsequent lines describe each province over the following three lines: Each of the next two lines contains a string, S, of length N denoting the characters for the
The first line contains an integer, N, denoting the number of columns in the province.
first and second row of the province.
Output Format
For each province, print the number of distinct strings the knight can form on a new line.
Sample Input
3
1
a
a
3
dab
abd
5
ababa
babab
Sample Output
1
8
2Explanation
Province 0:
The knight can only form one string (aa), so we print on a new line.
Province 1:
The knight can form eight different strings (abdbad, adabdb, badabd, bdbada, dababd, dabdba, dbabad, and dbadab), so we print 8 on a new line.
Province 2:
The knight can form two different strings (ababababab and bababababa), so we print 2 on a new line.
Gridland Provinces C Solution
#include <stdio.h>
#include <stdlib.h>
#define MOD1 1000000007
#define MOD2 1000000009
#define HASH_SIZE 123455
typedef struct _node{
int x;
int y;
struct _node *next;
} node;
void solve(int i,int j);
void insert(int x,int y);
void freehash();
long long modInverse(long long a,long long mod);
char a[2][601];
int hash_count,N;
long long tr1[1200],tl1[1200],br1[1200],
bl1[1200],dr1[1200],dl1[1200],ur1[1200],
ul1[1200],mod1[1201],inmod1[1201];
long long tr2[1200],tl2[1200],br2[1200],
bl2[1200],dr2[1200],dl2[1200],ur2[1200],
ul2[1200],mod2[1201],inmod2[1201];
node *hash[HASH_SIZE]={0};
int main(){
int T,i,j;
long long t1,t2;
scanf("%d",&T);
while(T--){
hash_count=0;
scanf("%d%s%s",&N,&a[0][0],&a[1][0]);
for(i=0,t1=t2=1;i<N;i++,t1=t1*26%MOD1,t2=t2*26%MOD2)
if(i){
tl1[i]=((a[0][i]-'a')*t1+tl1[i-1])%MOD1;
bl1[i]=((a[1][i]-'a')*t1+bl1[i-1])%MOD1;
tl2[i]=((a[0][i]-'a')*t2+tl2[i-1])%MOD2;
bl2[i]=((a[1][i]-'a')*t2+bl2[i-1])%MOD2;
}
else{
tl1[i]=a[0][i]-'a';
bl1[i]=a[1][i]-'a';
tl2[i]=a[0][i]-'a';
bl2[i]=a[1][i]-'a';
}
for(i=N-1;i>=0;i--,t1=t1*26%MOD1,t2=t2*26%MOD2){
tl1[2*N-i-1]=((a[1][i]-'a')*t1+tl1[2*N-i-2])%MOD1;
bl1[2*N-i-1]=((a[0][i]-'a')*t1+bl1[2*N-i-2])%MOD1;
tl2[2*N-i-1]=((a[1][i]-'a')*t2+tl2[2*N-i-2])%MOD2;
bl2[2*N-i-1]=((a[0][i]-'a')*t2+bl2[2*N-i-2])%MOD2;
}
for(i=N-1,t1=t2=1;i>=0;i--,t1=t1*26%MOD1,t2=t2*26%MOD2)
if(i!=N-1){
tr1[N-i-1]=((a[0][i]-'a')*t1+tr1[N-i-2])%MOD1;
br1[N-i-1]=((a[1][i]-'a')*t1+br1[N-i-2])%MOD1;
tr2[N-i-1]=((a[0][i]-'a')*t2+tr2[N-i-2])%MOD2;
br2[N-i-1]=((a[1][i]-'a')*t2+br2[N-i-2])%MOD2;
}
else{
tr1[N-i-1]=a[0][i]-'a';
br1[N-i-1]=a[1][i]-'a';
tr2[N-i-1]=a[0][i]-'a';
br2[N-i-1]=a[1][i]-'a';
}
for(i=0;i<N;i++,t1=t1*26%MOD1,t2=t2*26%MOD2){
tr1[i+N]=((a[1][i]-'a')*t1+tr1[i+N-1])%MOD1;
br1[i+N]=((a[0][i]-'a')*t1+br1[i+N-1])%MOD1;
tr2[i+N]=((a[1][i]-'a')*t2+tr2[i+N-1])%MOD2;
br2[i+N]=((a[0][i]-'a')*t2+br2[i+N-1])%MOD2;
}
for(i=0,t1=t2=1;i<N;i++){
if(i%2){
ul1[2*i]=((a[0][i]-'a')*t1+ul1[2*i-1])%MOD1;
dl1[2*i]=((a[1][i]-'a')*t1+dl1[2*i-1])%MOD1;
ul2[2*i]=((a[0][i]-'a')*t2+ul2[2*i-1])%MOD2;
dl2[2*i]=((a[1][i]-'a')*t2+dl2[2*i-1])%MOD2;
}
else
if(!i){
ul1[2*i]=a[1][i]-'a';
dl1[2*i]=a[0][i]-'a';
ul2[2*i]=a[1][i]-'a';
dl2[2*i]=a[0][i]-'a';
}
else{
ul1[2*i]=((a[1][i]-'a')*t1+ul1[2*i-1])%MOD1;
dl1[2*i]=((a[0][i]-'a')*t1+dl1[2*i-1])%MOD1;
ul2[2*i]=((a[1][i]-'a')*t2+ul2[2*i-1])%MOD2;
dl2[2*i]=((a[0][i]-'a')*t2+dl2[2*i-1])%MOD2;
}
t1=t1*26%MOD1;
t2=t2*26%MOD2;
if(i%2){
ul1[2*i+1]=((a[1][i]-'a')*t1+ul1[2*i])%MOD1;
dl1[2*i+1]=((a[0][i]-'a')*t1+dl1[2*i])%MOD1;
ul2[2*i+1]=((a[1][i]-'a')*t2+ul2[2*i])%MOD2;
dl2[2*i+1]=((a[0][i]-'a')*t2+dl2[2*i])%MOD2;
}
else{
ul1[2*i+1]=((a[0][i]-'a')*t1+ul1[2*i])%MOD1;
dl1[2*i+1]=((a[1][i]-'a')*t1+dl1[2*i])%MOD1;
ul2[2*i+1]=((a[0][i]-'a')*t2+ul2[2*i])%MOD2;
dl2[2*i+1]=((a[1][i]-'a')*t2+dl2[2*i])%MOD2;
}
t1=t1*26%MOD1;
t2=t2*26%MOD2;
}
for(i=N-1,t1=t2=1;i>=0;i--)
if(i==N-1){
ur1[2*(N-1-i)]=a[1][i]-'a';
dr1[2*(N-1-i)]=a[0][i]-'a';
ur2[2*(N-1-i)]=a[1][i]-'a';
dr2[2*(N-1-i)]=a[0][i]-'a';
t1=t1*26%MOD1;
t2=t2*26%MOD2;
ur1[2*(N-1-i)+1]=((a[0][i]-'a')*t1+ur1[2*(N-1-i)])%MOD1;
dr1[2*(N-1-i)+1]=((a[1][i]-'a')*t1+dr1[2*(N-1-i)])%MOD1;
ur2[2*(N-1-i)+1]=((a[0][i]-'a')*t2+ur2[2*(N-1-i)])%MOD2;
dr2[2*(N-1-i)+1]=((a[1][i]-'a')*t2+dr2[2*(N-1-i)])%MOD2;
t1=t1*26%MOD1;
t2=t2*26%MOD2;
}
else{
if((N-i)%2==0){
ur1[2*(N-1-i)]=((a[0][i]-'a')*t1+ur1[2*(N-1-i)-1])%MOD1;
dr1[2*(N-1-i)]=((a[1][i]-'a')*t1+dr1[2*(N-1-i)-1])%MOD1;
ur2[2*(N-1-i)]=((a[0][i]-'a')*t2+ur2[2*(N-1-i)-1])%MOD2;
dr2[2*(N-1-i)]=((a[1][i]-'a')*t2+dr2[2*(N-1-i)-1])%MOD2;
}
else{
ur1[2*(N-1-i)]=((a[1][i]-'a')*t1+ur1[2*(N-1-i)-1])%MOD1;
dr1[2*(N-1-i)]=((a[0][i]-'a')*t1+dr1[2*(N-1-i)-1])%MOD1;
ur2[2*(N-1-i)]=((a[1][i]-'a')*t2+ur2[2*(N-1-i)-1])%MOD2;
dr2[2*(N-1-i)]=((a[0][i]-'a')*t2+dr2[2*(N-1-i)-1])%MOD2;
}
t1=t1*26%MOD1;
t2=t2*26%MOD2;
if((N-i)%2==0){
ur1[2*(N-1-i)+1]=((a[1][i]-'a')*t1+ur1[2*(N-1-i)])%MOD1;
dr1[2*(N-1-i)+1]=((a[0][i]-'a')*t1+dr1[2*(N-1-i)])%MOD1;
ur2[2*(N-1-i)+1]=((a[1][i]-'a')*t2+ur2[2*(N-1-i)])%MOD2;
dr2[2*(N-1-i)+1]=((a[0][i]-'a')*t2+dr2[2*(N-1-i)])%MOD2;
}
else{
ur1[2*(N-1-i)+1]=((a[0][i]-'a')*t1+ur1[2*(N-1-i)])%MOD1;
dr1[2*(N-1-i)+1]=((a[1][i]-'a')*t1+dr1[2*(N-1-i)])%MOD1;
ur2[2*(N-1-i)+1]=((a[0][i]-'a')*t2+ur2[2*(N-1-i)])%MOD2;
dr2[2*(N-1-i)+1]=((a[1][i]-'a')*t2+dr2[2*(N-1-i)])%MOD2;
}
t1=t1*26%MOD1;
t2=t2*26%MOD2;
}
for(i=0;i<=2*N;i++)
if(i){
mod1[i]=mod1[i-1]*26%MOD1;
inmod1[i]=modInverse(mod1[i],MOD1);
mod2[i]=mod2[i-1]*26%MOD2;
inmod2[i]=modInverse(mod2[i],MOD2);
}
else
mod1[i]=inmod1[i]=mod2[i]=inmod2[i]=1;
for(i=0;i<=N;i++)
for(j=i;j<=N;j++)
solve(i,j);
printf("%d\n",hash_count);
freehash();
}
return 0;
}
void solve(int i,int j){
long long t1,t2,t3,t4,t5,t6,t7,t8,t9;
long long tt1,tt2,tt3,tt4,tt5,tt6,tt7,tt8,tt9;
t1=tr1[N+i-1];
t2=br1[N+i-1];
if(i!=N){
t1=(t1-tr1[N-i-1]+MOD1)%MOD1;
t2=(t2-br1[N-i-1]+MOD1)%MOD1;
}
t1=t1*inmod1[N-i]%MOD1;
t2=t2*inmod1[N-i]%MOD1;
t3=tl1[2*N-j-1];
t4=bl1[2*N-j-1];
if(j){
t3=(t3-tl1[j-1]+MOD1)%MOD1;
t4=(t4-bl1[j-1]+MOD1)%MOD1;
}
t3=t3*inmod1[j]%MOD1;
t4=t4*inmod1[j]%MOD1;
if(!j)
t5=t6=0;
else{
t5=ul1[2*j-1];
t6=dl1[2*j-1];
if(i){
t5=(t5-ul1[2*i-1]+MOD1)%MOD1;
t6=(t6-dl1[2*i-1]+MOD1)%MOD1;
}
}
if(i==N)
t7=t8=0;
else{
t7=ur1[2*(N-i)-1];
t8=dr1[2*(N-i)-1];
if(j!=N){
t7=(t7-ur1[2*(N-j)-1]+MOD1)%MOD1;
t8=(t8-dr1[2*(N-j)-1]+MOD1)%MOD1;
}
}
tt1=tr2[N+i-1];
tt2=br2[N+i-1];
if(i!=N){
tt1=(tt1-tr2[N-i-1]+MOD2)%MOD2;
tt2=(tt2-br2[N-i-1]+MOD2)%MOD2;
}
tt1=tt1*inmod2[N-i]%MOD2;
tt2=tt2*inmod2[N-i]%MOD2;
tt3=tl2[2*N-j-1];
tt4=bl2[2*N-j-1];
if(j){
tt3=(tt3-tl2[j-1]+MOD2)%MOD2;
tt4=(tt4-bl2[j-1]+MOD2)%MOD2;
}
tt3=tt3*inmod2[j]%MOD2;
tt4=tt4*inmod2[j]%MOD2;
if(!j)
tt5=tt6=0;
else{
tt5=ul2[2*j-1];
tt6=dl2[2*j-1];
if(i){
tt5=(tt5-ul2[2*i-1]+MOD2)%MOD2;
tt6=(tt6-dl2[2*i-1]+MOD2)%MOD2;
}
}
if(i==N)
tt7=tt8=0;
else{
tt7=ur2[2*(N-i)-1];
tt8=dr2[2*(N-i)-1];
if(j!=N){
tt7=(tt7-ur2[2*(N-j)-1]+MOD2)%MOD2;
tt8=(tt8-dr2[2*(N-j)-1]+MOD2)%MOD2;
}
}
t9=t1;
if(i%2)
t9+=t6;
else
t9+=t5;
if((j-i)%2)
t9+=t3*mod1[j*2]%MOD1;
else
t9+=t4*mod1[j*2]%MOD1;
t9%=MOD1;
tt9=tt1;
if(i%2)
tt9+=tt6;
else
tt9+=tt5;
if((j-i)%2)
tt9+=tt3*mod2[j*2]%MOD2;
else
tt9+=tt4*mod2[j*2]%MOD2;
tt9%=MOD2;
insert(t9,tt9);
t9=t2;
if(i%2)
t9+=t5;
else
t9+=t6;
if((j-i)%2)
t9+=t4*mod1[j*2]%MOD1;
else
t9+=t3*mod1[j*2]%MOD1;
t9%=MOD1;
tt9=tt2;
if(i%2)
tt9+=tt5;
else
tt9+=tt6;
if((j-i)%2)
tt9+=tt4*mod2[j*2]%MOD2;
else
tt9+=tt3*mod2[j*2]%MOD2;
tt9%=MOD2;
insert(t9,tt9);
t9=t3;
if((N-j)%2)
t9+=t8;
else
t9+=t7;
if((j-i)%2)
t9+=t1*mod1[(N-i)*2]%MOD1;
else
t9+=t2*mod1[(N-i)*2]%MOD1;
t9%=MOD1;
tt9=tt3;
if((N-j)%2)
tt9+=tt8;
else
tt9+=tt7;
if((j-i)%2)
tt9+=tt1*mod2[(N-i)*2]%MOD2;
else
tt9+=tt2*mod2[(N-i)*2]%MOD2;
tt9%=MOD2;
insert(t9,tt9);
t9=t4;
if((N-j)%2)
t9+=t7;
else
t9+=t8;
if((j-i)%2)
t9+=t2*mod1[(N-i)*2]%MOD1;
else
t9+=t1*mod1[(N-i)*2]%MOD1;
t9%=MOD1;
tt9=tt4;
if((N-j)%2)
tt9+=tt7;
else
tt9+=tt8;
if((j-i)%2)
tt9+=tt2*mod2[(N-i)*2]%MOD2;
else
tt9+=tt1*mod2[(N-i)*2]%MOD2;
tt9%=MOD2;
insert(t9,tt9);
return;
}
void insert(int x,int y){
int bucket=(x+y)%HASH_SIZE;
node *t=hash[bucket];
while(t){
if(t->x==x && t->y==y)
return;
t=t->next;
}
t=(node*)malloc(sizeof(node));
t->x=x;
t->y=y;
t->next=hash[bucket];
hash[bucket]=t;
hash_count++;
return;
}
void freehash(){
int i;
node *t,*p;
for(i=0;i<HASH_SIZE;i++){
t=hash[i];
while(t){
p=t->next;
free(t);
t=p;
}
hash[i]=NULL;
}
return;
}
long long modInverse(long long a,long long mod){
long long b0 = mod, t, q;
long long x0 = 0, x1 = 1;
while (a > 1) {
q = a / mod;
t = mod; mod = a % mod; a = t;
t = x0; x0 = x1 - q * x0; x1 = t;
}
if (x1 < 0) x1 += b0;
return x1;
}Gridland Provinces C++ Solution
/// Stupido del problemo
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cassert>
#include <cstdlib>
#include <ctime>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const double EPS = 1e-9;
const double PI = acos(-1);
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define fe first
#define se second
const int oo = 1e9, bpr = 1e9 + 7, N = 610, K = 432857;
int pp[2];
char a[N][N];
vector <ull> bek[K];
int n;
pair <int, ull> pre[2][N];
ull pows[2][N + N];
inline void gh (ull &hh, int a) {
hh = 131 * hh + a;
hh %= bpr;
}
inline void gh2 (int &hh, int a) {
hh = 131 * hh + a;
hh %= K;
}
inline void calc (int x, int y) {
pair <int, ull> ha = mp (0, 0);
for (int i = y; i >= 1; --i)
gh2 (ha.fe, a[x][i]), gh (ha.se, a[x][i]);
x ^= 1;
for (int i = 1; i <= y; ++i)
gh2 (ha.fe, a[x][i]), gh (ha.se, a[x][i]);
for (int i = y; i <= n; ++i) {
if (i != y)
gh2 (ha.fe, a[x][i]), gh (ha.se, a[x][i]), gh2 (ha.fe, a[x ^= 1][i]), gh (ha.se, a[x][i]);
auto ha2 = mp ((ha.fe * pows[0][(n - i) * 2] + pre[x][i + 1].fe) % K, (ha.se * 1ll * pows[1][(n - i) * 2] + pre[x][i + 1].se) % bpr);
bek[ha2.fe].eb (ha2.se);
}
}
inline void calcpre () {
for (int i = 0; i < 2; ++i) {
for (int j = 1; j < N; ++j) {
pre[i][j] = mp (0, 0);
for (int k = j; k <= n; ++k)
gh2 (pre[i][j].fe, a[i][k]), gh (pre[i][j].se, a[i][k]);
for (int k = n; k >= j; --k)
gh2 (pre[i][j].fe, a[i ^ 1][k]), gh (pre[i][j].se, a[i ^ 1][k]);
}
}
}
int main() {
#ifdef LOCAL
freopen ("in", "r", stdin);
#endif
ios_base :: sync_with_stdio (0);
cin.tie (0);
int p;
cin >> p;
for (int i = pows[1][0] = 1; i < N + N; ++i)
pows[1][i] = pows[1][i - 1] * 131ll % bpr;
for (int i = pows[0][0] = 1; i < N + N; ++i)
pows[0][i] = pows[0][i - 1] * 131ll % K;
while (p--) {
cin >> n;
for (int i = 0; i < 2; ++i)
for (int j = 1; j <= n; ++j)
cin >> a[i][j];
calcpre ();
for (int i = 0; i < K; ++i)
bek[i].clear ();
for (int i = 0; i < 2; ++i)
for (int j = 1; j <= n; ++j)
calc (i, j);
reverse (a[0] + 1, a[0] + n + 1);
reverse (a[1] + 1, a[1] + n + 1);
calcpre ();
for (int i = 0; i < 2; ++i)
for (int j = 1; j <= n; ++j)
calc (i, j);
int ans = 0;
for (int i = 0; i < K; ++i) {
sort (bek[i].begin (), bek[i].end ());
bek[i].resize (unique (bek[i].begin (), bek[i].end ()) - bek[i].begin ());
ans += bek[i].size ();
}
cout << ans << "\n";
}
return 0;
}Gridland Provinces C Sharp Solution
using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;
class Result
{
/*
* Complete the 'gridlandProvinces' function below.
*
* The function is expected to return an INTEGER.
* The function accepts following parameters:
* 1. STRING s1
* 2. STRING s2
*/
private static long mod, f1, f2;
private static long[] arr1, arr2;
private static HashSet<long> result;
public static void inIt()
{
mod = 2147483607; f1 = 107; f2 = 101;
arr1 = new long[1201];
arr2 = new long[1201];
for (int i = 0; i < 1201; ++i)
{
arr1[i] = i > 0 ? arr1[i - 1] * f1 % mod : 1;
arr2[i] = i > 0 ? arr2[i - 1] * f2 % mod : 1;
}
}
public static int gridlandProvinces(string s1, string s2)
{
result = new HashSet<long>();
for (int i = 0; i < s1.Length; ++i)
{
process(s1, s2, i, false);
process(s2, s1, i, false);
process(s1, s2, i, true);
process(s2, s1, i, true);
}
s1 = new string(s1.Reverse().ToArray());
s2 = new string(s2.Reverse().ToArray());
for (int i = 0; i < s1.Length; ++i)
{
process(s1, s2, i, false);
process(s2, s1, i, false);
process(s1, s2, i, true);
process(s2, s1, i, true);
}
return result.Count();
}
private static void process(string s1, string s2, int k, bool b)
{
long p1 = 0, p2 = 0, p3 = 0, p4 = 0;
for (int i = 0; i < k; ++i)
{
p1 = (p1 + s1[i] * arr1[k - 1 - i]) % mod;
p1 = (p1 + s2[i] * arr1[k + i]) % mod;
p3 = (p3 + s1[i] * arr2[k - 1 - i]) % mod;
p3 = (p3 + s2[i] * arr2[k + i]) % mod;
}
if (b)
{
p1 = (p1 + s2[k] * arr1[k * 2]) % mod;
p1 = (p1 + s1[k] * arr1[k * 2 + 1]) % mod;
p3 = (p3 + s2[k] * arr2[k * 2]) % mod;
p3 = (p3 + s1[k] * arr2[k * 2 + 1]) % mod;
string s = s1; s1 = s2; s2 = s;
++k;
}
for (int i = k; i < s1.Length; ++i)
{
p2 = (p2 + s1[i] * arr1[s1.Length * 2 + k - 1 - i]) % mod;
p2 = (p2 + s2[i] * arr1[i + k]) % mod;
p4 = (p4 + s1[i] * arr2[s1.Length * 2 + k - 1 - i]) % mod;
p4 = (p4 + s2[i] * arr2[i + k]) % mod;
}
long ans = (p1 + p2) % mod * mod + (p3 + p4) % mod;
if (!result.Contains(ans)) result.Add(ans);
for (int i = k; i < s1.Length - 1; i += 2)
{
p1 = (p1 + s2[i] * arr1[i * 2]) % mod;
p1 = (p1 + s1[i] * arr1[i * 2 + 1]) % mod;
p1 = (p1 + s1[i + 1] * arr1[i * 2 + 2]) % mod;
p1 = (p1 + s2[i + 1] * arr1[i * 2 + 3]) % mod;
p2 = (p2 + s2[i] * (mod - arr1[i * 2])) % mod;
p2 = (p2 + s2[i + 1] * (mod - arr1[i * 2 + 1])) % mod;
p2 = (p2 + s1[i] * (mod - arr1[s1.Length * 2 - 1])) % mod;
p2 = (p2 + s1[i + 1] * (mod - arr1[s1.Length * 2 - 2])) % mod;
p2 = (p2 * f1 * f1) % mod;
p3 = (p3 + s2[i] * arr2[i * 2]) % mod;
p3 = (p3 + s1[i] * arr2[i * 2 + 1]) % mod;
p3 = (p3 + s1[i + 1] * arr2[i * 2 + 2]) % mod;
p3 = (p3 + s2[i + 1] * arr2[i * 2 + 3]) % mod;
p4 = (p4 + s2[i] * (mod - arr2[i * 2])) % mod;
p4 = (p4 + s2[i + 1] * (mod - arr2[i * 2 + 1])) % mod;
p4 = (p4 + s1[i] * (mod - arr2[s1.Length * 2 - 1])) % mod;
p4 = (p4 + s1[i + 1] * (mod - arr2[s1.Length * 2 - 2])) % mod;
p4 = (p4 * f2 * f2) % mod;
ans = (p1 + p2) % mod * mod + (p3 + p4) % mod;
if (!result.Contains(ans)) result.Add(ans);
}
}
}
class Solution
{
public static void Main(string[] args)
{
Result.inIt();
TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);
int p = Convert.ToInt32(Console.ReadLine().Trim());
for (int pItr = 0; pItr < p; pItr++)
{
int n = Convert.ToInt32(Console.ReadLine().Trim());
string s1 = Console.ReadLine();
string s2 = Console.ReadLine();
int result = Result.gridlandProvinces(s1, s2);
textWriter.WriteLine(result);
}
textWriter.Flush();
textWriter.Close();
}
}Gridland Provinces Java Solution
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Solution2 {
private final static Scanner scanner =
new Scanner(System.in);
private final static long mod1 = 2147483607,
f1 = 107, f2 = 101;
private final static long[] arr1 = new long[10000],
arr2 = new long[10000];
private final static Set<Long> result = new HashSet<>();
public static void main(String[] args) {
for (int i = 0; i < arr1.length; ++i) {
arr1[i] = i > 0 ? arr1[i - 1] * f1 % mod1 : 1;
arr2[i] = i > 0 ? arr2[i - 1] * f2 % mod1 : 1;
}
for (int t = scanner.nextInt(); t > 0; --t) {
result.clear();
scanner.nextInt();
char[] c1 = scanner.next().toCharArray();
char[] c2 = scanner.next().toCharArray();
for (int i = 0; i < c1.length; ++i) {
process(c1, c2, i, false);
process(c2, c1, i, false);
process(c1, c2, i, true);
process(c2, c1, i, true);
}
reverse(c1);
reverse(c2);
for (int i = 0; i < c1.length; ++i) {
process(c1, c2, i, false);
process(c2, c1, i, false);
process(c1, c2, i, true);
process(c2, c1, i, true);
}
System.out.println(result.size());
}
}
static void process(char[] s1, char[] s2, int k, boolean b) {
long p1 = 0, p2 = 0, p3 = 0, p4 = 0;
for (int i = 0; i < k; ++i) {
p1 = (p1 + s1[i] * arr1[k - 1 - i]) % mod1;
p1 = (p1 + s2[i] * arr1[k + i]) % mod1;
p3 = (p3 + s1[i] * arr2[k - 1 - i]) % mod1;
p3 = (p3 + s2[i] * arr2[k + i]) % mod1;
}
if (b) {
p1 = (p1 + s2[k] * arr1[k * 2]) % mod1;
p1 = (p1 + s1[k] * arr1[k * 2 + 1]) % mod1;
p3 = (p3 + s2[k] * arr2[k * 2]) % mod1;
p3 = (p3 + s1[k] * arr2[k * 2 + 1]) % mod1;
char[] s = s1; s1 = s2; s2 = s;
++k;
}
for (int i = k; i < s1.length; ++i) {
p2 = (p2 + s1[i] * arr1[s1.length * 2 + k - 1 - i]) % mod1;
p2 = (p2 + s2[i] * arr1[i + k]) % mod1;
p4 = (p4 + s1[i] * arr2[s1.length * 2 + k - 1 - i]) % mod1;
p4 = (p4 + s2[i] * arr2[i + k]) % mod1;
}
result.add(((p1 + p2) % mod1) * mod1 + (p3 + p4) % mod1);
for (int i = k; i < s1.length - 1; i += 2) {
p1 = (p1 + s2[i] * arr1[i * 2]) % mod1;
p1 = (p1 + s1[i] * arr1[i * 2 + 1]) % mod1;
p1 = (p1 + s1[i + 1] * arr1[i * 2 + 2]) % mod1;
p1 = (p1 + s2[i + 1] * arr1[i * 2 + 3]) % mod1;
p2 = (p2 + s2[i] * (mod1 - arr1[i * 2])) % mod1;
p2 = (p2 + s2[i+1] * (mod1 - arr1[i * 2 + 1])) % mod1;
p2 = (p2 + s1[i] * (mod1 - arr1[s1.length * 2 - 1])) % mod1;
p2 = (p2 + s1[i+1] * (mod1 - arr1[s1.length * 2 - 2])) % mod1;
p2 = (p2 * f1 * f1) % mod1;
p3 = (p3 + s2[i] * arr2[i * 2]) % mod1;
p3 = (p3 + s1[i] * arr2[i * 2 + 1]) % mod1;
p3 = (p3 + s1[i + 1] * arr2[i * 2 + 2]) % mod1;
p3 = (p3 + s2[i + 1] * arr2[i * 2 + 3]) % mod1;
p4 = (p4 + s2[i] * (mod1 - arr2[i * 2])) % mod1;
p4 = (p4 + s2[i+1] * (mod1 - arr2[i * 2 + 1])) % mod1;
p4 = (p4 + s1[i] * (mod1 - arr2[s1.length * 2 - 1])) % mod1;
p4 = (p4 + s1[i+1] * (mod1 - arr2[s1.length * 2 - 2])) % mod1;
p4 = (p4 * f2 * f2) % mod1;
result.add(((p1 + p2) % mod1) * mod1 + (p3 + p4) % mod1);
}
}
private static void reverse(char[] str) {
for (int i = str.length / 2 - 1; i >= 0; --i) {
char t = str[i];
str[i] = str[str.length - 1 - i];
str[str.length - 1 - i] = t;
}
}
}Gridland Provinces JavaScript Solution
'use strict';
const fs = require('fs');
const _ = require('underscore');
process.stdin.resume();
process.stdin.setEncoding('ascii');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', _ => {
inputString = inputString.trim().split('\n').map(str => str.trim());
main();
});
function readLine() {
return inputString[currentLine++];
}
var res = new Set();
function arr2(x, y) {
var a1 = _.range(x).map(() => {
return _.range(y).map((i2) => {
return BigInt(i2);
})
})
return a1
}
function arr(x) {
return _.range(x).map((i) => {
return BigInt(i);
})
}
function* range(start, end) {
for (let i = start; i <= end; i++) {
yield i;
}
}
function shuffle(obj1, obj2) {
var index = obj1.length;
var rnd, tmp1, tmp2;
while (index) {
rnd = Math.floor(Math.random() * index);
index -= 1;
tmp1 = obj1[index];
tmp2 = obj2[index];
obj1[index] = obj1[rnd];
obj2[index] = obj2[rnd];
obj1[rnd] = tmp1;
obj2[rnd] = tmp2;
}
}
var M = BigInt(1202953049705846707);
var u = BigInt(7627744968637);
var u2 = u * u % M
var P = arr(608),
V = arr(128),
L = arr2(2, 608),
R = arr2(2, 608),
X = arr2(2, 608);
function hh(n, a) {
L[0][0] = L[0][1] = R[0][1] = R[0][0] = 0n
let p = u;
for (let i = 1; i <= n; ++i, p = p * u2 % M)
for (let j of range(0, 1)) {
L[j][i] = (BigInt(L[j][i - 1]) * u + BigInt(V[a[j ^ 1][i - 1].charCodeAt(0)]) + BigInt(V[a[j][i - 1].charCodeAt(0)]) * p) % M;
R[j][i] = (BigInt(R[j][i - 1]) * u + BigInt(V[a[j ^ 1][n - i].charCodeAt(0)]) + BigInt(V[a[j][n - i].charCodeAt(0)]) * p) % M;
};
res.add(L[0][n]);
res.add(L[1][n]);
res.add(R[0][n]);
res.add(R[1][n]);
for (let j of range(0, 1)) {
for (let i = 1; i < n; ++i) {
X[j][i] = (BigInt(V[a[j][i].charCodeAt(0)]) * BigInt(u) + BigInt(V[a[j ^ 1][i].charCodeAt(0)])) % M;
}
}
for (let k of range(0, 1)) {
for (let l = 1; l <= n; ++l) {
let t = L[k][l];
for (let r = n - l, j = l, f = !k ? 1 : 0; r; --r, ++j, f = !f ? 1 : 0) {
// console.log(t)
res.add((BigInt(t) * BigInt(P[r]) + BigInt(R[f][r])) % M)
t = (BigInt(t) * BigInt(u2) + BigInt(X[f][j])) % M
}
}
}
}
function main() {
P[0] = 1;
for (let i = 1; i < 608; ++i) {
P[i] = BigInt(P[i - 1]) * u2 % M;
}
for (let i = 0; i < 128; ++i) V[i] = i ^ i >> 1;
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const p = parseInt(readLine(), 10);
for (let pItr = p; pItr > 0; pItr--) {
let n = parseInt(readLine(), 10),
s1 = readLine(),
s2 = readLine(),
a = [s1, s2];
shuffle(V, [V, 128]);
res.clear();
hh(n, a);
a[0] = a[0].split('').reverse().join('');
a[1] = a[1].split('').reverse().join('');
hh(n, a);
ws.write(res.size + "\n");
}
ws.end();
}Gridland Provinces Python Solution
#!/bin/python3
import os
import sys
PRIME = 1000000007*65535
PMAP = [int((1<<(5*i)) % PRIME) for i in range(1202)]
def chash(s, p = 0):
for c in s:
p = ((p<<5) + ord(c)) % PRIME
return p
def hmap(s):
ret = [0]
for c in s:
ret.append(((ret[-1]<<5)+ord(c)) % PRIME)
return ret
def hrange(l,i,j,s):
return (l[j] + ((s-l[i]) * PMAP[j-i])) % PRIME
def count(s1 : str, s2 : str, s1rev, s2rev):
ret = set()
n,n2 = len(s1),2*len(s1)
left_to_top = s2rev + s1
left_to_bot = s1rev + s2
right_from_top = s1 + s2rev
right_from_bot = s2 + s1rev
mid_even_tb = [ord(s1[i//2]) if ((i%4) in (0,3)) else ord(s2[i//2]) for i in range(n2)]
mid_odd_tb = [ord(s2[i//2]) if ((i%4) in (0,3)) else ord(s1[i//2]) for i in range(n2)]
left_to_top,left_to_bot,right_from_top,right_from_bot = map(hmap,(left_to_top,left_to_bot,right_from_top,right_from_bot))
mid_even_tb = [mid_even_tb[2*j+1] + mid_even_tb[2*j] * PMAP[1] for j in range(n)]
mid_odd_tb = [mid_odd_tb[2*j+1] + mid_odd_tb[2*j] * PMAP[1] for j in range(n)]
for left,mids,rights in (left_to_top,(mid_even_tb,mid_odd_tb),(right_from_top,right_from_bot)),(left_to_bot,(mid_odd_tb,mid_even_tb),(right_from_bot,right_from_top)):
for i in range(0,n+1):
mid = mids[i&1]
s = hrange(left,n-i,n+i,0)
for j in range(i, n):
ret.add(hrange(rights[j&1],j,n2-j,s))
s = (s * PMAP[2] + mid[j]) % PRIME
ret.add(s)
rights = rights[::-1]
return ret
def gridlandProvinces(s1, s2):
s1rev,s2rev = s1[::-1],s2[::-1]
return len(count(s1, s2, s1rev, s2rev).union(count(s1rev, s2rev, s1, s2)))
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
p = int(input())
for p_itr in range(p):
n = int(input())
s1 = input()
s2 = input()
result = gridlandProvinces(s1, s2)
fptr.write(str(result) + '\n')
fptr.close()
