oj.uz

Submission #674890

# Submission time Handle Problem Language Result Execution time Memory
674890 2022-12-26T13:01:24 Z finn__ Osmosmjerka (COCI17_osmosmjerka) C++17
140 / 160
 4000 ms 33732 KB 
#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.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 5 ms 340 KB Output is correct
5 Correct 17 ms 452 KB Output is correct
6 Correct 2233 ms 5356 KB Output is correct
7 Execution timed out 4056 ms 21640 KB Time limit exceeded
8 Correct 3275 ms 33732 KB Output is correct