Submission #1006154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006154		BF001	Osmosmjerka (COCI17_osmosmjerka)	C++17	140 / 160	1313 ms	222036 KiB

osmosmjerka

#include <bits/stdc++.h>
using namespace std;

#define N 505
#define log 30
#define fi first
#define se second
#define int long long

typedef pair<int, int> ii;

ii par[log + 2][N][N];
int hsh[log + 2][N][N], pw[log + 2], base = 32, md = 1e9 + 7, n, m, len;
map<int, int> dd;

char s[N][N];

void solve(int dx, int dy){
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			hsh[0][i][j] = s[i][j] - 'a' + 1;
			par[0][i][j] = {(i + dx + n) % n, (j + dy + m) % m};
		}
	}
	pw[0] = base;
	for (int k = 1; k <= log; k++){
		pw[k] = pw[k - 1] * pw[k - 1] % md;
		for (int i = 0; i < n; i++){
			for (int j = 0; j < m; j++){
				par[k][i][j] = par[k - 1][par[k - 1][i][j].fi][par[k - 1][i][j].se];
				int x = par[k - 1][i][j].fi;
				int y = par[k - 1][i][j].se;
				hsh[k][i][j] = (hsh[k - 1][i][j] * pw[k - 1] % md + hsh[k - 1][x][y]) % md; 
			}
		}
	}

	int dis = len;

	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			int x = i, y = j;
			int cnt = 0;
			dis = len;
			for (int k = log; k >= 0; k--){
				if ((1ll << k) <= dis){
					dis -= (1ll << k);
					int tx = x;
					cnt = (cnt * pw[k] + hsh[k][x][y]) % md;
					x = par[k][x][y].fi;
					y = par[k][tx][y].se;
				}
			}
			dd[cnt]++;
		}
	}
}	

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
      
    cin >> n >> m >> len;
    for (int i = 0; i < n; i++){
    	for (int j = 0; j < m; j++) cin >> s[i][j];
    }  

	for (int i = -1; i <= 1; i++){
		for (int j = -1; j <= 1; j++){
			if (i == 0 && j == 0) continue;
			solve(i, j);
		}
	}

	int t = 0, mm = (n * m * 8) * (n * m * 8);
	for (auto x : dd){
		t += x.se * x.se;
	}

	int gcd = __gcd(t, mm);
	t /= gcd, mm /= gcd;

	cout << t << "/" << mm;

    return 0;
}     

• Subtask 1: 140 / 160