Submission #586578

#	Time	Username	Problem	Language	Result	Execution time	Memory
586578		leeh18	Osmosmjerka (COCI17_osmosmjerka)	C++17	80 / 160	4065 ms	10068 KiB

osmosmjerka

#include <bits/stdc++.h>

template<__int128 p, __int128 m>
struct hash_string {
    static std::vector<__int128> power;
    std::vector<__int128> p_hash;
    hash_string(const std::string& s) : p_hash(s.size()+1, 0) {
        for (int i = 0; i < (int)s.size(); i++) {
            p_hash[i+1] = (p_hash[i] * p + s[i]) % m;
        }
    }
    __int128 pow(int i) {
        while (i >= (int)power.size()) {
            auto val = power.back();
            val = val * p % m;
            power.push_back(val);
        }
        return power[i];
    }
    __int128 pow(__int128 x, int i) {
        if (i == 0) return 1;
        auto ret = pow(x, i/2);
        ret = ret * ret % m;
        if (i & 1) ret = ret * x % m;
        return ret;
    }
    __int128 pow_sum(__int128 x, int i) {
        if (i == 1) return 1;
        auto ret = pow_sum(x, i/2);
        ret = (1 + pow(x, i/2)) % m * ret % m;
        if (i & 1) {
            ret = ret * x % m;
            ret = (ret + x) % m;
        }
        return ret;
    }
    __int128 hash(int l, int r) { // [l, r] inclusive
        assert(0 <= l && l <= r && r < (int)p_hash.size()-1);
        auto ret = p_hash[r+1] - p_hash[l] * pow(r-l+1) % m;
        ret = (ret + m) % m;
        return ret;
    }
    __int128 hash(int l, int r, int k) {
        int n = r - l + 1;
        __int128 ret = 0;
        if (k / n != 0) {
            ret = hash(l, r) * pow_sum(pow(n), k/n) % m;
        }
        if (k % n != 0) {
            ret = ret * pow(k % n) % m + hash(l, l + k % n - 1);
            ret %= m;
        }
        return ret;
    }
};

template<__int128 p, __int128 m>
std::vector<__int128> hash_string<p, m>::power {1};

struct hash_string2 {
    hash_string<9973, 9223372036854775783LL> s1;
    hash_string<9973, 9223372036854775643LL> s2;
    hash_string2(const std::string& s) : s1(s), s2(s) {}
    __int128 hash(int l, int r, int k) {
        return (s1.hash(l, r, k) << 64) | s2.hash(l, r, k);
    }
};

constexpr auto max = 501;
bool visited[max][max][4];

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int n, m, k;
    std::cin >> n >> m >> k;
    std::vector<std::string> v(n);
    for (auto &s : v) {
        std::cin >> s;
    }
    std::map<__int128, int64_t> cnt;
    auto update = [&](std::pair<int, int> start, int t) -> void {
        const std::array<std::pair<int, int>, 4> direction {{{1, 0}, {1, 1}, {1, -1}, {0, 1}}};
        auto [row, col] = start;
        if (visited[row][col][t]) return;
        const auto [dr, dc] = direction[t];
        std::string s;
        int loop_count = 0;
        while (!visited[row][col][t]) {
            assert(++loop_count <= std::max(n, m));
            visited[row][col][t] = true;
            s.push_back(v[row][col]);
            row = (row + dr + n) % n;
            col = (col + dc + m) % m;
        }
        int sz = int(std::size(s));
        s += s;
        hash_string2 hs(s);
        for (int i = 0; i < sz; i++) {
            auto hash = hs.hash(i, i+sz-1, k);
            ++cnt[hash];
        }
        std::reverse(s.begin(), s.end());
        hash_string2 hs_reversed(s);
        for (int i = 0; i < sz; i++) {
            auto hash = hs_reversed.hash(i, i+sz-1, k);
            ++cnt[hash];
        }
    };
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (int t = 0; t < 4; t++) {
                update({i, j}, t);
            }
        }
    }
    int64_t p = 0;
    int64_t q = 64 * n * n * m * m;
    for (auto [key, val] : cnt) {
        p += val * val;
    }
    auto g = std::gcd(p, q);
    std::cout << p/g << '/' << q/g << '\n';
}

• Subtask 1: 80 / 160