oj.uz

Submission #200218

# Submission time Handle Problem Language Result Execution time Memory
200218 2020-02-05T17:14:06 Z MetB Osmosmjerka (COCI17_osmosmjerka) C++14
100 / 160
 3227 ms 116588 KB 
#include <bits/stdc++.h>
 
#define N 1000001
#define f first
#define s second
 
using namespace std;
 
typedef long long ll;
 
const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e6 + 3;

int n, m, k;
ll p = 37;
pair <ll, ll> d[501][501][21], pm[N];
string s[1000];
map <pair <ll, ll>, ll> mp;

pair <ll, ll> query (int x, int y, int h, int v, int k) {
	pair <ll, ll> sum = {0, 0}, mult = {1, 1};

	for (int i = 0; i <= 20; i++) {
		if (k & (1 << i)) {
			sum.f = (sum.f + d[x][y][i].f * mult.f % MOD) % MOD;
			sum.s = (sum.s + d[x][y][i].s * mult.s % MOD2) % MOD2;
			x = (x + (n + h) * (1 << i)) % n;
			y = (y + (m + v) * (1 << i)) % m;
			mult.f = (mult.f * pm[i].f) % MOD;
			mult.s = (mult.s * pm[i].s) % MOD2;
		}
	}

	return sum;
}

ll gcd (ll a, ll b) {
	if (!b) return a;
	return gcd (b, a % b);
}

int main () {
	cin >> n >> m >> k;
	k = min (k, n * m);

	for (int i = 0; i < n; i++)
		cin >> s[i];

	pm[0] = {p, p};

	for (int i = 1; i <= 20; i++) {
		pm[i].f = pm[i-1].f * pm[i-1].f % MOD;
		pm[i].s = pm[i-1].s * pm[i-1].s % MOD;
	}

	for (int h = -1; h <= 1; h++)
		for (int v = -1; v <= 1; v++) {
			if (!h && !v) continue;

			for (int i = 0; i < n; i++)
				for (int j = 0; j < m; j++) {
					d[i][j][0].f = s[i][j] - 'a';
					d[i][j][0].s = s[i][j] - 'a';
				}

			for (int w = 0; w < 20; w++)
				for (int i = 0; i < n; i++) {
					for (int j = 0; j < m; j++) {
						int nx = (i + (n + h) * (1 << w)) % n;
						int ny = (j + (m + v) * (1 << w)) % m;
						d[i][j][w+1].f = (d[i][j][w].f + d[nx][ny][w].f * pm[w].f % MOD) % MOD;
						d[i][j][w+1].s = (d[i][j][w].s + d[nx][ny][w].s * pm[w].s % MOD2) % MOD2;
					}
				}

			for (int i = 0; i < n; i++)
				for (int j = 0; j < m; j++) {
					mp[query (i, j, h, v, k)]++;
				}
		}

	ll ans = 0, all = (n * m * 8) * (n * m * 8);
	for (auto a : mp) {
		ans += a.second * a.second;
	}

	cout << ans / gcd (ans, all) << "/" << all / gcd (ans, all);
}

Subtask #1
100.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 380 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 7 ms 632 KB Output is correct
5 Correct 12 ms 1144 KB Output is correct
6 Incorrect 54 ms 6264 KB Output isn't correct
7 Incorrect 841 ms 40240 KB Output isn't correct
8 Incorrect 3227 ms 116588 KB Output isn't correct