Entrenamiento IOI - Etapa #2 - Problem: Long Hamming - Judge: omegaUp - 30/11/2014 - Puntaje: 100% (AC) - GCD + BIT (Theory mathematical + Binary Indexed Tree) - Complexity: O( 2 N 3 log 26 ).

gistfile1.cpp

#include <bits/stdc++.h>
#define pb push_back
#define MAXN 1000005
using namespace std;
typedef long long int lli;

lli N, M;
lli P, Q;
char A[MAXN];
char B[MAXN];
lli mark[1000002][28]={0};
lli g = 0, mcm = 0;
lli x = 0;
lli ans = 0;

void update(int gr, int idx, lli val){
	while(idx<=26){
		mark[gr][idx] += val;
		idx += (idx&(-idx));
	}
}
lli query(int gr, int idx){
	lli sum = 0;
	while(idx){
		sum += mark[gr][idx];
		idx -= (idx&(-idx));
	}
	return sum;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int i,j,k;
	lli l;
	int temp;
	cin>>N>>M;
	cin>>A>>B;
	P = strlen(A);
	Q = strlen(B);
	g = __gcd(P,Q);
	for(i=0; i<P; ++i){
		update((int)i%g, (int)((A[i]-'a')+1), 1);
	}
	for(i=0; i<Q; ++i){
		l = ((B[i]-'a')+1);
		temp = query((int)i%g, 26) - query((int)i%g, l);
		temp += query((int)i%g, l-1);
		ans += temp;
	}
	
	mcm = (P*Q)/__gcd(P,Q);
	x = (P*N)/mcm;
	ans = ans * x;
	cout << ans << "\n";
	return 0;
}