#include <bits/stdc++.h>
template<__int128 p, __int128 m>
struct hash_string {
static std::vector<__int128> power;
std::vector<__int128> p_hash;
hash_string(const std::string& s) : p_hash(s.size()+1, 0) {
for (int i = 0; i < (int)s.size(); i++) {
p_hash[i+1] = (p_hash[i] * p + s[i]) % m;
}
}
__int128 pow(int i) {
while (i >= (int)power.size()) {
auto val = power.back();
val = val * p % m;
power.push_back(val);
}
return power[i];
}
__int128 pow(__int128 x, int i) {
if (i == 0) return 1;
auto ret = pow(x, i/2);
ret = ret * ret % m;
if (i & 1) ret = ret * x % m;
return ret;
}
__int128 pow_sum(__int128 x, int i) {
if (i == 1) return 1;
auto ret = pow_sum(x, i/2);
ret = (1 + pow(x, i/2)) % m * ret % m;
if (i & 1) {
ret = ret * x % m;
ret = (ret + x) % m;
}
return ret;
}
__int128 hash(int l, int r) { // [l, r] inclusive
assert(0 <= l && l <= r && r < (int)p_hash.size()-1);
auto ret = p_hash[r+1] - p_hash[l] * pow(r-l+1) % m;
ret = (ret + m) % m;
return ret;
}
__int128 hash(int l, int r, int k) {
int n = r - l + 1;
__int128 ret = 0;
if (k / n != 0) {
ret = hash(l, r) * pow_sum(pow(n), k/n) % m;
}
if (k % n != 0) {
ret = ret * pow(k % n) % m + hash(l, l + k % n - 1);
ret %= m;
}
return ret;
}
};
template<__int128 p, __int128 m>
std::vector<__int128> hash_string<p, m>::power {1};
struct hash_string2 {
hash_string<9973, 9223372036854775783LL> s1;
hash_string<9973, 9223372036854775643LL> s2;
hash_string2(const std::string& s) : s1(s), s2(s) {}
__int128 hash(int l, int r, int k) {
return (s1.hash(l, r, k) << 64) | s2.hash(l, r, k);
}
};
constexpr auto max = 501;
bool visited[max][max][4];
int main() {
std::cin.tie(0)->sync_with_stdio(0);
int n, m, k;
std::cin >> n >> m >> k;
std::vector<std::string> v(n);
for (auto &s : v) {
std::cin >> s;
}
std::map<__int128, int64_t> cnt;
auto update = [&](std::pair<int, int> start, int t) -> void {
const std::array<std::pair<int, int>, 4> direction {{{1, 0}, {1, 1}, {1, -1}, {0, 1}}};
auto [row, col] = start;
if (visited[row][col][t]) return;
const auto [dr, dc] = direction[t];
std::string s;
while (!visited[row][col][t]) {
assert(0 <= row && row < n && 0 <= col && col < m);
visited[row][col][t] = true;
s.push_back(v[row][col]);
row = (row + dr + n) % n;
col = (col + dc + m) % m;
}
int sz = int(std::size(s));
s += s;
hash_string2 hs(s);
for (int i = 0; i < sz; i++) {
auto hash = hs.hash(i, i+sz-1, k);
++cnt[hash];
}
std::reverse(s.begin(), s.end());
hash_string2 hs_reversed(s);
for (int i = 0; i < sz; i++) {
auto hash = hs_reversed.hash(i, i+sz-1, k);
++cnt[hash];
}
};
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int t = 0; t < 4; t++) {
update({i, j}, t);
}
}
}
int64_t p = 0;
int64_t q = 64 * n * n * m * m;
for (auto [key, val] : cnt) {
p += val * val;
}
auto g = std::gcd(p, q);
std::cout << p/g << '/' << q/g << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
9 ms |
340 KB |
Output is correct |
| 5 |
Correct |
65 ms |
588 KB |
Output is correct |
| 6 |
Incorrect |
329 ms |
4236 KB |
Output isn't correct |
| 7 |
Incorrect |
3120 ms |
29208 KB |
Output isn't correct |
| 8 |
Execution timed out |
4093 ms |
9828 KB |
Time limit exceeded |
