#include<bits/stdc++.h>
#define ii array<int, 2>
#define int long long
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
const int maxn = 505;
int n, m, k, nn, mm;
int st[32][maxn][maxn];
map<int,int> mp;
void make(int dc, int dr)
{
for (int lg = 1, base = 311; lg < 31; lg++)
{
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)
{
int nx = (1ll << (lg - 1)), ny = (1ll << (lg - 1));
nx = (i + dc * nx + nn) % n;
ny = (j + dr * ny + mm) % m;
st[lg][i][j] = st[lg - 1][i][j] * base + st[lg - 1][nx][ny];
}
base *= base;
}
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)
{
int cx = i, cy = j, tmp = 0;
for (int lg = 0, base = 311; lg < 31; lg++)
{
if (k >> lg & 1)
{
int nx = (1ll << lg), ny = (1ll << lg);
tmp = tmp * base + st[lg][cx][cy];
cx = (cx + dc * nx + nn) % n;
cy = (cy + dr * ny + mm) % m;
}
base *= base;
}
mp[tmp]++;
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// freopen("test.inp", "r", stdin);
// freopen("test.out", "w", stdout);
cin >> n >> m >> k;
nn = n * (int)1e9;
mm = m * (int)1e9;
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)
{
char c;
cin >> c;
st[0][i][j] = c - 'a' + 1;
}
for (int x = -1; x < 2; x++)
for (int y = -1; y < 2; y++)
if (!(x == y && x == 0))
make(x, y);
int x = 0, y = (n * m * 8) * (n * m * 8);
for (auto p : mp) x += p.second * p.second;
int g = __gcd(x, y);
cout << x / g << "/" << y / g;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
61784 KB |
Output is correct |
| 2 |
Correct |
7 ms |
62044 KB |
Output is correct |
| 3 |
Correct |
8 ms |
62040 KB |
Output is correct |
| 4 |
Correct |
8 ms |
62044 KB |
Output is correct |
| 5 |
Correct |
13 ms |
62300 KB |
Output is correct |
| 6 |
Correct |
46 ms |
64744 KB |
Output is correct |
| 7 |
Correct |
529 ms |
81364 KB |
Output is correct |
| 8 |
Correct |
1753 ms |
97224 KB |
Output is correct |
