제출 #868031

#제출 시각아이디문제언어결과실행 시간메모리
868031serifefedartarOsmosmjerka (COCI17_osmosmjerka)C++17
160 / 160
2313 ms104580 KiB
#include <bits/stdc++.h> using namespace std; #define fast ios::sync_with_stdio(0);cin.tie(0); #define s second #define f first typedef long long ll; const ll MOD = 1e9+9; const ll LOGN = 30; const ll MAXN = 2e5 + 100; const ll MULT = 1e9; vector<string> grid; ll all = 1, expected = 1, N, M, K; map<ll,ll> mp; const ll P = 31; ll hashes[LOGN][550][550], pow2[LOGN], powP[LOGN]; void solve(int dx, int dy) { for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) hashes[0][i][j] = (grid[i][j] - 'a' + 1); } for (int lg = 1; lg < LOGN; lg++) { for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) hashes[lg][i][j] = (hashes[lg - 1][i][j] * powP[lg-1] % MOD + hashes[lg - 1][((i + dx * pow2[lg-1]) % M + MULT * M) % M][((j + dy * pow2[lg-1]) % N + MULT * N) % N]) % MOD; } } for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { ll hash_val = 0; int now_i = i, now_j = j; for (int lg = 0; lg < LOGN; lg++) { if (pow2[lg] & K) { hash_val = (hash_val * powP[lg] % MOD + hashes[lg][now_i][now_j]) % MOD; now_i = ((now_i + dx * pow2[lg]) % M + MULT * M) % M; now_j = ((now_j + dy * pow2[lg]) % N + MULT * N) % N; } } mp[hash_val]++; } } } int main() { fast pow2[0] = 1; powP[0] = P; for (int i = 1; i < LOGN; i++) { pow2[i] = pow2[i-1] * 2; powP[i] = (powP[i-1] * powP[i-1]) % MOD; } cin >> M >> N >> K; grid = vector<string>(M); for (int i = 0; i < M; i++) cin >> grid[i]; all = M * N * M * N * 8 * 8; for (int dx = -1; dx <= 1; dx++) { for (int dy = -1; dy <= 1; dy++) { if (!(dx == 0 && dy == 0)) solve(dx, dy); } } for (auto u : mp) expected += u.s * u.s; expected--; ll GCD = __gcd(all, expected); all /= GCD; expected /= GCD; cout << expected << "/" << all << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...