Submission #914202

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
914202	2024-01-21T10:50:45 Z	MisterReaper	Osmosmjerka (COCI17_osmosmjerka)	C++17	140 / 160	1989 ms	57208 KB

osmosmjerka

#include <bits/stdc++.h>
using i64 = long long;

constexpr int N = 500 + 5;
constexpr int LOG = 32;

/**
 * Description: Modular arithmetic operations basic
 * Source: MisterReaper
 * KACTL:
 * Not. 
 */

constexpr int MOD = 1E9 + 9;
constexpr int BASE = 27;

int mul(int a, int b) {
    return (1LL * a * b) % MOD;
}

int add(int a, int b) {
    return (a + b) % MOD;
}

int sub(int a, int b) {
    return add(a, MOD - b);
}

int expo(int a, int b) {
    int res = 1;
    while(b) {
        if(b & 1) {
            res = mul(res, a);
        }

        a = mul(a, a);
        b >>= 1;
    }

    return res;
}

int inv(int a) {
    return expo(a, MOD - 2);
}

int divide(int a, int b) {
    return mul(a, inv(b));
}

int pol[LOG];
char grid[N][N];
int par[LOG][N][N];

#define ONLINE_JUDGE
void solve() {
    int n, m, k;
    std::cin >> n >> m >> k;

    i64 INF = (1LL << 32) * n * m;

    pol[0] = BASE;
    for(int lg = 1; lg < LOG; lg++) {
        pol[lg] = mul(pol[lg - 1], pol[lg - 1]);
    }

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            std::cin >> grid[i][j];
            par[0][i][j] = (grid[i][j] - 'a' + 1);
        }
    }

    auto ok = [&](int x, int y) -> bool {
        return 0 <= x && x < n && 0 <= y && y < m;
    };

    std::map<int, int> cnt;
    for(int dx : {-1, 0, 1}) {
        for(int dy : {-1, 0, 1}) {
            if(dx == 0 && dy == 0) {
                continue;
            }

            for(int lg = 1; lg < LOG; lg++) {
                for(int i = 0; i < n; i++) {
                    for(int j = 0; j < m; j++) {
                        int ni = (i + dx * (1LL << (lg - 1)) + INF) % n;
                        int nj = (j + dy * (1LL << (lg - 1)) + INF) % m;

                        assert(ok(ni, nj));
                        par[lg][i][j] = mul(par[lg - 1][i][j], pol[(lg - 1)]);
                        par[lg][i][j] = add(par[lg][i][j], par[lg - 1][ni][nj]);
                    }
                }
            }

            for(int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                    int ci = i, cj = j, h = 0;
                    for(int lg = LOG - 1; lg >= 0; lg--) {
                        if(k & (1 << lg)) {
                            h = mul(h, pol[lg]);
                            h = add(h, par[lg][ci][cj]);
                            ci = (ci + dx * (1LL << lg) + INF) % n;
                            cj = (cj + dy * (1LL << lg) + INF) % m;
                            assert(ok(ci, cj));
                        }
                    }

                    cnt[h]++;
                }
            }
        }
    }

    i64 q = (n * m * 8);
    q *= q;

    i64 p = 0;
    for(auto [h, c] : cnt) {
        p += (1LL * c * c);
    }

    std::cerr << p << " " << q << "\n";
    i64 g = std::gcd(p, q);
    p /= g;
    q /= g;

    std::cout << p << "/" << q;
    
    return;
}

signed main() {
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL); std::cout.tie(NULL);

    int t = 1; //std::cin >> t;
    for(int i = 1; i <= t; i++) {
        solve();
    }

    return 0;
}

Subtask #1

140.0 / 160.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	31064 KB	Output is correct
2	Correct	5 ms	31068 KB	Output is correct
3	Correct	5 ms	31256 KB	Output is correct
4	Correct	6 ms	31324 KB	Output is correct
5	Correct	12 ms	31324 KB	Output is correct
6	Correct	50 ms	33620 KB	Output is correct
7	Incorrect	581 ms	46144 KB	Output isn't correct
8	Correct	1989 ms	57208 KB	Output is correct