제출 #1291043

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291043		vk3601h	Osmosmjerka (COCI17_osmosmjerka)	C++20	160 / 160	152 ms	18580 KiB

osmosmjerka

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

// 使用 64 位哈希（自然溢出）
using ull = unsigned long long;
using ll = long long;

// 8 个方向
const int DX[8] = {-1, 1, 0, 0, -1,  1, -1,  1};
const int DY[8] = { 0, 0,-1, 1, -1, -1,  1,  1};

ll gcdll(ll a, ll b) {
    while (b) {
        ll t = a % b;
        a = b;
        b = t;
    }
    return a;
}
ll lcmll(ll a, ll b) {
    return a / gcdll(a, b) * b;
}

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

    int M, N;
    ll K;
    cin >> M >> N >> K;

    vector<string> grid(M);   // 改名，不再叫 g
    for (int i = 0; i < M; ++i) cin >> grid[i];

    const ull P = 911382323ull;
    int MN = M * N;

    // 预处理 P^i
    vector<ull> powP(MN + 1);
    powP[0] = 1;
    for (int i = 1; i <= MN; ++i) {
        powP[i] = powP[i - 1] * P;
    }

    vector<ull> all_hashes;
    all_hashes.reserve(8ll * MN);

    for (int d = 0; d < 8; ++d) {
        int dx = DX[d], dy = DY[d];

        // 求沿此方向的周期长度 L_dir
        ll a, b;
        if (dx == 0) a = 1;
        else         a = M / gcdll(llabs(dx), (ll)M);

        if (dy == 0) b = 1;
        else         b = N / gcdll(llabs(dy), (ll)N);

        ll L_dir = lcmll(a, b);

        vector<char> visited(MN, 0);

        for (int start = 0; start < MN; ++start) {
            if (visited[start]) continue;

            vector<int> nodes;
            nodes.reserve((int)L_dir);

            int x = start / N, y = start % N;
            for (int step = 0; step < L_dir; ++step) {
                int id = x * N + y;
                visited[id] = 1;
                nodes.push_back(id);

                x += dx; if (x < 0) x += M; else if (x >= M) x -= M;
                y += dy; if (y < 0) y += N; else if (y >= N) y -= N;
            }

            int L = nodes.size();

            // 构造周期串前缀哈希
            vector<ull> pref(L + 1);
            pref[0] = 0;
            for (int i = 0; i < L; ++i) {
                int id = nodes[i];
                char ch = grid[id / N][id % N];
                ull v = (ull)(ch - 'a' + 1);
                pref[i + 1] = pref[i] * P + v;
            }

            ull H_S = pref[L];
            ull powL = powP[L];

            vector<pair<ull, ull>> basePow;
            vector<ll> lenPow;
            basePow.reserve(64);
            lenPow.reserve(64);

            basePow.push_back({H_S, powL});
            lenPow.push_back(L);

            while (lenPow.back() * 2 <= K) {
                ull h = basePow.back().first;
                ull p = basePow.back().second;
                ll len = lenPow.back();

                ull h2 = h * p + h;       // S^2 = S + S
                ull p2 = p * p;
                ll  l2 = len * 2;

                basePow.push_back({h2, p2});
                lenPow.push_back(l2);
            }

            auto pow_repeat = [&](ll t) {
                ull h_res = 0;
                ull p_res = 1;
                int bit = 0;
                while (t > 0) {
                    if (t & 1) {
                        ull h1 = h_res, p1 = p_res;
                        ull h2 = basePow[bit].first;
                        ull p2 = basePow[bit].second;
                        h_res = h1 * p2 + h2;
                        p_res = p1 * p2;
                    }
                    t >>= 1;
                    bit++;
                }
                return pair<ull, ull>(h_res, p_res);
            };

            // 为本周期上每个起点生成长度 K 的单词哈希
            for (int p = 0; p < L; ++p) {
                ll rem = K;
                ull h_cur = 0;
                ull p_cur = 1;

                // 先取 p 到周期末尾
                ll len1 = min(rem, (ll)L - p);
                if (len1 > 0) {
                    ull hFirst = pref[p + len1] - pref[p] * powP[len1];
                    ull pFirst = powP[len1];
                    h_cur = h_cur * pFirst + hFirst;
                    p_cur = p_cur * pFirst;
                    rem -= len1;
                }

                if (rem > 0) {
                    ll t_full = rem / L;
                    ll lenLast = rem % L;

                    if (t_full > 0) {
                        auto mid = pow_repeat(t_full);
                        h_cur = h_cur * mid.second + mid.first;
                        p_cur = p_cur * mid.second;
                    }
                    if (lenLast > 0) {
                        ull hLast = pref[lenLast];
                        ull pLast = powP[lenLast];
                        h_cur = h_cur * pLast + hLast;
                        p_cur = p_cur * pLast;
                    }
                }

                all_hashes.push_back(h_cur);
            }
        }
    }

    // 统计 X^2
    sort(all_hashes.begin(), all_hashes.end());
    ll num = 0;
    for (size_t i = 0; i < all_hashes.size(); ) {
        size_t j = i + 1;
        while (j < all_hashes.size() && all_hashes[j] == all_hashes[i]) j++;
        ll cnt = j - i;
        num += cnt * cnt;
        i = j;
    }

    ll T = 8ll * M * N;
    ll den = T * T;

    ll gg = gcdll(num, den);  // 不再叫 g，避免冲突
    num /= gg;
    den /= gg;

    cout << num << "/" << den << "\n";
    return 0;
}

• Subtask 1: 160 / 160