#include <bits/stdc++.h>
#define task "O"
#define all(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define Rep(i, r, l) for (int i = (r); i >= (l); --i)
#define DB(X) { cerr << #X << " = " << (X) << '\n'; }
#define DB1(A, _) { cerr << #A << "[" << _ << "] = " << (A[_]) << '\n'; }
#define DB2(A, _, __) { cerr << #A << "[" << _ << "][" << __ << "] = " << (A[_][__]) << '\n'; }
#define DB3(A, _, __, ___) { cerr << #A << "[" << _ << "][" << __ << "][" << ___ << "] = " << (A[_][__][___]) << '\n'; }
#define PR(A, l, r) { cerr << '\n'; rep(_, l, r) DB1(A, _); cerr << '\n';}
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back
#define pf push_front
#define F first
#define S second
#define by(x) [](const auto& a, const auto& b) { return a.x < b.x; } // sort(arr, arr + N, by(a));
#define next ___next
#define prev ___prev
#define y1 ___y1
#define left ___left
#define right ___right
#define y0 ___y0
#define div ___div
#define j0 ___j0
#define jn ___jn
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using namespace std;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vl;
const int N = 500, mod1 = 1e9 + 7, mod2 = 1e9 + 123, Base1 = 257, Base2 = 31777;
int n, m, K, dx[] = {1, 1, 1, 0, 0, -1, -1, -1}, dy[] = {-1, 0, 1, -1, 1, -1, 0, 1}, pw1[18], pw2[18];
ii hs[8][N][N][2], fin[8][N][N];
string s[N];
vii allHash;
int main()
{
#ifdef HynDuf
freopen(task".in", "r", stdin);
//freopen(task".out", "w", stdout);
#else
ios_base::sync_with_stdio(false); cin.tie(nullptr);
#endif
cin >> n >> m >> K;
K = min(n * m, K);
rep(i, 0, n - 1) cin >> s[i];
pw1[0] = Base1;
pw2[0] = Base2;
rep(i, 1, 17) pw1[i] = pw1[i - 1] * 1LL * pw1[i - 1] % mod1, pw2[i] = pw2[i - 1] * 1LL * pw2[i - 1] % mod2;
rep(dir, 0, 7) rep(i, 0, n - 1) rep(j, 0, m - 1) hs[dir][i][j][0] = {s[i][j], s[i][j]};
int steps = 0;
rep(mu2, 0, 17)
{
if (mu2) rep(dir, 0, 7) rep(i, 0, n - 1) rep(j, 0, m - 1)
{
int nx = i + dx[dir] * (1 << (mu2 - 1)), ny = j + dy[dir] * (1 << (mu2 - 1));
nx = (nx % n + n) % n;
ny = (ny % m + m) % m;
int nh1 = (hs[dir][i][j][(mu2 & 1) ^ 1].F * 1LL * pw1[mu2 - 1] % mod1 + hs[dir][nx][ny][(mu2 & 1) ^ 1].F) % mod1;
int nh2 = (hs[dir][i][j][(mu2 & 1) ^ 1].S * 1LL * pw2[mu2 - 1] % mod2 + hs[dir][nx][ny][(mu2 & 1) ^ 1].S) % mod2;
hs[dir][i][j][mu2 & 1] = {nh1, nh2};
}
if (K >> mu2 & 1)
{
rep(dir, 0, 7) rep(i, 0, n - 1) rep(j, 0, m - 1)
{
int x = i + dx[dir] * steps, y = j + dy[dir] * steps;
x = (x % n + n) % n;
y = (y % m + m) % m;
int nh1 = (fin[dir][i][j].F * 1LL * pw1[mu2] % mod1 + hs[dir][x][y][mu2 & 1].F) % mod1;
int nh2 = (fin[dir][i][j].S * 1LL * pw2[mu2] % mod2 + hs[dir][x][y][mu2 & 1].S) % mod2;
fin[dir][i][j] = {nh1, nh2};
}
steps += (1 << mu2);
}
}
rep(dir, 0, 7) rep(i, 0, n - 1) rep(j, 0, m - 1) allHash.pb(fin[dir][i][j]);
sort(all(allHash));
//for (ii v : allHash) cout << "(" << v.F << ", " << v.S << ")\n";
ll num = 0, tot = (n * 1LL * m * 8 * n * m * 8);
for (int l = 0, r = 0; l < SZ(allHash); l = r)
{
while (r < SZ(allHash) && allHash[r] == allHash[l]) r++;
num += (r - l) * 1LL * (r - l);
}
ll g = __gcd(num, tot);
cout << (num / g) << '/' << (tot / g);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
512 KB |
Output is correct |
| 2 |
Correct |
1 ms |
768 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1024 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 5 |
Correct |
6 ms |
3328 KB |
Output is correct |
| 6 |
Correct |
31 ms |
8572 KB |
Output is correct |
| 7 |
Correct |
213 ms |
23528 KB |
Output is correct |
| 8 |
Correct |
775 ms |
64228 KB |
Output is correct |
