Submission #1247870

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247870		Abdo_Eid	Osmosmjerka (COCI17_osmosmjerka)	C++20	60 / 160	275 ms	19692 KiB

osmosmjerka

#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 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.push_back(1);
        hsh.push_back(0);

        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, pw[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);
    }

    ll duplicate(int val, int k) {
        if (k == 0) return 0;

        ll ret = duplicate(val, k >> 1);
        ret = merge(ret, ret, k >> 1);
        if (k % 2) ret = merge(ret, val, n);

        return ret;
    }

    ll getByStart(int i) {
        return merge(get(i, n - 1), get(0, i - 1), 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, int> 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 = pow(1ll * n * m * 8, 2);
    ll num = 0, sum = 0;
    for (auto& [k, v] : mp) {
        num += v * v;
        sum += 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();
}

• Subtask 1: 60 / 160