#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long
const ll p1 = 1663, p2 = 5953, mod = 1e9+7;
//left, right, up, down, up left, up right, down right, down left
int n, m, k; string grid[500];
int di[8] = {0, 0, -1, 1, -1, -1, 1, 1}, dj[8] = {-1, 1, 0, 0, -1, 1, 1, -1};
ll pow1 = 1, pow2 = 1; map<pair<ll, ll>, ll> eq;
bool in1(int i, int j) { return i >= 0 and i < n and j >= 0 and j < m; }
bool in2(int i, int j, int d) { return in1(i-(k-1)*di[d], j-(k-1)*dj[d]); }
void solve(int ti, int tj, int move, int d){
for (; in1(ti, tj); ti += di[move], tj += dj[move]){
ll hash1 = 0, hash2 = 0;
for (int i = ti, j = tj, cnt = 1; cnt <= k or in2(i, j, d); i += di[d], j += dj[d], cnt++){
ll curr = grid[(i+500*n)%n][(j+500*m)%m]-'a'+1;
hash1 = ((hash1*p1)+(curr))%mod; hash2 = ((hash2*p2)+(curr))%mod;
if (cnt > k){
hash1 = (hash1-(pow1*(grid[i-k*di[d]][j-k*dj[d]]-'a'+1)%mod)+mod)%mod;
hash2 = (hash2-(pow2*(grid[i-k*di[d]][j-k*dj[d]]-'a'+1)%mod)+mod)%mod;
}
if (cnt >= k)
eq[{hash1, hash2}]++;
}
}
}
int main() {
cin >> n >> m >> k; k = min(k, max(n, m)*8);
for (int i = 0; i < n; i++) cin >> grid[i];
for (int i = 0; i < k; i++) pow1 = (pow1*p1)%mod, pow2 = (pow2*p2)%mod;
solve(0, 0, 1, 7); solve(0, 0, 1, 6); solve(n-1, 0, 1, 4); solve(n-1, 0, 1, 5);
solve(n-2, 0, 2, 5); solve(n-2, m-1, 2, 4); solve(1, 0, 3, 6); solve(1, m-1, 3, 7);
solve(0, 0, 1, 3); solve(n-1, 0, 1, 2); solve(0, 0, 3, 1); solve(0, m-1, 3, 0);
ll good = 0, tot = (ll)(n*m*8)*(n*m*8);
for (auto elem : eq) good += elem.second*elem.second;
ll div = __gcd(good, tot); cout<<good/div<<"/"<<tot/div;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
236 KB |
Output is correct |
| 3 |
Correct |
2 ms |
332 KB |
Output is correct |
| 4 |
Correct |
3 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
528 KB |
Output is correct |
| 6 |
Correct |
39 ms |
3068 KB |
Output is correct |
| 7 |
Correct |
500 ms |
19268 KB |
Output is correct |
| 8 |
Correct |
1532 ms |
33512 KB |
Output is correct |
