Submission #296847

#	Time	Username	Problem	Language	Result	Execution time	Memory
296847		HynDuf	Osmosmjerka (COCI17_osmosmjerka)	C++14	120 / 160	385 ms	262144 KiB

osmosmjerka

#include <bits/stdc++.h>

#define task "O"
#define all(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define Rep(i, r, l) for (int i = (r); i >= (l); --i)
#define DB(X) { cerr << #X << " = " << (X) << '\n'; }
#define DB1(A, _) { cerr << #A << "[" << _ << "] = " << (A[_]) << '\n'; }
#define DB2(A, _, __) { cerr << #A << "[" << _ << "][" << __ << "] = " << (A[_][__]) << '\n'; }
#define DB3(A, _, __, ___) { cerr << #A << "[" << _ << "][" << __ << "][" << ___ << "] = " << (A[_][__][___]) << '\n'; }
#define PR(A, l, r) { cerr << '\n'; rep(_, l, r) DB1(A, _); cerr << '\n';}
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back
#define pf push_front
#define F first
#define S second
#define by(x) [](const auto& a, const auto& b) { return a.x < b.x; } // sort(arr, arr + N, by(a));
#define next ___next
#define prev ___prev
#define y1 ___y1
#define left ___left
#define right ___right
#define y0 ___y0
#define div ___div
#define j0 ___j0
#define jn ___jn

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using namespace std;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vl;
const int N = 500, mod1 = 1e9 + 7, mod2 = 1e9 + 123, Base1 = 257, Base2 = 317;
int n, m, K, dx[] = {1, 1, 1, 0, 0, -1, -1, -1}, dy[] = {-1, 0, 1, -1, 1, -1, 0, 1}, pw1[30], pw2[30];
ii hs[8][N][N][18];
string s[N];
vii allHash;
int main()
{
#ifdef HynDuf
    freopen(task".in", "r", stdin);
    //freopen(task".out", "w", stdout);
#else
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
#endif
    cin >> n >> m >> K;
    K = min(n * m, K);
    rep(i, 0, n - 1) cin >> s[i];
    pw1[0] = Base1;
    pw2[0] = Base2;
    rep(i, 1, 17) pw1[i] = pw1[i - 1] * 1LL * pw1[i - 1] % mod1, pw2[i] = pw2[i - 1] * 1LL * pw2[i - 1] % mod2;
    rep(dir, 0, 7) rep(i, 0, n - 1) rep(j, 0, m - 1) hs[dir][i][j][0] = {s[i][j], s[i][j]};
    rep(mu2, 1, 17) rep(dir, 0, 7) rep(i, 0, n - 1) rep(j, 0, m - 1)
    {
        int nx = i + dx[dir] * ((1 << mu2) - 1), ny = j + dy[dir] * ((1 << mu2) - 1);
        nx = (nx % n + n) % n;
        ny = (ny % m + m) % m;
        int nh1 = (hs[dir][i][j][mu2 - 1].F * 1LL * pw1[mu2 - 1] % mod1 + hs[dir][nx][ny][mu2 - 1].F) % mod1;
        int nh2 = (hs[dir][i][j][mu2 - 1].S * 1LL * pw2[mu2 - 1] % mod2 + hs[dir][nx][ny][mu2 - 1].S) % mod2;
        hs[dir][i][j][mu2] = {nh1, nh2};
    }
    rep(dir, 0, 7) rep(i, 0, n - 1) rep(j, 0, m - 1)
    {
        int h1 = 0, h2 = 0, x = i, y = j, nx = 0, ny = 0;
        rep(mu2, 0, 17) if (K >> mu2 & 1)
        {
            h1 = (h1 * 1LL * pw1[mu2] % mod1 + hs[dir][x][y][mu2].F) % mod1;
            h2 = (h2 * 1LL * pw2[mu2] % mod2 + hs[dir][x][y][mu2].S) % mod2;
            nx = x + dx[dir] * (1 << mu2), ny = y + dy[dir] * (1 << mu2);
            x = (nx % n + n) % n;
            y = (ny % m + m) % m;
        }
        allHash.eb(h1, h2);
    }
    sort(all(allHash));
    //for (ii v : allHash) cout << "(" << v.F << ", " << v.S << ")\n";
    ll num = 0, tot = (n * 1LL * m * 8 * n * m * 8);
    for (int l = 0, r = 0; l < SZ(allHash); l = r)
    {
        while (r < SZ(allHash) && allHash[r] == allHash[l]) r++;
        num += (r - l) * 1LL * (r - l);
    }
    ll g = __gcd(num, tot);
    cout << (num / g) << '/' << (tot / g);
    return 0;
}

• Subtask 1: 120 / 160