제출 #674890

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
674890		finn__	Osmosmjerka (COCI17_osmosmjerka)	C++17	140 / 160	4056 ms	33732 KiB

osmosmjerka

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

#define MOD ((1ULL << 61) - 1)
#define BASE 1000000009

vector<__uint128_t> p;
map<uint64_t, size_t> c;

void check_str(string const &s, size_t k, size_t n)
{
    vector<vector<uint64_t>> t(32, vector<uint64_t>(s.size()));
    for (size_t i = 0; i < s.size(); i++)
        t[0][i] = s[i];

    __uint128_t m = BASE;
    for (size_t i = 1; i < 32; i++)
    {
        for (size_t j = 0; j < s.size(); j++)
            t[i][j] = (t[i - 1][j] * m + t[i - 1][(j + (1 << (i - 1))) % s.size()]) % MOD;
        m = (m * m) % MOD;
    }

    for (size_t i = 0; i < n; i++)
    {
        __uint128_t m = BASE, h = 0;
        size_t j = i;
        for (size_t z = 0; z < 32; z++)
        {
            if (k & (1 << z))
            {
                h = (h * m + t[z][j]) % MOD;
                j = (j + (1 << z)) % s.size();
            }
            m = (m * m) % MOD;
        }
        c[h]++;
    }
}

uint64_t lcm(uint64_t a, uint64_t b)
{
    return (a / __gcd(a, b)) * b;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    size_t n, m, k;
    cin >> n >> m >> k;

    vector<string> y(n);
    for (string &s : y)
        cin >> s;

    p = vector<__uint128_t>(n + m);
    p[0] = 1;
    for (size_t i = 1; i < p.size(); i++)
        p[i] = (p[i - 1] * BASE) % MOD;

    for (size_t i = 0; i < n; i++)
    {
        check_str(y[i], k, m);
        reverse(y[i].begin(), y[i].end());
        check_str(y[i], k, m);
        reverse(y[i].begin(), y[i].end());
    }

    for (size_t j = 0; j < m; j++)
    {
        string s;
        for (size_t i = 0; i < n; i++)
            s.push_back(y[i][j]);
        check_str(s, k, n);
        reverse(s.begin(), s.end());
        check_str(s, k, n);
    }

    uint64_t l = lcm(n, m);

    for (size_t i = 0; i < n; i++)
    {
        string s;
        for (size_t j = 0; j < l; j++)
            s.push_back(y[(i + j) % n][j % m]);
        check_str(s, k, m);
        reverse(s.begin(), s.end());
        check_str(s, k, m);
    }

    for (size_t i = 0; i < n; i++)
    {
        string s;
        for (size_t j = 0; j < l; j++)
            s.push_back(y[(i - j + n * m) % n][j % m]);
        check_str(s, k, m);
        reverse(s.begin(), s.end());
        check_str(s, k, m);
    }

    uint64_t total = 0, all_pos = n * m * 8 * n * m * 8;
    for (auto const [h, x] : c)
        total += x * x;

    cout << total / __gcd(total, all_pos) << '/' << all_pos / __gcd(total, all_pos) << '\n';
}

• Subtask 1: 140 / 160