#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][8][2], deg[31][2];
int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
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++)
for (int k = 0; k < 8; k++)
hs[i][j][0][k][0] = hs[i][j][0][k][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++){
for (int k = 0; k < 8; k++){
hs[i][j][st][k][0] = hs[((i+(dx[k]*(1<<(st - 1)))%n)+2*n)%n][((j+(dy[k]*(1<<(st - 1)))%m)+2*m)%m][st - 1][k][0] * deg[st][0] + hs[i][j][st - 1][k][0];
hs[i][j][st][k][1] = hs[((i+(dx[k]*(1<<(st - 1)))%n)+2*n)%n][((j+(dy[k]*(1<<(st - 1)))%m)+2*m)%m][st - 1][k][1] * deg[st][1] + hs[i][j][st - 1][k][1];
hs[i][j][st][k][0] %= mod[0];
hs[i][j][st][k][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++){
for (int d = 0; d < 8; d++){
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][d][0] * deg[g][0];
e.second += hs[X][Y][g][d][1] * deg[g][1];
e.first %= mod[0];
e.second %= mod[1];
X = ((X+(dx[d]*(1<<g))%n)+2*n)%n;
Y = ((Y+(dy[d]*(1<<g))%m)+2*m)%m;
}
v.push_back(e);
// mp[e]++;
}
}
}
}
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];
make_hash();
get_cnt(k);
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:88: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 |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
512 KB |
Output is correct |
| 3 |
Correct |
1 ms |
896 KB |
Output is correct |
| 4 |
Correct |
3 ms |
2176 KB |
Output is correct |
| 5 |
Correct |
10 ms |
7296 KB |
Output is correct |
| 6 |
Correct |
64 ms |
33652 KB |
Output is correct |
| 7 |
Correct |
715 ms |
243848 KB |
Output is correct |
| 8 |
Runtime error |
108 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
