#include <bits/stdc++.h>
using namespace std;
#define ll 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];
bool vis[mxN][mxN];
ll h[2*mxN*mxN+1],a1,a2,a3,pB=1,c[8*mxN*mxN];
int main() {
cin >> n >> m >> k,k=min(n*m,k);
for (int i=0; i<k; i++) {
pB*=B;
}
for (int i=0; i<n; i++) {
cin >> g[i];
}
for (int d=0,e=0; d<8; d++) {
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
if (vis[i][j]) {
continue;
}
int a=0;
for (int ci=i,cj=j; !vis[ci][cj]; ci=(ci+di[d]+n)%n,cj=(cj+dj[d]+m)%m) {
vis[ci][cj]=1;
h[++a]=g[ci][cj]-'a'+1;
}
for (int l=a; l+1<a+k; l+=a) {
memcpy(h+l+1,h+1,8*a);
}
for (int l=1; l<a+k; l++) {
h[l]+=h[l-1]*B;
}
for (int l=0; l<a; l++) {
c[e++]=h[l+k]-h[l]*pB;
}
}
}
memset(vis,0,sizeof(vis));
}
sort(c,c+8*n*m);
for (int i=0,j=0; i<8*n*m; i=j) {
for(; j<8*n*m&&c[j]==c[i]; ++j);
a1+=(ll)(j-i)*(j-i);
}
a2=n*m*8;
a2*=a2;
a3=__gcd(a1,a2);
cout << a1/a3 << '/' << a2/a3;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |