Submission #914205

#TimeUsernameProblemLanguageResultExecution timeMemory
914205MisterReaperOsmosmjerka (COCI17_osmosmjerka)C++17
160 / 160
3454 ms97276 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...