Submission #1247889

#TimeUsernameProblemLanguageResultExecution timeMemory
1247889Abdo_EidOsmosmjerka (COCI17_osmosmjerka)C++20
60 / 160
317 ms19660 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define all(a) a.begin(), a.end() #define allr(a) a.rbegin(), a.rend() const int N = 5e2 + 1; int vis[N][N][8], n, m, k; char grid[N][N]; const int dr[] = {1, 1, 1, 0, 0, -1, -1, -1}; const int dc[] = {1, -1, 0, 1, -1, 1, -1, 0}; string get_path(int r, int c, int d) { string res = ""; while (!vis[r][c][d]) { res += grid[r][c]; vis[r][c][d] = true; r = (r + dr[d] + n) % n; c = (c + dc[d] + m) % m; } return res; } struct Hash { const ll M = 1e9 + 9; const ll P = 9973; int n; vector<ll> pw, hsh; ll mul(ll a, ll b) { return (a * b) % M; } ll add(ll a, ll b) { return (a + b) % M; } ll sub(ll a, ll b) { return (a - b + M) % M; } Hash(string s) { n = s.size(); pw.push_back(1); hsh.push_back(0); for (int i = 1; i <= n; i++) { pw.push_back(mul(pw.back(), P)); hsh.push_back(add(s[i - 1], mul(hsh.back(), P))); } } ll get(int l, int r) { return sub(hsh[r + 1], mul(hsh[l], pw[r - l + 1])); } ll merge(ll lval, ll rval, int rsize) { return add(rval, mul(lval, pw[rsize])); } ll getByLen(int l, int len) { if (len == 0) return 0; int end = (l + len - 1) % n; if (l <= end) return get(l, end); return merge(get(l, n - 1), get(0, end), end + 1); } ll duplicate(ll val, int k) { if (k == 0) return 0; ll ret = duplicate(val, k >> 1); ret = merge(ret, ret, k >> 1); if (k % 2) ret = merge(ret, val, n); return ret; } ll getByStart(int i) { return getByLen(i, n); } }; void solve() { cin >> n >> m >> k; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> grid[i][j]; map<ll, ll> mp; for (int r = 0; r < n; r++) for (int c = 0; c < m; c++) for (int d = 0; d < 8; d++) { if (vis[r][c][d]) continue; string s = get_path(r, c, d); Hash hsh(s); int len = s.size(); int cnt = k / len, remain = k % len; for (int i = 0; i < len; i++) { ll cur = hsh.getByStart(i); cur = hsh.duplicate(cur, cnt); ll other = hsh.getByLen(i, remain); cur = hsh.merge(cur, other, remain); ++mp[cur]; } } ll den = 1ll * n * m * 8; den *= den; ll num = 0; for (auto& [k, v] : mp) { num += v * v; } ll GCD = gcd(num, den); num /= GCD; den /= GCD; cout << num << "/" << den << endl; } int main() { ios_base::sync_with_stdio(NULL); cin.tie(NULL), cout.tie(NULL); int t = 1; // cin >> t; while (t--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...