#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll P = 9973;
ll MOD = 1e9+7;
ll poly[(int)5e2][(int)5e2];
ll ppow[(int)5e2];
int M,N,K;
//can't simulate the K-length string, need to stop when it hits origin again
//cycle must be in less than NM steps (think of movement as a permutation function)
//have hashmap using hashes as keys & count # of hashes
//TIME COMPLEXITY: O(8MN*MN)
//denom = (MN*8)^2
//numerator = sum (freq[i])^2
//then divide by gcd
ll gcd(ll x, ll y){
if (x>y){
swap(x,y);
}
if (x == 0){
return y;
}else{
return gcd(x,y%x);
}
//y >= x always
}
int main() {
cin >> M >> N >> K;
string s[M];
for (int i = 0; i < M; i++){
cin >> s[i];
}
unordered_map<ll, ll> count;
for (int i = 0; i < M; i++){
for (int j = 0; j < N; j++){
int curX = i;
int curY = j;
for (int dx = -1; dx <= 1; dx++){
for (int dy = -1; dy <= 1; dy++){
if (dx == 0 && dy == 0){
continue;
}
ll rollHash = (s[i][j]-'a');
while(true) {
curX = (curX + dx+M) % M;
curY = (curY + dy+N) % N;
rollHash = (rollHash*P+(s[curX][curY]-'a')+MOD)%MOD;
//will always end in lcm(M,N) moves so all hashes are of same-length string
if (curX == i && curY == j){
if (count.count(rollHash)==1) {
count[rollHash] += 1;
}else{
count[rollHash] = 1;
}
break;
}
}
}
}
}
}
ll num = 0;
for (auto e: count){
num += e.second*e.second;
}
ll denom = (8*M*N)*(8*M*N);
ll g = gcd(num, denom);
num = num/g;
denom = denom/g;
cout << num << "/" << denom;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
300 KB |
Output is correct |
| 4 |
Correct |
2 ms |
332 KB |
Output is correct |
| 5 |
Correct |
11 ms |
332 KB |
Output is correct |
| 6 |
Execution timed out |
4051 ms |
1852 KB |
Time limit exceeded |
| 7 |
Execution timed out |
4059 ms |
800 KB |
Time limit exceeded |
| 8 |
Execution timed out |
4065 ms |
6204 KB |
Time limit exceeded |
