#include <bits/stdc++.h>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC optimize("fast-math")
#include <ext/pb_ds/assoc_container.hpp>
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define s2 array<short,2>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
const int N = 510;
const int M = 100100;
const int x = 233;
const int PW = 73;
const int md = 999999937;
//const int md = int(1e9) + 9;
//const int md = 998244353;
gp_hash_table<int, int> mem;
int n, m, stp[8][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
int a[N][N], hsh[2][N][N], rhsh[N][N], k;
s2 nt[2][N][N], from[N][N];
int mult(int x, int y) { return (1ll * x * y) % md; }
int sum(int x, int y){
x += y;
if (x >= md)
x -= md;
return x;
}
int sub(int x, int y){
x -= y;
if (x < 0)
x += md;
return x;
}
int binpow(int x, int po){
int res = 1;
while (po > 0){
if (x & 1)
res = mult(res, x);
x = mult(x, x);
po >>= 1;
}
return res;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef _LOCAL
freopen("in.txt","r",stdin);
#endif // _LOCAL
cin >> n >> m >> k;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++){
char c; cin >> c;
a[i][j] = c - 'a' + 1;
}
for (int it = 0; it < 8; it++){
int tp = 0;
int ad = PW, kk = k, mul = 1;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
hsh[0][i][j] = a[i][j];
from[i][j] = {i, j};
rhsh[i][j] = 0;
int x = i, y = j;
x += stp[it][0];
y += stp[it][1];
if (x < 0) x += n;
if (y < 0) y += m;
if (x >= n) x -= n;
if (y >= m) y -= m;
nt[0][i][j] = {x, y};
if (kk & 1) {
rhsh[i][j] = hsh[0][i][j];
from[i][j] = {x, y};
}
}
if (kk & 1)
mul = PW;
kk >>= 1;
while (kk > 0){
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
int x = nt[tp][i][j][0], y = nt[tp][i][j][1];
int nw = sum(mult(hsh[tp][x][y], ad), hsh[tp][i][j]);
hsh[tp ^ 1][i][j] = nw;
nt[tp ^ 1][i][j] = nt[tp][x][y];
}
if (kk & 1) {
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
int x = from[i][j][0], y = from[i][j][1];
int nw = hsh[tp ^ 1][x][y];
rhsh[i][j] = sum(rhsh[i][j], mult(mul, nw));
from[i][j] = nt[tp ^ 1][x][y];
}
mul = mult(mul, mult(ad, ad));
}
ad = mult(ad, ad);
tp ^= 1;
kk >>= 1;
}
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
mem[rhsh[i][j]]++;
}
ll res = 0;
for (auto cr : mem){
ll nw = cr.second;
nw *= nw;
res += nw;
}
ll full = ll(n) * ll(m) * ll(n) * ll(m) * ll(8) * ll(8);
ll gc = __gcd(full, res);
cout << res / gc << "/" << full / gc;
return 0;
}
Compilation message
osmosmjerka.cpp: In function 'int main()':
osmosmjerka.cpp:77:31: warning: narrowing conversion of 'i' from 'int' to 'short int' inside { } [-Wnarrowing]
from[i][j] = {i, j};
^
osmosmjerka.cpp:77:31: warning: narrowing conversion of 'j' from 'int' to 'short int' inside { } [-Wnarrowing]
osmosmjerka.cpp:90:32: warning: narrowing conversion of 'x' from 'int' to 'short int' inside { } [-Wnarrowing]
nt[0][i][j] = {x, y};
^
osmosmjerka.cpp:90:32: warning: narrowing conversion of 'y' from 'int' to 'short int' inside { } [-Wnarrowing]
osmosmjerka.cpp:94:35: warning: narrowing conversion of 'x' from 'int' to 'short int' inside { } [-Wnarrowing]
from[i][j] = {x, y};
^
osmosmjerka.cpp:94:35: warning: narrowing conversion of 'y' from 'int' to 'short int' inside { } [-Wnarrowing]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
512 KB |
Output is correct |
| 4 |
Correct |
5 ms |
768 KB |
Output is correct |
| 5 |
Correct |
8 ms |
1280 KB |
Output is correct |
| 6 |
Correct |
21 ms |
4216 KB |
Output is correct |
| 7 |
Correct |
181 ms |
21852 KB |
Output is correct |
| 8 |
Correct |
572 ms |
25944 KB |
Output is correct |
