#include <bits/stdc++.h>
#if __has_include("debugging.hpp")
#include "debugging.hpp"
#endif
using namespace std;
using ll = long long;
ll M = 1e9 + 9;
constexpr ll B = 9973;
class HashedString {
private:
vector<ll> p_hash;
public:
static vector<ll> pow;
HashedString(const string& s) : p_hash(s.size() + 1) {
while (pow.size() <= s.size()) {
pow.push_back((pow.back() * B) % M);
}
p_hash[0] = 0;
for (int i = 0; i < s.size(); i++) {
p_hash[i + 1] = ((p_hash[i] * B) % M + s[i]) % M;
}
}
ll get_hash(int start, int end) {
ll raw_val = (p_hash[end + 1] - (p_hash[start] * pow[end - start + 1]));
return (raw_val % M + M) % M;
}
};
vector<ll> HashedString::pow = {1};
ll binpow(ll x, ll n, ll m) {
assert(n >= 0);
x %= m;
ll res = 1;
while (n > 0) {
if (n % 2 == 1) {
res = res * x % m;
}
x = x * x % m;
n /= 2;
}
return res;
}
ll mod_inv(ll x, ll m) { return binpow(x, m - 2, m); }
constexpr int DR[] = {0, 0, 1, -1, 1, -1, -1, 1};
constexpr int DC[] = {1, -1, 0, 0, 1, -1, 1, -1};
int main() {
int row_num, col_num;
int len;
cin >> row_num >> col_num >> len;
vector<string> grid(row_num);
for (string& r : grid) {
cin >> r;
assert(r.size() == col_num);
}
vector<ll> hashes1;
for (int dir = 0; dir < 8; dir++) {
vector<vector<bool>> visited(row_num, vector<bool>(col_num));
for (int r = 0; r < row_num; r++) {
for (int c = 0; c < col_num; c++) {
if (visited[r][c]) {
continue;
}
string loop;
int at_r = r, at_c = c;
while (!visited[at_r][at_c]) {
visited[at_r][at_c] = true;
loop.push_back(grid[at_r][at_c]);
at_r = (at_r + DR[dir] + row_num) % row_num;
at_c = (at_c + DC[dir] + col_num) % col_num;
}
ll loop_pow = binpow(B, loop.size(), M);
ll div_by = mod_inv(loop_pow - 1, M);
HashedString hashed(loop);
ll whole = hashed.get_hash(0, loop.size() - 1);
for (int i = 0; i < loop.size(); i++) {
int head_amt = min(len, (int)loop.size() - i);
int mid_loops = (len - head_amt) / loop.size();
int tail_amt = (len - head_amt) % loop.size();
ll head_hash = hashed.get_hash(i, i + head_amt - 1);
head_hash = head_hash * binpow(B, len - head_amt, M) % M;
ll mid_hash =
whole * (binpow(loop_pow, mid_loops, M) - 1) % M * div_by % M;
mid_hash = mid_hash * binpow(B, tail_amt, M) % M;
ll tail_hash = hashed.get_hash(0, tail_amt - 1);
ll hsh = (head_hash + mid_hash + tail_hash) % M;
hashes1.push_back(hsh);
}
}
}
}
M = 1e9 + 7;
HashedString::pow = {1};
vector<ll> hashes2;
for (int dir = 0; dir < 8; dir++) {
vector<vector<bool>> visited(row_num, vector<bool>(col_num));
for (int r = 0; r < row_num; r++) {
for (int c = 0; c < col_num; c++) {
if (visited[r][c]) {
continue;
}
string loop;
int at_r = r, at_c = c;
while (!visited[at_r][at_c]) {
visited[at_r][at_c] = true;
loop.push_back(grid[at_r][at_c]);
at_r = (at_r + DR[dir] + row_num) % row_num;
at_c = (at_c + DC[dir] + col_num) % col_num;
}
ll loop_pow = binpow(B, loop.size(), M);
ll div_by = mod_inv(loop_pow - 1, M);
HashedString hashed(loop);
ll whole = hashed.get_hash(0, loop.size() - 1);
for (int i = 0; i < loop.size(); i++) {
int head_amt = min(len, (int)loop.size() - i);
int mid_loops = (len - head_amt) / loop.size();
int tail_amt = (len - head_amt) % loop.size();
ll head_hash = hashed.get_hash(i, i + head_amt - 1);
head_hash = head_hash * binpow(B, len - head_amt, M) % M;
ll mid_hash =
whole * (binpow(loop_pow, mid_loops, M) - 1) % M * div_by % M;
mid_hash = mid_hash * binpow(B, tail_amt, M) % M;
ll tail_hash = hashed.get_hash(0, tail_amt - 1);
ll hsh = (head_hash + mid_hash + tail_hash) % M;
hashes2.push_back(hsh);
}
}
}
}
assert(hashes1.size() == hashes2.size());
map<pair<ll, ll>, int> hash_occ;
for (int i = 0; i < hashes1.size(); i++) {
hash_occ[{hashes1[i], hashes2[i]}]++;
}
ll total_strings = (ll)row_num * row_num * col_num * col_num * 64;
ll same_pairs = 0;
for (const auto& [_, amt] : hash_occ) {
same_pairs += (ll)amt * amt;
}
ll div_by = gcd(total_strings, same_pairs);
printf("%lli/%lli\n", same_pairs / div_by, total_strings / div_by);
}
Compilation message
osmosmjerka.cpp: In constructor 'HashedString::HashedString(const string&)':
osmosmjerka.cpp:23:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for (int i = 0; i < s.size(); i++) {
| ~~^~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from osmosmjerka.cpp:1:
osmosmjerka.cpp: In function 'int main()':
osmosmjerka.cpp:61:25: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
61 | assert(r.size() == col_num);
| ~~~~~~~~~^~~~~~~~~~
osmosmjerka.cpp:86:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for (int i = 0; i < loop.size(); i++) {
| ~~^~~~~~~~~~~~~
osmosmjerka.cpp:131:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | for (int i = 0; i < loop.size(); i++) {
| ~~^~~~~~~~~~~~~
osmosmjerka.cpp:154:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
154 | for (int i = 0; i < hashes1.size(); i++) {
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
2 ms |
348 KB |
Output is correct |
| 5 |
Correct |
7 ms |
604 KB |
Output is correct |
| 6 |
Correct |
46 ms |
4164 KB |
Output is correct |
| 7 |
Correct |
440 ms |
27400 KB |
Output is correct |
| 8 |
Correct |
1843 ms |
65136 KB |
Output is correct |
