Submission #713288

#TimeUsernameProblemLanguageResultExecution timeMemory
713288JohannOsmosmjerka (COCI17_osmosmjerka)C++14
140 / 160
2483 ms262144 KiB
#include "bits/stdc++.h" using namespace std; typedef long long ll; typedef pair<ll, ll> pii; typedef vector<ll> vi; typedef vector<vi> vvi; typedef vector<vvi> vvvi; typedef vector<vvvi> vvvvi; typedef vector<pii> vpii; #define sz(x) (ll)(x).size() #define all(x) (x).begin(), (x).end() const ll MOD = ((1LL << 61) - 1); const ll P = 9973; const ll P1 = 98999; const ll P2 = 22573; const ll P3 = 1367; const ll P4 = 41809; ll mod_mul(ll a, ll b) { __int128 res = (__int128)a * b; return res % MOD; } int N, M, K; vpii dirs = {{1, 1}, {1, 0}, {1, -1}, {0, 1}, {0, -1}, {-1, 1}, {-1, 0}, {-1, -1}}; pii move(pii &pos, pii &dir, ll amount) { pii ans; ans.first = (pos.first + dir.first * amount) % N; ans.second = (pos.second + dir.second * amount) % M; ans.first = (ans.first + N) % N; ans.second = (ans.second + M) % M; assert(0 <= ans.first && 0 <= ans.second && ans.first < N && ans.second < M); return ans; } vvi grid; vvvvi dp; vi pot; void initDP() { int logheight = ceil(log2(K) + 1); dp.assign(N, vvvi(M, vvi(sz(dirs), vi(logheight, 0)))); for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j) for (int d = 0; d < sz(dirs); ++d) dp[i][j][d][0] = grid[i][j]; pot.assign(logheight, P); // pot[i] = P^(2^i) for (int l = 1; l < logheight; ++l) { pot[l] = mod_mul(pot[l - 1], pot[l - 1]); for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j) { pii coords = {i, j}; ll in, jn; for (int d = 0; d < sz(dirs); ++d) { tie(in, jn) = move(coords, dirs[d], 1LL << (l - 1)); dp[i][j][d][l] = (dp[i][j][d][l - 1] + mod_mul(pot[l - 1], dp[in][jn][d][l - 1])) % MOD; assert(dp[i][j][d][l] >= 0); } } } } ll lift(pii pos, int d, int k) { int i, j; tie(i, j) = pos; ll ans = 0; ll pp = 1; for (int l = 0; l < sz(dp[i][j][d]); ++l) { if (k & (1 << l)) { ans = (ans + mod_mul(pp, dp[i][j][d][l])) % MOD; pp = mod_mul(pp, pot[l]); tie(i, j) = move(pos, dirs[d], 1LL << l); } assert(ans >= 0); } return ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> N >> M >> K; grid.assign(N, vi(M, 0)); for (int i = 0; i < N; ++i) { string tmp; cin >> tmp; for (int j = 0; j < M; ++j) grid[i][j] = tmp[j]; } initDP(); vi paths; for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j) for (int d = 0; d < sz(dirs); ++d) paths.push_back(lift({i, j}, d, K)); sort(all(paths)); ll num = 0; ll denom = sz(paths) * sz(paths); ll last = paths.front(); ll cnt = 1; for (int i = 1; i < sz(paths); ++i) { if (paths[i] == last) ++cnt; else { num += cnt * cnt; cnt = 1; last = paths[i]; } } num += cnt * cnt; ll g = __gcd(num, denom); cout << num / g << "/" << denom / g << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...