# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
914200 | MisterReaper | Osmosmjerka (COCI17_osmosmjerka) | C++17 | 1993 ms | 57192 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 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 = 37;
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;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |