Submission #914205

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
914205	2024-01-21T10:57:04 Z	MisterReaper	Osmosmjerka (COCI17_osmosmjerka)	C++17	160 / 160	3454 ms	97276 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 B[] = {29, 31};

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][2];
char grid[N][N];
int par[LOG][N][N][2];

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

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

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

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

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

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

            for(int x = 0; x < 2; x++) {
                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][x] = mul(par[lg - 1][i][j][x], pol[(lg - 1)][x]);
                            par[lg][i][j][x] = add(par[lg][i][j][x], par[lg - 1][ni][nj][x]);
                        }
                    }
                }
            }

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

                    cnt[{h[0], h[1]}]++;
                }
            }
        }
    }

    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

160.0 / 160.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	63832 KB	Output is correct
2	Correct	9 ms	64088 KB	Output is correct
3	Correct	10 ms	64092 KB	Output is correct
4	Correct	12 ms	64124 KB	Output is correct
5	Correct	22 ms	64252 KB	Output is correct
6	Correct	87 ms	66904 KB	Output is correct
7	Correct	979 ms	83312 KB	Output is correct
8	Correct	3454 ms	97276 KB	Output is correct