제출 #1291053

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291053		vk3601h	Osmosmjerka (COCI17_osmosmjerka)	C++20	100 / 160	691 ms	18292 KiB

osmosmjerka

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

long long rng(long long low, long long high){
    static mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
    return uniform_int_distribution<long long>(low, high)(gen);
}

const long long M = (1ll << 61) - 1;
const long long B = rng((1ll << 20), (1ll << 40));

const int DX[8] = {-1, 1, 0, 0, -1, 1, -1, 1};
const int DY[8] = {0, 0, -1, 1, -1, -1, 1, 1};

long long mod_mul(long long a, long long b) {return (__int128)a * b % M;}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int row_num, col_num, len;
    cin >> row_num >> col_num >> len;
    int size = row_num * col_num;

    vector<string> grid(row_num);
    for (string &str : grid) cin >> str;

    vector<long long> pow(size + 1);
    pow[0] = 1;
    for (int i = 1; i <= size; i++) pow[i] = mod_mul(pow[i - 1], B);

    vector<long long> all_hashes;
    all_hashes.reserve(8 * size);

    for (int d = 0; d < 8; d++){
        int dx = DX[d], dy = DY[d];

        int a = 0, b = 0;
        if (dx == 0) a = 1;
        else a = row_num / __gcd(row_num, abs(dx));
        if (dy == 0) b = 1;
        else b = col_num / __gcd(col_num, abs(dy));
        int L_dir = a * b / __gcd(a, b);

        vector<bool> visited(size, false);
        for (int start = 0; start < size; start++){
            if (visited[start]) continue;

            vector<int> nodes;
            nodes.reserve(L_dir);

            int x = start / col_num, y = start % col_num;
            for (int step = 0; step < L_dir; step++){
                int id = x * col_num + y;
                visited[id] = true;
                nodes.push_back(id);
                (x += dx + row_num) %= row_num;
                (y += dy + col_num) %= col_num;
            }

            vector<long long> p_hash(L_dir + 1);
            p_hash[0] = 0;
            for (int i = 0; i < L_dir; i++){
                int id = nodes[i];
                p_hash[i + 1] = (mod_mul(p_hash[i], B) + grid[id / col_num][id % col_num]) % M;
            }

            auto pow_repeat = [&](long long exp){
                pair<long long, long long> base = {p_hash[L_dir], pow[L_dir]};
                pair<long long, long long> res = {0, 1};

                while (exp){
                    if (exp & 1){
                        res.first = (mod_mul(res.first, base.second) + base.first) % M;
                        res.second = mod_mul(res.second, base.second);
                    }

                    base.first = (mod_mul(base.first, base.second) + base.first) % M;
                    base.second = mod_mul(base.second, base.second);

                    exp >>= 1;
                }

                return res;
            };

            for (int p = 0; p < L_dir; p++){
                int rem = len;
                long long curr_hash = 0, curr_pow = 1;

                int first_len = min(rem, L_dir - p);
                if (first_len > 0){
                    long long first_hash = (p_hash[p + first_len] - mod_mul(p_hash[p], pow[first_len]) + M) % M;
                    long long first_pow = pow[first_len];
                    curr_hash = (mod_mul(curr_hash, first_pow) + first_hash) % M;
                    curr_pow = mod_mul(curr_pow, first_pow);
                    rem -= first_len;
                }

                if (rem > 0){
                    int full_t = rem / L_dir, last_len = rem % L_dir;

                    pair<long long, long long> mid = pow_repeat(full_t);
                    curr_hash = (mod_mul(curr_hash, mid.second) + mid.first) % M;
                    curr_pow = mod_mul(curr_pow, mid.second);

                    if (last_len > 0){
                        curr_hash = (mod_mul(curr_hash, pow[last_len]) + p_hash[last_len]) % M;
                        curr_pow = mod_mul(curr_pow, pow[last_len]);
                    }
                }

                all_hashes.push_back(curr_hash);
            }
        }
    }
    sort(all_hashes.begin(), all_hashes.end());

    long long total = 0;
    size_t i = 0;
    while (i < all_hashes.size()){
        int cnt = 1;
        size_t j = i + 1;
        while (j < all_hashes.size() && all_hashes[i] == all_hashes[j]) cnt++, j++;
        total += (long long)cnt * cnt;
        i = j;
    }

    long long div = (8 * row_num * col_num) * (8 * row_num * col_num);
    long long gcd = __gcd(total, div);

    cout << total / gcd << "/" << div / gcd;
    return 0;
}

• Subtask 1: 100 / 160