#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int mxN=500, di[8]={0, 1, 1, 1, 0, -1, -1, -1}, dj[8]={-1, -1, 0, 1, 1, 1, 0, -1}, B=29;
int n, m, k;
string g[mxN];
ull a1, a2, a3, c[2][mxN*mxN], e[2][mxN*mxN], f[8*mxN*mxN];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> k, k=min(n*m, k);
for(int i=0; i<n; ++i)
cin >> g[i];
for(int d=0; d<8; ++d) {
for(int i=0; i<n; ++i)
for(int j=0; j<m; ++j)
c[0][i*m+j]=g[i][j]-'a'+1;
ull pB=B;
memset(e[0], 0, 8*n*m);
int a=0;
for(int l=1; l<18; ++l, pB*=pB) {
if(k>>l-1&1) {
a^=1;
for(int i=0; i<n; ++i)
for(int j=0; j<m; ++j)
e[a][i*m+j]=c[l&1^1][i*m+j]*pB+e[a^1][(i+(di[d]<<l-1)%n+n)%n*m+(j+(dj[d]<<l-1)%m+m)%m];
}
for(int i=0; i<n; ++i)
for(int j=0; j<m; ++j)
c[l&1][i*m+j]=c[l&1^1][i*m+j]*pB+c[l&1^1][(i+(di[d]<<l-1)%n+n)%n*m+(j+(dj[d]<<l-1)%m+m)%m];
}
memcpy(f+d*n*m, e[a], 8*n*m);
}
sort(f, f+8*n*m);
for(int i=0, j=0; i<8*n*m; i=j) {
for(; j<8*n*m&&f[j]==f[i]; ++j);
a1+=1ll*(j-i)*(j-i);
}
a2=n*m*8, a2*=a2;
a3=__gcd(a1, a2);
cout << a1/a3 << "/" << a2/a3;
}
Compilation message
osmosmjerka.cpp: In function 'int main()':
osmosmjerka.cpp:26:11: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
if(k>>l-1&1) {
~^~
osmosmjerka.cpp:30:22: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
e[a][i*m+j]=c[l&1^1][i*m+j]*pB+e[a^1][(i+(di[d]<<l-1)%n+n)%n*m+(j+(dj[d]<<l-1)%m+m)%m];
~^~
osmosmjerka.cpp:30:57: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
e[a][i*m+j]=c[l&1^1][i*m+j]*pB+e[a^1][(i+(di[d]<<l-1)%n+n)%n*m+(j+(dj[d]<<l-1)%m+m)%m];
~^~
osmosmjerka.cpp:30:82: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
e[a][i*m+j]=c[l&1^1][i*m+j]*pB+e[a^1][(i+(di[d]<<l-1)%n+n)%n*m+(j+(dj[d]<<l-1)%m+m)%m];
~^~
osmosmjerka.cpp:34:23: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
c[l&1][i*m+j]=c[l&1^1][i*m+j]*pB+c[l&1^1][(i+(di[d]<<l-1)%n+n)%n*m+(j+(dj[d]<<l-1)%m+m)%m];
~^~
osmosmjerka.cpp:34:42: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
c[l&1][i*m+j]=c[l&1^1][i*m+j]*pB+c[l&1^1][(i+(di[d]<<l-1)%n+n)%n*m+(j+(dj[d]<<l-1)%m+m)%m];
~^~
osmosmjerka.cpp:34:60: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
c[l&1][i*m+j]=c[l&1^1][i*m+j]*pB+c[l&1^1][(i+(di[d]<<l-1)%n+n)%n*m+(j+(dj[d]<<l-1)%m+m)%m];
~^~
osmosmjerka.cpp:34:85: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
c[l&1][i*m+j]=c[l&1^1][i*m+j]*pB+c[l&1^1][(i+(di[d]<<l-1)%n+n)%n*m+(j+(dj[d]<<l-1)%m+m)%m];
~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
4 ms |
512 KB |
Output is correct |
| 6 |
Correct |
12 ms |
1152 KB |
Output is correct |
| 7 |
Correct |
82 ms |
6136 KB |
Output is correct |
| 8 |
Correct |
306 ms |
24144 KB |
Output is correct |
