Submission #1234974

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234974		newsboy	Osmosmjerka (COCI17_osmosmjerka)	C++20	160 / 160	3687 ms	102388 KiB

osmosmjerka

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <set>
#include <map>
#include <numeric>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <tuple>
#include <cassert>
#include <array>
#include <list>
#include <random>
#include <initializer_list>
#include <chrono>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using db = double;
using ld = long double;
const i64 inf = i64(1E18);

template<class T>
constexpr T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b & 1) {
            res *= a;
        }
    }
    return res;
}

i64 mul(i64 a, i64 b, i64 p) {
    i64 res = a * b - i64(1.L * a * b / p) * p;
    res %= p;
    if (res < 0) {
        res += p;
    }
    return res;
}
template<i64 P>
struct MLong {
    i64 x;
    constexpr MLong() : x{} {}
    constexpr MLong(i64 x) : x{ norm(x % P) } {}
    constexpr i64 norm(i64 x) const {
        if (x < 0) {
            x += P;
        }
        if (x >= P) {
            x -= P;
        }
        return x;
    }
    constexpr MLong inv() const {
        assert(x != 0);
        return power(*this, P - 2);
    }
    constexpr i64 val() const {
        return x;
    }
    constexpr MLong& operator*=(MLong rhs)& {
        x = mul(x, rhs.x, P);
        return *this;
    }
    constexpr MLong& operator+=(MLong rhs)& {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MLong& operator-=(MLong rhs)& {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MLong& operator/=(MLong rhs)& {
        return *this *= rhs.inv();
    }
    friend constexpr MLong operator*(MLong lhs, MLong rhs) {
        MLong res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MLong operator+(MLong lhs, MLong rhs) {
        MLong res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MLong operator-(MLong lhs, MLong rhs) {
        MLong res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MLong operator/(MLong lhs, MLong rhs) {
        MLong res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr istream& operator>>(istream& is, MLong& a) {
        i64 v;
        is >> v;
        a = MLong(v);
        return is;
    }
    friend constexpr ostream& operator<<(ostream& os, const MLong& a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MLong lhs, MLong rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MLong lhs, MLong rhs) {
        return lhs.val() != rhs.val();
    }
};

constexpr i64 P = i64(1E18) + 9;
using Z = MLong<P>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const Z B = rng() % (P - 100) + 50;

i64 gcd(i64 a, i64 b) {
    return (b ? gcd(b, a % b) : a);
}

i64 n, m, K;
vector<string> s(501);
vector<vector<vector<Z>>> h(501, vector<vector<Z>> (501, vector<Z> (31)));
vector<Z> pw(31);
map<i64, i64> f;

void work(i64 di, i64 dj) {
    for (i64 i = 0; i < n; ++i) {
        for (i64 j = 0; j < m; ++j) {
            h[i][j][0] = s[i][j];
        }
    }
    pw[0] = B;
    for (i64 k = 1; k < 31; ++k) {
        for (i64 i = 0; i < n; ++i) {
            for (i64 j = 0; j < m; ++j) {
                h[i][j][k] = h[i][j][k - 1] * pw[k - 1] + h[(i + di * (1 << (k - 1)) % n + n) % n][(j + dj * (1 << (k - 1)) % m + m) % m][k - 1];
            }
        }
        pw[k] = pw[k - 1] * pw[k - 1];
    }
    for (i64 i = 0; i < n; ++i) {
        for (i64 j = 0; j < m; ++j) {
            i64 l = K;
            i64 ci = i, cj = j;
            Z H;
            for (i64 k = 30; k >= 0; --k) {
                if ((1 << k) <= l) {
                    l -= (1 << k);
                    H = H * pw[k] + h[ci][cj][k];
                    ci = ((ci + di * (1 << k)) % n + n) % n;
                    cj = ((cj + dj * (1 << k)) % m + m) % m;
                }
            }
            f[H.val()]++;
        }
    }
}

void solve() {
    cin >> n >> m >> K;
    for (i64 i = 0; i < n; ++i) {
        cin >> s[i];
    }
    for (i64 di = -1; di <= 1; ++di) {
        for (i64 dj = -1; dj <= 1; ++dj) {
            if (di == 0 && dj == 0) {
                continue;
            }
            work(di, dj);
        }
    }
    i64 a = 0;
    i64 b = (8 * n * m) * (8 * n * m);
    for (auto _ : f) {
        a += _.second * _.second;
    }
    i64 g = gcd(a, b);
    a /= g;
    b /= g;
    cout << a << "/" << b << '\n';
} 

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t = 1;
    /*cin >> t;*/
    while (t--) {
        solve();
    }
}

• Subtask 1: 160 / 160