Submission #1311656

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311656		hansen	Osmosmjerka (COCI17_osmosmjerka)	C++20	160 / 160	144 ms	41716 KiB

osmosmjerka

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define int long long
#define pb push_back

typedef gp_hash_table<int, int> hash_map;

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() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int m, n, k;
    if (!(cin >> m >> n >> k)) return;
    
    vector<string> a(m);
    for (int i = 0; i < m; i++) cin >> a[i];

    hash_map 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};

    vector<int> line, h1, h2;
    line.reserve(max_len);
    h1.reserve(max_len);
    h2.reserve(max_len);

    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;

                line.clear();
                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();
                
                if ((int)h1.size() < sz) {
                    h1.resize(sz);
                    h2.resize(sz);
                }

                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;
                }
                
                int total_reps = k / sz;
                int rem = k % sz;
                int gs1 = gs(p1[sz], total_reps, MOD1);
                int gs2 = gs(p2[sz], total_reps, MOD2);

                for (int x = 0; x < sz; x++) {
                    int prev1 = (x == 0) ? 0 : h1[x - 1];
                    int rot1 = (h1[sz - 1] - (prev1 * p1[sz - x]) % MOD1 + MOD1); 
                    if (rot1 >= MOD1) rot1 -= MOD1;
                    
                    if (x > 0) {
                        rot1 = (rot1 * p1[x] + h1[x - 1]) % MOD1;
                    }

                    int term1_1 = (rot1 * gs1) % 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);
                    if (rot2 >= MOD2) rot2 -= MOD2;
                    
                    if (x > 0) {
                        rot2 = (rot2 * p2[x] + h2[x - 1]) % MOD2;
                    }

                    int term1_2 = (rot2 * gs2) % 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);
                            if(rem1 >= MOD1) rem1 -= MOD1;

                            int p_rem2 = (x == 0) ? 0 : h2[x - 1];
                            rem2 = (h2[x + rem - 1] - (p_rem2 * p2[rem]) % MOD2 + MOD2);
                            if(rem2 >= MOD2) rem2 -= 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);
                            if(chunk1_1 >= MOD1) chunk1_1 -= 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);
                            if(chunk2_1 >= MOD2) chunk2_1 -= MOD2;
                            int chunk2_2 = h2[len2 - 1];
                            rem2 = (chunk2_1 * p2[len2] + chunk2_2) % MOD2;
                        }
                        final1 = (final1 + rem1) % MOD1;
                        final2 = (final2 + rem2) % MOD2;
                    }

                    int combined_key = (final1 << 32) | final2;
                    mp[combined_key]++;
                }
            }
        }
    }

    __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() {
    solve();
    return 0;
}

• Subtask 1: 160 / 160