# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
868031 | serifefedartar | Osmosmjerka (COCI17_osmosmjerka) | C++17 | 2313 ms | 104580 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |