Submission #868031

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
868031	2023-10-30T09:12:57 Z	serifefedartar	Osmosmjerka (COCI17_osmosmjerka)	C++17	160 / 160	2313 ms	104580 KB

osmosmjerka

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9+9;
const ll LOGN = 30; 
const ll MAXN = 2e5 + 100;
const ll MULT = 1e9;

vector<string> grid;
ll all = 1, expected = 1, N, M, K;
map<ll,ll> mp;
const ll P = 31;
ll hashes[LOGN][550][550], pow2[LOGN], powP[LOGN];
void solve(int dx, int dy) {
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++)
			hashes[0][i][j] = (grid[i][j] - 'a' + 1);
	}

	for (int lg = 1; lg < LOGN; lg++) {
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++)
				hashes[lg][i][j] = (hashes[lg - 1][i][j] * powP[lg-1] % MOD + hashes[lg - 1][((i + dx * pow2[lg-1]) % M + MULT * M) % M][((j + dy * pow2[lg-1]) % N + MULT * N) % N]) % MOD;
		}
	}

	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			ll hash_val = 0;
			int now_i = i, now_j = j;
			for (int lg = 0; lg < LOGN; lg++) {
				if (pow2[lg] & K) {
					hash_val = (hash_val * powP[lg] % MOD + hashes[lg][now_i][now_j]) % MOD;
					now_i = ((now_i + dx * pow2[lg]) % M + MULT * M) % M;
					now_j = ((now_j + dy * pow2[lg]) % N + MULT * N) % N;
				}
			}
			mp[hash_val]++;
		}
	}
}

int main() {
	fast
	pow2[0] = 1; 
	powP[0] = P;
	for (int i = 1; i < LOGN; i++) {
		pow2[i] = pow2[i-1] * 2; 
		powP[i] = (powP[i-1] * powP[i-1]) % MOD;
	}
	cin >> M >> N >> K;

	grid = vector<string>(M);
	for (int i = 0; i < M; i++)
		cin >> grid[i];

	all = M * N * M * N * 8 * 8;
	for (int dx = -1; dx <= 1; dx++) {
		for (int dy = -1; dy <= 1; dy++) {
			if (!(dx == 0 && dy == 0))
				solve(dx, dy);
		}
	}

	for (auto u : mp)
		expected += u.s * u.s;
	expected--; 
	ll GCD = __gcd(all, expected);
	all /= GCD;
	expected /= GCD;
	cout << expected << "/" << all << "\n";
}

Subtask #1

160.0 / 160.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	59736 KB	Output is correct
2	Correct	7 ms	64092 KB	Output is correct
3	Correct	7 ms	64092 KB	Output is correct
4	Correct	8 ms	64088 KB	Output is correct
5	Correct	16 ms	68392 KB	Output is correct
6	Correct	61 ms	73044 KB	Output is correct
7	Correct	690 ms	89720 KB	Output is correct
8	Correct	2313 ms	104580 KB	Output is correct