#include<bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int MAXN = 505;
const int mod1 = 1e9 + 696969;
const int mod2 = 1e9 + 409;
vector<lint> hashes;
int n, m, k;
char str[MAXN][MAXN];
int spt1[2][MAXN][MAXN], spt2[2][MAXN][MAXN];
int hsh0[MAXN][MAXN], hsh1[MAXN][MAXN], nhsh0[MAXN][MAXN], nhsh1[MAXN][MAXN];
lint pwr1[30], pwr2[30];
void Do(int dx, int dy){
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
spt1[0][i][j] = spt2[0][i][j] = str[i][j];
hsh0[i][j] = hsh1[i][j] = 0;
}
}
for(int i=1; i<=30; i++){
if((k >> (i-1)) & 1){
for(int j=0; j<n; j++){
for(int k=0; k<m; k++){
int nxtX = j - (dx<<(i-1));
int nxtY = k - (dy<<(i-1));
nxtX %= n, nxtY %= m;
nxtX += n, nxtY += m;
nxtX %= n, nxtY %= m;
nhsh0[j][k] = (hsh0[nxtX][nxtY] * pwr1[i-1] + spt1[(i-1)%2][j][k]) % mod1;
nhsh1[j][k] = (hsh1[nxtX][nxtY] * pwr2[i-1] + spt2[(i-1)%2][j][k]) % mod2;
}
}
memcpy(hsh0, nhsh0, sizeof(hsh0));
memcpy(hsh1, nhsh1, sizeof(hsh1));
}
for(int j=0; j<n; j++){
for(int k=0; k<m; k++){
int nxtX = j - (dx<<(i-1));
int nxtY = k - (dy<<(i-1));
nxtX %= n, nxtY %= m;
nxtX += n, nxtY += m;
nxtX %= n, nxtY %= m;
spt1[i%2][j][k] = (spt1[(i-1)%2][nxtX][nxtY] * pwr1[i-1] + spt1[(i-1)%2][j][k]) % mod1;
spt2[i%2][j][k] = (spt2[(i-1)%2][nxtX][nxtY] * pwr2[i-1] + spt2[(i-1)%2][j][k]) % mod2;
}
}
}
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
lint ans = 1ll * hsh0[i][j] * mod2 + hsh1[i][j];
hashes.push_back(ans);
}
}
}
lint gcd(lint x, lint y){ return y ? gcd(y, x%y) : x; }
int main(){
scanf("%d %d %d",&n,&m,&k);
for(int i=0; i<n; i++) scanf("%s", str[i]);
pwr1[0] = pwr2[0] = 257;
for(int i=1; i<30; i++){
pwr1[i] = 1ll * pwr1[i-1] * pwr1[i-1] % mod1;
pwr2[i] = 1ll * pwr2[i-1] * pwr2[i-1] % mod2;
}
lint Y = 64ll * n * m * n * m;
for(int i=-1; i<=1; i++){
for(int j=-1; j<=1; j++){
if(i || j) Do(i, j);
}
}
lint X = 0;
sort(hashes.begin(), hashes.end());
for(int i=0; i<hashes.size(); ){
int e = i;
while(e < hashes.size() && hashes[e] == hashes[i]) e++;
X += 1ll * (e - i) * (e - i);
i = e;
}
lint g = gcd(X, Y);
X /= g, Y /= g;
printf("%lld/%lld\n", X, Y);
}
Compilation message
osmosmjerka.cpp: In function 'int main()':
osmosmjerka.cpp:77:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<hashes.size(); ){
~^~~~~~~~~~~~~~
osmosmjerka.cpp:79:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(e < hashes.size() && hashes[e] == hashes[i]) e++;
~~^~~~~~~~~~~~~~~
osmosmjerka.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&n,&m,&k);
~~~~~^~~~~~~~~~~~~~~~~~~~~
osmosmjerka.cpp:63:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=0; i<n; i++) scanf("%s", str[i]);
~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
2304 KB |
Output is correct |
| 2 |
Correct |
8 ms |
2432 KB |
Output is correct |
| 3 |
Correct |
8 ms |
2432 KB |
Output is correct |
| 4 |
Correct |
15 ms |
2724 KB |
Output is correct |
| 5 |
Correct |
22 ms |
3064 KB |
Output is correct |
| 6 |
Correct |
70 ms |
4264 KB |
Output is correct |
| 7 |
Correct |
507 ms |
9188 KB |
Output is correct |
| 8 |
Correct |
1750 ms |
25452 KB |
Output is correct |
