Submission #1311654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311654		hansen	Osmosmjerka (COCI17_osmosmjerka)	C++20	120 / 160	2979 ms	35304 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 fi first
#define se second
#define pb push_back

mt19937 rng((int)chrono::steady_clock::now().time_since_epoch().count());
int hashp = uniform_int_distribution<int>(257, 1e9)(rng);
int hashm1 = 1e9+7;

int be(int cur, int exp){
    if(exp == 0) return 1;
    int res = 1;
    while(exp){
        if(exp % 2 == 0){
            exp >>= 1;
            cur *= cur;
            cur %= hashm1;
        } else{
            exp--;
            res *= cur;
            res %= hashm1;
        }
    }
    return res;
}

long long gs(long long r, long long n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (n % 2 == 0) {
        long long half_sum = gs(r, n / 2);
        long long multiplier = (1 + be(r, n / 2)) % hashm1;
        return (half_sum * multiplier) % hashm1;
    } else {
        return (1 + r * gs(r, n - 1)) % hashm1;
    }
}

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<int, int> mp;
    
    int max_len = m * n + 5;
    vector<int> p(max_len, 1);
    for(int i = 1; i < max_len; i++){
        p[i] = (p[i-1]*hashp) % hashm1;
    }

    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> end(sz, 0);
                end[0] = line[0];
                for(int x = 1; x < sz; x++){
                    end[x] = (end[x-1] * hashp + line[x]) % hashm1;
                }

                for(int x = 0; x < sz; x++){
                    int total_reps = k / sz;
                    int rem = k % sz;
                    
                    int prev = (x == 0) ? 0 : end[x-1];
                    int part1 = (end[sz-1] - (prev * p[sz-x]) % hashm1 + hashm1) % hashm1;
                    int rot_hash = part1;
                    if(x > 0) {
                        rot_hash = (rot_hash * p[x] + end[x-1]) % hashm1;
                    }

                    int term1 = (rot_hash * gs(p[sz], total_reps)) % hashm1;
                    int final_hash = (term1 * p[rem]) % hashm1;

                    if (rem > 0) {
                        int rem_hash;
                        if(x + rem <= sz) {
                            int prev_rem = (x == 0) ? 0 : end[x-1];
                            rem_hash = (end[x+rem-1] - (prev_rem * p[rem]) % hashm1 + hashm1) % hashm1;
                        } else {
                            int first_chunk_len = sz - x;
                            int second_chunk_len = rem - first_chunk_len;
                            
                            int prev_wrap = (x == 0) ? 0 : end[x-1];
                            int h1 = (end[sz-1] - (prev_wrap * p[first_chunk_len]) % hashm1 + hashm1) % hashm1;
                            int h2 = end[second_chunk_len-1];
                            
                            rem_hash = (h1 * p[second_chunk_len] + h2) % hashm1;
                        }
                        final_hash = (final_hash + rem_hash) % hashm1;
                    }
                    
                    mp[final_hash]++;
                }
            }
        }
    }

    __int128 num = 0;
    for(auto &pi : mp){
        num += (__int128)pi.second * pi.second;
    }
    
    __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;
}

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

• Subtask 1: 120 / 160