Submission #497478

#	Time	Username	Problem	Language	Result	Execution time	Memory
497478		sberens	Osmosmjerka (COCI17_osmosmjerka)	C++17	80 / 160	4034 ms	4544 KiB

osmosmjerka

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
template<typename K> using hset = gp_hash_table<K, null_type>;
template<typename K, typename V> using hmap = gp_hash_table<K, V>;


using namespace std;

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define smax(x, y) (x = max(x, y))
#define smin(x, y) (x = min(x, y))

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i,0,a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i,0,a)


using ll = long long;
using ld = long double;

template<typename T>
using vv = vector<vector<T>>;

using vi = vector<int>;
using ii = array<int, 2>;
using vii = vector<ii>;
using vvi = vv<int>;

using vll = vector<ll>;
using l2 = array<ll, 2>;
using vl2 = vector<l2>;
using vvll = vv<ll>;

template<typename T>
using minq = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using maxq = priority_queue<T>;

template<typename T>
using oset = tree<T, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;

const ll M = 1000000007;
const ll infll = M * M;

template<ll M>
struct modint {

    static ll _reduce(ll n) {
        constexpr static ll b = -1ull/M;
        ll r = n-(ll)(__uint128_t(b)*n>>64)*M; return r >= M ? r-M : r;
    }

    static ll _pow(ll n, ll k) {
        ll r = 1;
        for (; k > 0; k >>= 1, n = _reduce(n*n))
            if (k&1) r = _reduce(r*n);
        return r;
    }

    ll v; modint(ll n = 0) : v(_reduce(n)) { v += (M&(0-(v<0))); }

    friend string to_string(const modint n) { return to_string(n.v); }
    friend istream& operator>>(istream& i, modint& n) { return i >> n.v; }
    friend ostream& operator<<(ostream& o, const modint n) { return o << n.v; }
    template<typename T> explicit operator T() { return T(v); }

    friend bool operator==(const modint n, const modint m) { return n.v == m.v; }
    friend bool operator!=(const modint n, const modint m) { return n.v != m.v; }
    friend bool operator<(const modint n, const modint m) { return n.v < m.v; }
    friend bool operator<=(const modint n, const modint m) { return n.v <= m.v; }
    friend bool operator>(const modint n, const modint m) { return n.v > m.v; }
    friend bool operator>=(const modint n, const modint m) { return n.v >= m.v; }

    modint& operator+=(const modint n) { v += n.v; v -= (M&(0-(v>=M))); return *this; }
    modint& operator-=(const modint n) { v -= n.v; v += (M&(0-(v<0))); return *this; }
    modint& operator*=(const modint n) { v = _reduce(v*n.v); return *this; }
    modint& operator/=(const modint n) { v = _reduce(v*_pow(n.v, M-2)); return *this; }
    friend modint operator+(const modint n, const modint m) { return modint(n) += m; }
    friend modint operator-(const modint n, const modint m) { return modint(n) -= m; }
    friend modint operator*(const modint n, const modint m) { return modint(n) *= m; }
    friend modint operator/(const modint n, const modint m) { return modint(n) /= m; }
    modint& operator++() { return *this += 1; }
    modint& operator--() { return *this -= 1; }
    modint operator++(int) { modint t = *this; return *this += 1, t; }
    modint operator--(int) { modint t = *this; return *this -= 1, t; }
    modint operator+() { return *this; }
    modint operator-() { return modint(0) -= *this; }

    // O(logk) modular exponentiation
    modint pow(const ll k) const {
        return k < 0 ? _pow(v, M-1-(-k%(M-1))) : _pow(v, k);
    }
    modint inv() const { return _pow(v, M-2); }
};

mt19937 randint(chrono::steady_clock::now().time_since_epoch().count());

// returns a random integer over [a, b] inclusive
inline int uniform_randint(const int a, const int b) {
    return uniform_int_distribution<int>(a, b)(randint);
}
constexpr ll P = (1ull << 61) - 1;

template<>
modint<P> &modint<P>::operator*=(const modint<P> n) {
    uint64_t l1 = (uint32_t) v, h1 = v >> 32, l2 = (uint32_t) n.v, h2 = n.v >> 32;
    uint64_t l = l1 * l2, m = l1 * h2 + l2 * h1, h = h1 * h2;
    uint64_t ret = (l & P) + (l >> 61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
    ret = (ret & P) + (ret >> 61);
    ret = (ret & P) + (ret >> 61);
    v = ret - 1;
    return *this;
}

using mi = modint<P>;
using vmi = vector<mi>;

int b1 = uniform_randint(5000, 10000);
int b2 = uniform_randint(10001, 20000);

using shash_t = ll;

struct hash_querier {
    vmi hsh1, hsh2, bp1, bp2;

    explicit hash_querier(const string &s) :
            hsh1(s.size() + 1), hsh2(s.size() + 1),
            bp1(s.size() + 1, 1), bp2(s.size() + 1, 1) {
        F0R(i, s.size()) {
            hsh1[i + 1] = s[i] - 'a' + hsh1[i] * b1;
//            hsh2[i + 1] = s[i] - 'a' + hsh2[i] * b2;
            bp1[i + 1] = bp1[i] * b1;
//            bp2[i + 1] = bp2[i] * b2;
        }
    }

    // hash of substring [l, r] inclusive
    shash_t query(int l, int r) {
//        return {hsh1[r + 1] - hsh1[l] * bp1[r - l + 1],
//                hsh2[r + 1] - hsh2[l] * bp2[r - l + 1]};
            return (hsh1[r + 1] - hsh1[l] * bp1[r - l + 1]).v;
    }
};

vii dirs{{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int m, n, k;
    cin >> m >> n >> k;
    vector<string> g(m);
    F0R(i, m) cin >> g[i];
    map<shash_t, ll> cnt;
    for (auto [dr, dc] : dirs) {
        F0R(r, m) {
            F0R(c, n) {
                string s;
                int cr = r, cc = c;
                F0R(_, min(gcd(m, n), k)) {
                    s += g[cr][cc];
                    cr = (cr + dr + m) % m;
                    cc = (cc + dc + n) % n;
                }
                hash_querier rh(s);
                cnt[rh.query(0, s.size()-1)]++;
            }
        }
    }
    ll q = pow(m * n * 8, 2);
    ll p = 0;
    for (auto & [_, kcnt] : cnt) p += kcnt * kcnt;
    ll gc = gcd(p, q);
    p /= gc;
    q /= gc;
    cout << p << '/' << q << '\n';
}

Compilation message (stderr)

osmosmjerka.cpp: In constructor 'hash_querier::hash_querier(const string&)':
osmosmjerka.cpp:18:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 | #define FOR(i, a, b) for (int i = (a); i < (b); ++i)
      |                                          ^
osmosmjerka.cpp:19:19: note: in expansion of macro 'FOR'
   19 | #define F0R(i, a) FOR(i,0,a)
      |                   ^~~
osmosmjerka.cpp:135:9: note: in expansion of macro 'F0R'
  135 |         F0R(i, s.size()) {
      |         ^~~

• Subtask 1: 80 / 160