// https://oj.uz/problem/view/COCI17_osmosmjerka
#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
#include <map>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
// 从任一点出发，最多LCM(M,N)个字符之后，就会出现重复的pattern，因此我们只要生成这个长度的hash，就可以找到所有唯一字符串了。
// 然后出现重复的概率，就是每个unique pattern概率的平方和。
//
// Hash要按binary jumping方式来算，这样就快了。
//
// 因为数据较多（500*500*8=2e6），所以32位的hash是不够的，会有birthday paradox collision。办法是用两个32位hash，这个
// 就相当于64位，就可以了。
//
// O(n^2logn)
int m,n,K; // m,n <= 500, K <= 1e9
char s[505][505]; // M rows, N cols
int dir[8][2] = {{0,1},{0,-1},{1,0},{-1,0},{1,1},{-1,-1},{1,-1},{-1,1}};
int hsh[2][23][505][505]; // hash value patterns for 23 log levels
int p[2][23];
map<pi,int> cnts; // hash -> count
const int A[2] = {911382323, 69420}, M[2] = {972663749, (int)1e9+9};
ll gcd(ll a, ll b) {
return b == 0 ? a : gcd(b, a%b);
}
int main() {
scanf("%d %d %d", &m, &n, &K);
for (int i = 0; i < m; i++)
scanf("%s", s[i]);
int lcm = m*n/gcd(m,n);
if (K > lcm) K = lcm;
for (int j = 0; j < 2; j++) {
p[j][0] = A[j];
for (int i = 1; i < 23; i++)
p[j][i] = (ll)p[j][i-1] * p[j][i-1] % M[j];
}
for (int di = 0; di < 8; di++) { // 8 directions
// calc hash values for step-len strings from each pos
for (int lg = 0; lg < 23; lg++) {
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++) {
if (lg == 0)
hsh[0][di][r][c] = hsh[1][di][r][c] = s[r][c];
else {
int R = (r + (1 << (lg-1)) * (m + dir[di][0])) % m;
int C = (c + (1 << (lg-1)) * (n + dir[di][1])) % n;
for (int j = 0; j < 2; j++)
hsh[j][lg][r][c] = ((ll)hsh[j][lg-1][r][c] * p[j][lg-1] + hsh[j][lg-1][R][C]) % M[j];
}
}
}
// calc hashes for K-len strings from each pos
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++) {
int hs[2] = {0};
int R = r, C = c;
for (int j = 0; j < 23; j++) { // binary jumping
if ((K & (1 << j)) == 0) continue;
for (int k = 0; k < 2; k++)
hs[k] = ((ll)hs[k] * p[k][j] + hsh[k][j][R][C]) % M[k];
R = (R + (ll)(1<<j)*(m+dir[di][0])) % m;
C = (C + (ll)(1<<j)*(n+dir[di][1])) % n;
}
cnts[{hs[0], hs[1]}]++;
}
}
ll total = m*n*8;
total = total*total;
ll squared = 0;
for (auto e: cnts) {
int v = e.second;
squared += (ll)v*v;
}
ll g = gcd(total, squared);
printf("%lld/%lld", squared/g, total/g);
return 0;
}
Compilation message
osmosmjerka.cpp: In function 'int main()':
osmosmjerka.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
36 | scanf("%d %d %d", &m, &n, &K);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
osmosmjerka.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
38 | scanf("%s", s[i]);
| ~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
480 KB |
Output is correct |
| 2 |
Correct |
1 ms |
864 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1320 KB |
Output is correct |
| 4 |
Correct |
3 ms |
2344 KB |
Output is correct |
| 5 |
Correct |
8 ms |
4268 KB |
Output is correct |
| 6 |
Correct |
49 ms |
12368 KB |
Output is correct |
| 7 |
Correct |
469 ms |
37728 KB |
Output is correct |
| 8 |
Correct |
1758 ms |
79104 KB |
Output is correct |
