Submission #1247886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247886		Abdo_Eid	Osmosmjerka (COCI17_osmosmjerka)	C++20	80 / 160	4098 ms	327680 KiB

osmosmjerka

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

const int N = 5e2 + 1;
int n, m, k;
char grid[N][N];
const int dr[] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dc[] = {1, -1, 0, 1, -1, 1, -1, 0};

string get_path(int r, int c, int d) {
    string res;
    for (int step = 0; step < k; step++) {
        res += grid[r][c];
        r = (r + dr[d] + n) % n;
        c = (c + dc[d] + m) % m;
    }
    return res;
}

struct Hash {
    const int M = 1e9 + 9;
    const int P = 9973;
    int n;
    vector<ll> pw, hsh;

    ll mul(ll a, ll b) { return (a * b) % M; }
    ll add(ll a, ll b) { return (a + b) % M; }
    ll sub(ll a, ll b) { return (a - b + M) % M; }

    Hash(string s) {
        n = s.size();
        pw.resize(k + 1);  // Precompute up to k
        hsh.resize(n + 1);
        pw[0] = 1;
        hsh[0] = 0;
        for (int i = 1; i <= n; i++) {
            pw[i] = mul(pw[i - 1], P);
            hsh[i] = add(s[i - 1], mul(hsh[i - 1], P));
        }
        for (int i = n + 1; i <= k; i++) {
            pw[i] = mul(pw[i - 1], P);
        }
    }

    ll get(int l, int r) {
        return sub(hsh[r + 1], mul(hsh[l], pw[r - l + 1]));
    }

    ll merge(ll lval, ll rval, int rsize) {
        return add(rval, mul(lval, pw[rsize]));
    }

    ll getByStart(int i) {
        return merge(get(i, n - 1), get(0, i - 1), n - i);
    }
};

void solve() {
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> grid[i][j];

    map<ll, ll> mp;
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < m; c++) {
            for (int d = 0; d < 8; d++) {
                string s = get_path(r, c, d);
                Hash hsh(s);
                ll full_hash = hsh.get(0, k - 1);
                mp[full_hash]++;
            }
        }
    }

    ll den = (1ll * n * m * 8) * (1ll * n * m * 8);
    ll num = 0;
    for (auto& [hash, cnt] : mp) {
        num += 1ll * cnt * cnt;
    }

    if (num == 0) {
        cout << "0/1" << endl;
    } else {
        ll GCD = gcd(num, den);
        cout << num / GCD << "/" << den / GCD << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    while (t--) solve();
    return 0;
}

• Subtask 1: 80 / 160