Submission #1247898

#TimeUsernameProblemLanguageResultExecution timeMemory
1247898Abdo_EidOsmosmjerka (COCI17_osmosmjerka)C++20
140 / 160
2037 ms41312 KiB
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define all(a) a.begin(), a.end()
#define allr(a) a.rbegin(), a.rend()

const int N = 5e2 + 1;
int vis[N][N][8], 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 = "";

    while (!vis[r][c][d]) {
        res += grid[r][c];
        vis[r][c][d] = true;
        r = (r + dr[d] + n) % n;
        c = (c + dc[d] + m) % m;
    }

    return res;
}

struct Hash {
    const ll M = 1e9 + 9;
    const ll P = 9973;
    int n;

    vector<ll> pw, hsh;
    ll inv_p;  // Modular inverse of P

    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;
    }

    ll fpow(ll a, ll b) {
        if (!b) return 1;
        ll x = fpow(a, b >> 1);
        x = mul(x, x);
        if (b & 1) x = mul(x, a);
        return x;
    }

    Hash(string s) {
        n = s.size();
        pw.push_back(1);
        hsh.push_back(0);
        inv_p = fpow(P, M - 2);  // Fermat's little theorem for modular inverse

        for (int i = 1; i <= n; i++) {
            pw.push_back(mul(pw.back(), P));
            hsh.push_back(add(s[i - 1], mul(hsh.back(), 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, fpow(P, rsize)));
    }

    ll getByLen(int l, int len) {
        if (len == 0) return 0;
        int end = (l + len - 1) % n;

        if (l <= end) return get(l, end);
        return merge(get(l, n - 1), get(0, end), end + 1);
    }

    // Mathematical O(1) duplicate function
    ll duplicate(ll val, int k) {
        if (k == 0) return 0;
        if (k == 1) return val;

        // Hash of k copies = val * (P^(n*k) - 1) / (P^n - 1)
        // This is the formula for geometric series sum

        ll p_n = fpow(P, n);             // P^n
        ll p_nk = fpow(P, 1ll * n * k);  // P^(n*k)

        ll numerator = sub(p_nk, 1);   // P^(n*k) - 1
        ll denominator = sub(p_n, 1);  // P^n - 1

        // Multiply by val and divide by denominator
        // Since we're in modular arithmetic, division = multiplication by modular inverse
        ll denom_inv = fpow(denominator, M - 2);

        return mul(val, mul(numerator, denom_inv));
    }

    ll getByStart(int i) {
        return getByLen(i, n);
    }
};

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++) {
                if (vis[r][c][d]) continue;

                string s = get_path(r, c, d);
                Hash hsh(s);

                int len = s.size();
                int cnt = k / len, remain = k % len;

                for (int i = 0; i < len; i++) {
                    ll cur = hsh.getByStart(i);
                    cur = hsh.duplicate(cur, cnt);
                    ll other = hsh.getByLen(i, remain);

                    cur = hsh.merge(cur, other, remain);
                    ++mp[cur];
                }
            }
    ll den = 1ll * n * m * 8;
    den *= den;
    ll num = 0;
    for (auto& [k, v] : mp) {
        num += v * v;
    }
    ll GCD = gcd(num, den);
    num /= GCD;
    den /= GCD;
    cout << num << "/" << den << endl;
}

int main() {
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL), cout.tie(NULL);

    int t = 1;
    // cin >> t;
    while (t--) solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...