#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma target("tune=native")
//#define int long long
#define inf 2e9
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
const int N = 500, P[2] = {10, 31}, mod[2] = {1000000000 + 7, 999999937};
int n, m, k;
string s[N];
ll hs[N][N][31][2], deg[31][2];
int dx, dy;
void make_hash(){
deg[0][0] = deg[0][1] = 1;
deg[1][0] = P[0]; deg[1][1] = P[1];
for (int i = 2; i < 31; i++) {
deg[i][0] = deg[i - 1][0] * deg[i - 1][0];
deg[i][1] = deg[i - 1][1] * deg[i - 1][1];
deg[i][0] %= mod[0];
deg[i][1] %= mod[1];
}
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
hs[i][j][0][0] = hs[i][j][0][1] = (s[i][j] - 'a' + 1);
for (int st = 1; st < 31; st++){
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
hs[i][j][st][0] = hs[((i+(dx*(1<<(st - 1)))%n)+2*n)%n][((j+(dy*(1<<(st - 1)))%m)+2*m)%m][st - 1][0] * deg[st][0] + hs[i][j][st - 1][0];
hs[i][j][st][1] = hs[((i+(dx*(1<<(st - 1)))%n)+2*n)%n][((j+(dy*(1<<(st - 1)))%m)+2*m)%m][st - 1][1] * deg[st][1] + hs[i][j][st - 1][1];
hs[i][j][st][0] %= mod[0];
hs[i][j][st][1] %= mod[1];
}
}
}
}
map <pair<ll, ll>, ll> mp;
vector <pair <ll, ll> > v;
void get_cnt(int k){
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
pair <ll, ll> e;
int X = i, Y = j;
for (int g = 0; g < 31; g++){
if (!((1<<g) & k)) continue;
e.first += hs[X][Y][g][0] * deg[g][0];
e.second += hs[X][Y][g][1] * deg[g][1];
e.first %= mod[0];
e.second %= mod[1];
X = ((X+(dx*(1<<g))%n)+2*n)%n;
Y = ((Y+(dy*(1<<g))%m)+2*m)%m;
}
v.push_back(e);
mp[e]++;
}
}
}
void gen(){
for (int i = -1; i <= 1; i++){
for (int j = -1; j <= 1; j++){
if (!i && !j) continue;
dx = i; dy = j;
make_hash();
get_cnt(k);
}
}
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif // LOCAL
cin >> n >> m >> k;
for (int i = 0; i < n; i++) cin >> s[i];
gen();
ll ans = 0;
sort(all(v));
ll cnt = 0;
if (v[1] != v[0]) ans++;
else cnt = 1;
for (int i = 1; i < v.size(); i++){
if (v[i] == v[i - 1]) cnt++;
else{
ans += cnt * cnt;
cnt = 1;
}
}
ans += cnt * cnt;
// for (auto u: v) cout << u.first << "\n";
// for (auto u: mp){
//// ans += u.second * u.second;
// cout << u.first.first << " : " << u.second << "\n";
// }
ll zn = n * m * 8; zn *= zn;
ll gcd = __gcd(ans, zn);
cout << ans/gcd << "/"<<zn/gcd;
}
Compilation message
osmosmjerka.cpp:4:0: warning: ignoring #pragma target [-Wunknown-pragmas]
#pragma target("tune=native")
osmosmjerka.cpp: In function 'int32_t main()':
osmosmjerka.cpp:92:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < v.size(); i++){
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
512 KB |
Output is correct |
| 4 |
Correct |
2 ms |
768 KB |
Output is correct |
| 5 |
Correct |
8 ms |
1764 KB |
Output is correct |
| 6 |
Correct |
62 ms |
8552 KB |
Output is correct |
| 7 |
Correct |
1000 ms |
57040 KB |
Output is correct |
| 8 |
Correct |
3797 ms |
186384 KB |
Output is correct |
