Submission #1311655

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311655		hansen	Osmosmjerka (COCI17_osmosmjerka)	C++20	140 / 160	4091 ms	27052 KiB

osmosmjerka

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

#define int long long
#define pb push_back

const int MOD1 = 1e9 + 7;
const int MOD2 = 1e9 + 9;

mt19937 rng((int)chrono::steady_clock::now().time_since_epoch().count());
int P1 = uniform_int_distribution<int>(257, 1e9)(rng);
int P2 = uniform_int_distribution<int>(257, 1e9)(rng);

int power(int base, int exp, int mod) {
    int res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

int gs(int r, int n, int mod) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (n % 2 == 0) {
        int half = gs(r, n / 2, mod);
        int mul = (1 + power(r, n / 2, mod)) % mod;
        return (half * mul) % mod;
    } else {
        return (1 + r * gs(r, n - 1, mod)) % mod;
    }
}

void solve() {
    int m, n, k;
    cin >> m >> n >> k;
    vector<string> a(m);
    for (int i = 0; i < m; i++) cin >> a[i];

    map<pair<int, int>, int> mp;

    int max_len = m * n + 5;
    
    vector<int> p1(max_len, 1), p2(max_len, 1);
    for (int i = 1; i < max_len; i++) {
        p1[i] = (p1[i - 1] * P1) % MOD1;
        p2[i] = (p2[i - 1] * P2) % MOD2;
    }

    int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1};
    int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};

    for (int d = 0; d < 8; d++) {
        vector<vector<bool>> vis(m, vector<bool>(n, false));

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (vis[i][j]) continue;

                vector<int> line;
                int r = i, c = j;
                while (!vis[r][c]) {
                    vis[r][c] = true;
                    line.pb(a[r][c]);
                    r = (r + dx[d] + m) % m;
                    c = (c + dy[d] + n) % n;
                }

                int sz = line.size();
                
                vector<int> h1(sz, 0), h2(sz, 0);
                h1[0] = line[0];
                h2[0] = line[0];
                
                for (int x = 1; x < sz; x++) {
                    h1[x] = (h1[x - 1] * P1 + line[x]) % MOD1;
                    h2[x] = (h2[x - 1] * P2 + line[x]) % MOD2;
                }

                for (int x = 0; x < sz; x++) {
                    int total_reps = k / sz;
                    int rem = k % sz;

                    int prev1 = (x == 0) ? 0 : h1[x - 1];
                    int rot1 = (h1[sz - 1] - (prev1 * p1[sz - x]) % MOD1 + MOD1) % MOD1;
                    if (x > 0) rot1 = (rot1 * p1[x] + h1[x - 1]) % MOD1;
                    
                    int term1_1 = (rot1 * gs(p1[sz], total_reps, MOD1)) % MOD1;
                    int final1 = (term1_1 * p1[rem]) % MOD1;
                    
                    int prev2 = (x == 0) ? 0 : h2[x - 1];
                    int rot2 = (h2[sz - 1] - (prev2 * p2[sz - x]) % MOD2 + MOD2) % MOD2;
                    if (x > 0) rot2 = (rot2 * p2[x] + h2[x - 1]) % MOD2;

                    int term1_2 = (rot2 * gs(p2[sz], total_reps, MOD2)) % MOD2;
                    int final2 = (term1_2 * p2[rem]) % MOD2;

                    if (rem > 0) {
                        int rem1, rem2;
                        if (x + rem <= sz) {
                            int p_rem1 = (x == 0) ? 0 : h1[x - 1];
                            rem1 = (h1[x + rem - 1] - (p_rem1 * p1[rem]) % MOD1 + MOD1) % MOD1;

                            int p_rem2 = (x == 0) ? 0 : h2[x - 1];
                            rem2 = (h2[x + rem - 1] - (p_rem2 * p2[rem]) % MOD2 + MOD2) % MOD2;
                        } else {
                            int len1 = sz - x;
                            int len2 = rem - len1;

                            int p_wrap1 = (x == 0) ? 0 : h1[x - 1];
                            int chunk1_1 = (h1[sz - 1] - (p_wrap1 * p1[len1]) % MOD1 + MOD1) % MOD1;
                            int chunk1_2 = h1[len2 - 1];
                            rem1 = (chunk1_1 * p1[len2] + chunk1_2) % MOD1;

                            int p_wrap2 = (x == 0) ? 0 : h2[x - 1];
                            int chunk2_1 = (h2[sz - 1] - (p_wrap2 * p2[len1]) % MOD2 + MOD2) % MOD2;
                            int chunk2_2 = h2[len2 - 1];
                            rem2 = (chunk2_1 * p2[len2] + chunk2_2) % MOD2;
                        }
                        final1 = (final1 + rem1) % MOD1;
                        final2 = (final2 + rem2) % MOD2;
                    }

                    mp[{final1, final2}]++;
                }
            }
        }
    }

    __int128 num = 0;
    for (auto const& [key, val] : mp) {
        num += (__int128)val * val;
    }

    __int128 total = (__int128)m * n * 8;
    __int128 denom = total * total;

    __int128 cd = std::gcd((long long)num, (long long)denom);
    num /= cd;
    denom /= cd;

    cout << (long long)num << "/" << (long long)denom << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

• Subtask 1: 140 / 160