Submission #498292

#	Time	Username	Problem	Language	Result	Execution time	Memory
498292		sberens	Osmosmjerka (COCI17_osmosmjerka)	C++17	160 / 160	1421 ms	145804 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) {
        if (M > 1.5e9) {
            modint r = 1;
            modint mn = n;
            for (; k > 0; k >>= 1, mn *= mn)
                if (k&1) r *= mn;
            return r.v;
        } else {
            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
    [[nodiscard]] modint pow(const ll k) const {
        return k < 0 ? _pow(v, M-1-(-k%(M-1))) : _pow(v, k);
    }
    [[nodiscard]] 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<M>; // ????
using vmi = vector<mi>;

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

struct shash_t {
    int sz{};
    mi h1, h2;
    static inline hmap<int, pair<mi, mi>> cache;

    shash_t& operator+=(const shash_t b) {
        auto [szb, h1b, h2b] = b;
        pair<mi, mi> ps;
        if (cache.find(szb) == cache.end()) {
            ps = {mi(b1).pow(szb), mi(b2).pow(szb)};
            cache[szb] = ps;
        } else {
            ps = cache[szb];
        }
        h1 = (h1 * ps.first) + h1b;
        h2 = (h2 * ps.second) + h2b;
        sz += szb;
        return *this;
    }

    friend shash_t operator+(const shash_t a, const shash_t b) {
        return shash_t(a) += b;
    }

    shash_t& operator*=(int t) {
//        shash_t res{};
//        assert(res.sz == 0);
//        F0R(_, t) {
//            if (_ == 1) assert(res == *this);
//            res+= *this;
//        }
//        return *this = res;
        if (t == 0) return *this = {};
        shash_t og = *this;
        R0F(i, log2(t)) {
            *this += *this;
            if (t & (1 << i)) *this += og;
        }
        return *this;
    }

    friend shash_t operator*(const shash_t a, const int t) {
        return shash_t(a) *= t;
    }

    bool operator<(const shash_t &rhs) const {
        if (sz < rhs.sz)
            return true;
        if (rhs.sz < sz)
            return false;
        if (h1 < rhs.h1)
            return true;
        if (rhs.h1 < h1)
            return false;
        return h2 < rhs.h2;
    }

    bool operator>(const shash_t &rhs) const {
        return rhs < *this;
    }

    bool operator<=(const shash_t &rhs) const {
        return !(rhs < *this);
    }

    bool operator>=(const shash_t &rhs) const {
        return !(*this < rhs);
    }

    bool operator==(const shash_t &rhs) const {
        return sz == rhs.sz &&
               h1 == rhs.h1 &&
               h2 == rhs.h2;
    }

    bool operator!=(const shash_t &rhs) const {
        return !(rhs == *this);
    }

};

struct hash_querier {
    vmi hsh1, hsh2;
    inline static vmi bp1{}, bp2{};

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

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


int m, n, k;


shash_t pad(const hash_querier & hq, int olen, int offset) {
    return hq.query(offset, offset + olen - 1) * (k / olen) + hq.query(offset, offset + (k % olen) - 1);
}

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);
    cin >> m >> n >> k;
    smin(k, lcm(m, n));
    vector<string> g(m);
    F0R(i, m) cin >> g[i];
    map<shash_t, ll> cnt;
    map<string , ll> cnt1;
    map<shash_t, string> mp;
    using seen_t = array<int, 4>; // vis, offset, tot len, hashqi
    vv<vector<seen_t>> seen(m, vv<seen_t>(n, vector<seen_t>(8)));
    vector<hash_querier> hqs;
    vector<string> sss;
    F0R(d, 8) {
        auto[dr, dc] = dirs[d];
        F0R(r, m) {
            F0R(c, n) {
                auto &[vis, offset, len, hqi] = seen[r][c][d];
                if (!vis) {
                    if (abs(dr) + abs(dc) == 2) len = lcm(m, n);
                    else if (abs(dr) == 1) len = m;
                    else len = n;
                    hqi = hqs.size();
                    string s;
                    int cr = r, cc = c;
                    offset = 0;
                    F0R(off, len) {
                        s += g[cr][cc];
                        if (!seen[cr][cc][d][0])
                            seen[cr][cc][d] = {1, off, len, hqi};
                        cr = (cr + dr + m) % m;
                        cc = (cc + dc + n) % n;
                    }
                    hqs.eb(s + s);
//                    sss.eb(s + s);
                    vis = 1;
                }
//                string s1;
//                int cr = r, cc = c;
//                F0R(off, k) {
////                    F0R(off, len) {
//                    s1 += g[cr][cc];
//                    cr = (cr + dr + m) % m;
//                    cc = (cc + dc + n) % n;
//                }
                auto key = pad(hqs[hqi], len, offset);
//                hash_querier temp(s1);
//                const shash_t &tempans = temp.query(0, k - 1);
//                auto h = hqs[hqi].query(offset, offset + len - 1);
//                shash_t rh{};
//                F0R(_, k / len) {
//                    rh += h;
//                    assert(rh == temp.query(0, rh.sz-1));
//                }
//                assert(key == tempans);
//                if (cnt1.count(s1) == 1 && cnt.count(key) == 0) {
//                    int q;
//                    auto x = hqs[0];
//                    auto y = hqs[hqi];
//                    q = 0;
//                }
                cnt[key]++;
//                cnt1[s1]++;
//                mp[key] = s1;
            }
        }
    }
    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';
    // high level:
    // 1) for each cell & direction get a "representative" string
            // for each cell + direction store if we've visited that state,
            // if we have we also need the offset + tot length of string
            // we also need a reference to the relevant string/hash querier
                // I can just make an array of hash queriers and store the index to be used
    // 2) "extend" the string to length k
    // 3) insert into map and continue as before
}

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:222:9: note: in expansion of macro 'F0R'
  222 |         F0R(i, s.size()) {
      |         ^~~
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:232:9: note: in expansion of macro 'FOR'
  232 |         FOR(i, bp1.size()-1, s.size()) {
      |         ^~~

• Subtask 1: 160 / 160