Submission #1291042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291042		vk3601h	Osmosmjerka (COCI17_osmosmjerka)	C++20	Compilation error	0 ms	0 KiB

osmosmjerka

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

// 使用 64 位哈希（自然溢出，相当于 mod 2^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};

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

    int M, N;
    long long K;
    if (!(cin >> M >> N >> K)) return 0;
    vector<string> g(M);
    for (int i = 0; i < M; ++i) cin >> g[i];

    const ull P = 911382323ull;           // 哈希基数（随便选个大的奇数）
    int MN = M * N;

    // 预处理 P^i，i 最大用到 MN（周期长度不会超过 MN）
    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);

    // 遍历 8 个方向
    for (int d = 0; d < 8; ++d) {
        int dx = DX[d], dy = DY[d];

        // 计算这个方向在 MxN 环面上的“步长周期” L_dir：
        // 找最小 t > 0 使得 t*dx ≡ 0 (mod M) 且 t*dy ≡ 0 (mod N)
        // 这个 t 就是沿该方向走回原位需要的步数，即每个轨道（cycle）的长度
        auto gcd = [](ll a, ll b) {
            while (b) { ll t = a % b; a = b; b = t; }
            return a;
        };
        auto lcm = [&](ll a, ll b) {
            return a / gcd(a, b) * b;
        };

        ll a, b;
        if (dx == 0) a = 1;
        else         a = M / gcd(std::llabs(dx), (ll)M);
        if (dy == 0) b = 1;
        else         b = N / gcd(std::llabs(dy), (ll)N);
        ll L_dir = lcm(a, b);            // 每条 cycle 的长度

        vector<char> visited(MN, 0);

        // 在这个方向上，把所有格子分解成若干条“环上的一维周期串”
        for (int start = 0; start < MN; ++start) {
            if (visited[start]) continue;

            // 收集当前 cycle 上的所有格子 id
            vector<int> nodes;
            nodes.reserve((int)L_dir);

            int x = start / N;
            int 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 = (int)nodes.size();   // 本周期串长度（应等于 L_dir）

            // 构造这个周期串 S 的前缀哈希：pref[i] = hash(S[0..i-1])
            // 哈希定义：h = (((c0)*P + c1)*P + ... )*P + c_{L-1}
            vector<ull> pref(L + 1);
            pref[0] = 0;
            for (int i = 0; i < L; ++i) {
                int id = nodes[i];
                char ch = g[id / N][id % N];
                ull v = (ull)(ch - 'a' + 1);
                pref[i + 1] = pref[i] * P + v;
            }

            // 整个周期串 S 的哈希和长度对应的 P^len
            ull H_S  = pref[L];
            ull powL = powP[L];          // P^L

            // 预处理 S^(2^k) 的哈希与对应的 P^{len}，用于快速幂
            vector<pair<ull, ull>> basePow;  // (hash, P^{len})
            vector<ll> lenPow;               // len = L * 2^k
            basePow.reserve(64);
            lenPow.reserve(64);

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

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

                // S^{2*len} = (S^len)(S^len)
                ull h2 = h * p + h;      // hash(A+A) = hash(A)*P^{|A|} + hash(A)
                ull p2 = p * p;          // P^{2*len} = (P^{len})^2
                ll  l2 = len * 2;

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

            // 快速求 S^t 的 (hash, P^{len})，使用二进制分解
            auto pow_repeat = [&](ll t) -> pair<ull, ull> {
                ull h_res = 0;      // 空串 hash = 0
                ull p_res = 1;      // 空串 P^{len} = 1 (len=0)

                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;
                        // 拼接: res = res + block
                        // hash(res+block) = h1 * P^{len(block)} + h2
                        h_res = h1 * p2 + h2;
                        p_res = p1 * p2;
                    }
                    t >>= 1;
                    ++bit;
                }
                return {h_res, p_res};
            };

            // 对于这个周期上的每一个起点 p，构造长度为 K 的单词的哈希
            for (int p = 0; p < L; ++p) {
                ll rem = K;                 // 剩余要取的长度
                ull h_cur = 0;              // 当前已拼单词的哈希
                ull p_cur = 1;              // 当前单词长度对应的 P^{len}

                // 1) 先取从位置 p 到周期末尾的那一段（最多 L-p，不能超过 rem）
                ll len1 = min(rem, (ll)L - p);
                if (len1 > 0) {
                    // 子串 S[p .. p+len1-1] 的哈希：
                    // hash = pref[p+len1] - pref[p]*P^{len1}
                    ull hFirst = pref[p + len1] - pref[p] * powP[len1];
                    ull pFirst = powP[len1]; // P^{len1}

                    // 拼接：cur = cur + first
                    ull h1 = h_cur, pp1 = p_cur;
                    ull h2 = hFirst, pp2 = pFirst;
                    h_cur = h1 * pp2 + h2;
                    p_cur = pp1 * pp2;

                    rem -= len1;
                }

                if (rem > 0) {
                    // 2) 中间部分是若干个完整的周期串 S
                    ll t_full  = rem / L;       // 完整周期串个数
                    ll lenLast = rem % L;       // 最后剩余的一小段

                    if (t_full > 0) {
                        auto mid = pow_repeat(t_full);   // (hash(S^t), P^{lenMid})
                        ull h1 = h_cur, pp1 = p_cur;
                        ull h2 = mid.first, pp2 = mid.second;
                        h_cur = h1 * pp2 + h2;
                        p_cur = pp1 * pp2;
                    }

                    // 3) 最后再取从 S[0..lenLast-1] 的那一段
                    if (lenLast > 0) {
                        ull hLast = pref[lenLast];   // 从 0 开始的子串
                        ull pLast = powP[lenLast];
                        ull h1 = h_cur, pp1 = p_cur;
                        ull h2 = hLast, pp2 = pLast;
                        h_cur = h1 * pp2 + h2;
                        p_cur = pp1 * pp2;
                    }
                }

                all_hashes.push_back(h_cur);
            }
        }
    }

    // 统计每个单词出现次数 X，累加 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 = (ll)(j - i);
        num += cnt * cnt;
        i = j;
    }

    ll T = 8ll * M * N;       // 所有起点+方向总数
    ll den = T * T;           // T^2

    ll g = std::gcd(num, den);
    num /= g;
    den /= g;

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

Compilation message (stderr)

osmosmjerka.cpp: In function 'int main()':
osmosmjerka.cpp:206:8: error: conflicting declaration 'll g'
  206 |     ll g = std::gcd(num, den);
      |        ^
osmosmjerka.cpp:19:20: note: previous declaration as 'std::vector<std::__cxx11::basic_string<char> > g'
   19 |     vector<string> g(M);
      |                    ^
osmosmjerka.cpp:207:9: error: no match for 'operator/=' (operand types are 'll' {aka 'long long int'} and 'std::vector<std::__cxx11::basic_string<char> >')
  207 |     num /= g;
      |     ~~~~^~~~
osmosmjerka.cpp:208:9: error: no match for 'operator/=' (operand types are 'll' {aka 'long long int'} and 'std::vector<std::__cxx11::basic_string<char> >')
  208 |     den /= g;
      |     ~~~~^~~~