Submission #1088100

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088100		SansPapyrus683	Osmosmjerka (COCI17_osmosmjerka)	C++17	160 / 160	1843 ms	65136 KiB

osmosmjerka

#include <bits/stdc++.h>
#if __has_include("debugging.hpp")
#include "debugging.hpp"
#endif
using namespace std;
using ll = long long;

ll M = 1e9 + 9;
constexpr ll B = 9973;

class HashedString {
   private:
    vector<ll> p_hash;

   public:
    static vector<ll> pow;

    HashedString(const string& s) : p_hash(s.size() + 1) {
        while (pow.size() <= s.size()) {
            pow.push_back((pow.back() * B) % M);
        }
        p_hash[0] = 0;
        for (int i = 0; i < s.size(); i++) {
            p_hash[i + 1] = ((p_hash[i] * B) % M + s[i]) % M;
        }
    }

    ll get_hash(int start, int end) {
        ll raw_val = (p_hash[end + 1] - (p_hash[start] * pow[end - start + 1]));
        return (raw_val % M + M) % M;
    }
};
vector<ll> HashedString::pow = {1};

ll binpow(ll x, ll n, ll m) {
    assert(n >= 0);
    x %= m;
    ll res = 1;
    while (n > 0) {
        if (n % 2 == 1) {
            res = res * x % m;
        }
        x = x * x % m;
        n /= 2;
    }
    return res;
}

ll mod_inv(ll x, ll m) { return binpow(x, m - 2, m); }

constexpr int DR[] = {0, 0, 1, -1, 1, -1, -1, 1};
constexpr int DC[] = {1, -1, 0, 0, 1, -1, 1, -1};

int main() {
    int row_num, col_num;
    int len;
    cin >> row_num >> col_num >> len;
    vector<string> grid(row_num);
    for (string& r : grid) {
        cin >> r;
        assert(r.size() == col_num);
    }

    vector<ll> hashes1;
    for (int dir = 0; dir < 8; dir++) {
        vector<vector<bool>> visited(row_num, vector<bool>(col_num));
        for (int r = 0; r < row_num; r++) {
            for (int c = 0; c < col_num; c++) {
                if (visited[r][c]) {
                    continue;
                }

                string loop;
                int at_r = r, at_c = c;
                while (!visited[at_r][at_c]) {
                    visited[at_r][at_c] = true;
                    loop.push_back(grid[at_r][at_c]);
                    at_r = (at_r + DR[dir] + row_num) % row_num;
                    at_c = (at_c + DC[dir] + col_num) % col_num;
                }

                ll loop_pow = binpow(B, loop.size(), M);
                ll div_by = mod_inv(loop_pow - 1, M);
                HashedString hashed(loop);
                ll whole = hashed.get_hash(0, loop.size() - 1);
                for (int i = 0; i < loop.size(); i++) {
                    int head_amt = min(len, (int)loop.size() - i);
                    int mid_loops = (len - head_amt) / loop.size();
                    int tail_amt = (len - head_amt) % loop.size();

                    ll head_hash = hashed.get_hash(i, i + head_amt - 1);
                    head_hash = head_hash * binpow(B, len - head_amt, M) % M;

                    ll mid_hash =
                        whole * (binpow(loop_pow, mid_loops, M) - 1) % M * div_by % M;
                    mid_hash = mid_hash * binpow(B, tail_amt, M) % M;

                    ll tail_hash = hashed.get_hash(0, tail_amt - 1);

                    ll hsh = (head_hash + mid_hash + tail_hash) % M;
                    hashes1.push_back(hsh);
                }
            }
        }
    }

    M = 1e9 + 7;
    HashedString::pow = {1};
    vector<ll> hashes2;
    for (int dir = 0; dir < 8; dir++) {
        vector<vector<bool>> visited(row_num, vector<bool>(col_num));
        for (int r = 0; r < row_num; r++) {
            for (int c = 0; c < col_num; c++) {
                if (visited[r][c]) {
                    continue;
                }

                string loop;
                int at_r = r, at_c = c;
                while (!visited[at_r][at_c]) {
                    visited[at_r][at_c] = true;
                    loop.push_back(grid[at_r][at_c]);
                    at_r = (at_r + DR[dir] + row_num) % row_num;
                    at_c = (at_c + DC[dir] + col_num) % col_num;
                }

                ll loop_pow = binpow(B, loop.size(), M);
                ll div_by = mod_inv(loop_pow - 1, M);
                HashedString hashed(loop);
                ll whole = hashed.get_hash(0, loop.size() - 1);
                for (int i = 0; i < loop.size(); i++) {
                    int head_amt = min(len, (int)loop.size() - i);
                    int mid_loops = (len - head_amt) / loop.size();
                    int tail_amt = (len - head_amt) % loop.size();

                    ll head_hash = hashed.get_hash(i, i + head_amt - 1);
                    head_hash = head_hash * binpow(B, len - head_amt, M) % M;

                    ll mid_hash =
                        whole * (binpow(loop_pow, mid_loops, M) - 1) % M * div_by % M;
                    mid_hash = mid_hash * binpow(B, tail_amt, M) % M;

                    ll tail_hash = hashed.get_hash(0, tail_amt - 1);

                    ll hsh = (head_hash + mid_hash + tail_hash) % M;
                    hashes2.push_back(hsh);
                }
            }
        }
    }
    assert(hashes1.size() == hashes2.size());

    map<pair<ll, ll>, int> hash_occ;
    for (int i = 0; i < hashes1.size(); i++) {
        hash_occ[{hashes1[i], hashes2[i]}]++;
    }

    ll total_strings = (ll)row_num * row_num * col_num * col_num * 64;
    ll same_pairs = 0;
    for (const auto& [_, amt] : hash_occ) {
        same_pairs += (ll)amt * amt;
    }
    ll div_by = gcd(total_strings, same_pairs);
    printf("%lli/%lli\n", same_pairs / div_by, total_strings / div_by);
}

Compilation message (stderr)

osmosmjerka.cpp: In constructor 'HashedString::HashedString(const string&)':
osmosmjerka.cpp:23:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         for (int i = 0; i < s.size(); i++) {
      |                         ~~^~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from osmosmjerka.cpp:1:
osmosmjerka.cpp: In function 'int main()':
osmosmjerka.cpp:61:25: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   61 |         assert(r.size() == col_num);
      |                ~~~~~~~~~^~~~~~~~~~
osmosmjerka.cpp:86:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |                 for (int i = 0; i < loop.size(); i++) {
      |                                 ~~^~~~~~~~~~~~~
osmosmjerka.cpp:131:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |                 for (int i = 0; i < loop.size(); i++) {
      |                                 ~~^~~~~~~~~~~~~
osmosmjerka.cpp:154:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |     for (int i = 0; i < hashes1.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~

• Subtask 1: 160 / 160