Submission #443545

#	Time	Username	Problem	Language	Result	Execution time	Memory
443545		nhuang685	Osmosmjerka (COCI17_osmosmjerka)	C++17	100 / 160	4080 ms	10368 KiB

osmosmjerka

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

const ll P = 9973;
const ll MOD = 1e9 + 9;

int M, N, K;
string grid[500];
unordered_map<ll, ll> cnt;
vector<int> dx, dy;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    // freopen("input.txt", "r", stdin);
    cin >> M >> N >> K;
    K = min(lcm(M, N), K);

    dx = {M - 1, M - 1, 0, 1, 1, 1, 0, M - 1};
    dy = {0, 1, 1, 1, 0, N - 1, N - 1, N - 1};

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

    ll num = 0;
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N; ++j) {
            for (int d = 0; d < 8; ++d) {
                int x = i;
                int y = j;
                ll ppow = 1;
                ll hash_val = 0;

                for (int k = 0; k < K; ++k) {
                    hash_val = (hash_val + (grid[x][y] - 'a' + 1) * ppow) % MOD;
                    ppow = (ppow * P) % MOD;
                    x = (x + dx[d]) % M;
                    y = (y + dy[d]) % N;
                }
                cnt[hash_val]++;
                num++;
            }
        }
    }

    ll numerator = 0;
    ll denominator = num * num;
    for (auto i : cnt) {
        numerator += i.second * i.second;
    }

    ll g = gcd(numerator, denominator);
    cout << numerator / g << "/" << denominator / g << '\n';
}

• Subtask 1: 100 / 160