#include <bits/stdc++.h>
#if __has_include("debugging.hpp")
#include "debugging.hpp"
#endif
using namespace std;
using ll = long long;
constexpr ll M = 1e9 + 9;
constexpr ll B = 9973;
class HashedString {
private:
static vector<ll> pow;
vector<ll> p_hash;
public:
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) {
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) { return binpow(x, M - 2); }
constexpr int DR[] = {0, 1, 1, -1};
constexpr int DC[] = {1, 0, 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);
}
auto move_hash = [&](ll hsh, ll amt) {
return hsh * binpow(B, amt) % M;
};
map<ll, int> hash_occ;
for (int dir = 0; dir < 4; 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());
ll div_by = mod_inv(loop_pow - 1);
for (int rev = 0; rev < 2; rev++) {
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 = hashed.get_hash(i, i + head_amt - 1);
head = move_hash(head, len - head_amt);
ll mid_hash = whole * (binpow(loop_pow, mid_loops) - 1) % M * div_by % M;
mid_hash = move_hash(mid_hash, tail_amt);
ll tail_hash = hashed.get_hash(0, tail_amt - 1);
ll hsh = (head + mid_hash + tail_hash) % M;
hash_occ[hsh]++;
}
if (rev == 0) {
reverse(loop.begin(), loop.end());
}
}
}
}
}
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:22:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | 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:58:25: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
58 | assert(r.size() == col_num);
| ~~~~~~~~~^~~~~~~~~~
osmosmjerka.cpp:88:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for (int i = 0; i < loop.size(); i++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
352 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
4 ms |
604 KB |
Output is correct |
| 6 |
Correct |
32 ms |
3340 KB |
Output is correct |
| 7 |
Correct |
296 ms |
20484 KB |
Output is correct |
| 8 |
Incorrect |
1170 ms |
33972 KB |
Output isn't correct |
