#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<typename K> using hset = gp_hash_table<K, null_type>;
template<typename K, typename V> using hmap = gp_hash_table<K, V>;
using namespace std;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define smax(x, y) (x = max(x, y))
#define smin(x, y) (x = min(x, y))
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i,0,a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i,0,a)
using ll = long long;
using ld = long double;
template<typename T>
using vv = vector<vector<T>>;
using vi = vector<int>;
using ii = array<int, 2>;
using vii = vector<ii>;
using vvi = vv<int>;
using vll = vector<ll>;
using l2 = array<ll, 2>;
using vl2 = vector<l2>;
using vvll = vv<ll>;
template<typename T>
using minq = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using maxq = priority_queue<T>;
template<typename T>
using oset = tree<T, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
const ll M = 1000000007;
const ll infll = M * M;
template<ll M>
struct modint {
static ll _reduce(ll n) {
constexpr static ll b = -1ull/M;
ll r = n-(ll)(__uint128_t(b)*n>>64)*M; return r >= M ? r-M : r;
}
static ll _pow(ll n, ll k) {
if (M > 1.5e9) {
modint r = 1;
modint mn = n;
for (; k > 0; k >>= 1, mn *= mn)
if (k&1) r *= mn;
return r.v;
} else {
ll r = 1;
for (; k > 0; k >>= 1, n = _reduce(n*n))
if (k&1) r = _reduce(r*n);
return r;
}
}
ll v; modint(ll n = 0) : v(_reduce(n)) { v += (M&(0-(v<0))); }
friend string to_string(const modint n) { return to_string(n.v); }
friend istream& operator>>(istream& i, modint& n) { return i >> n.v; }
friend ostream& operator<<(ostream& o, const modint n) { return o << n.v; }
template<typename T> explicit operator T() { return T(v); }
friend bool operator==(const modint n, const modint m) { return n.v == m.v; }
friend bool operator!=(const modint n, const modint m) { return n.v != m.v; }
friend bool operator<(const modint n, const modint m) { return n.v < m.v; }
friend bool operator<=(const modint n, const modint m) { return n.v <= m.v; }
friend bool operator>(const modint n, const modint m) { return n.v > m.v; }
friend bool operator>=(const modint n, const modint m) { return n.v >= m.v; }
modint& operator+=(const modint n) { v += n.v; v -= (M&(0-(v>=M))); return *this; }
modint& operator-=(const modint n) { v -= n.v; v += (M&(0-(v<0))); return *this; }
modint& operator*=(const modint n) { v = _reduce(v*n.v); return *this; }
modint& operator/=(const modint n) { v = _reduce(v*_pow(n.v, M-2)); return *this; }
friend modint operator+(const modint n, const modint m) { return modint(n) += m; }
friend modint operator-(const modint n, const modint m) { return modint(n) -= m; }
friend modint operator*(const modint n, const modint m) { return modint(n) *= m; }
friend modint operator/(const modint n, const modint m) { return modint(n) /= m; }
modint& operator++() { return *this += 1; }
modint& operator--() { return *this -= 1; }
modint operator++(int) { modint t = *this; return *this += 1, t; }
modint operator--(int) { modint t = *this; return *this -= 1, t; }
modint operator+() { return *this; }
modint operator-() { return modint(0) -= *this; }
// O(logk) modular exponentiation
[[nodiscard]] modint pow(const ll k) const {
return k < 0 ? _pow(v, M-1-(-k%(M-1))) : _pow(v, k);
}
[[nodiscard]] modint inv() const { return _pow(v, M-2); }
};
mt19937 randint(chrono::steady_clock::now().time_since_epoch().count());
// returns a random integer over [a, b] inclusive
inline int uniform_randint(const int a, const int b) {
return uniform_int_distribution<int>(a, b)(randint);
}
constexpr ll P = (1ull << 61) - 1;
template<>
modint<P> &modint<P>::operator*=(const modint<P> n) {
uint64_t l1 = (uint32_t) v, h1 = v >> 32, l2 = (uint32_t) n.v, h2 = n.v >> 32;
uint64_t l = l1 * l2, m = l1 * h2 + l2 * h1, h = h1 * h2;
uint64_t ret = (l & P) + (l >> 61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
ret = (ret & P) + (ret >> 61);
ret = (ret & P) + (ret >> 61);
v = ret - 1;
return *this;
}
using mi = modint<P>; // ????
using vmi = vector<mi>;
int b1 = uniform_randint(5000, 10000);
int b2 = uniform_randint(10001, 20000);
struct shash_t {
int sz{};
mi h1, h2;
static inline hmap<int, pair<mi, mi>> cache;
shash_t& operator+=(const shash_t b) {
auto [szb, h1b, h2b] = b;
pair<mi, mi> ps;
if (cache.find(szb) == cache.end()) {
ps = {mi(b1).pow(szb), mi(b2).pow(szb)};
cache[szb] = ps;
} else {
ps = cache[szb];
}
h1 = (h1 * ps.first) + h1b;
h2 = (h2 * ps.second) + h2b;
sz += szb;
return *this;
}
friend shash_t operator+(const shash_t a, const shash_t b) {
return shash_t(a) += b;
}
shash_t& operator*=(int t) {
if (t == 0) return *this = {};
shash_t og = *this;
R0F(i, log2(t)) {
*this += *this;
if (t & (1 << i)) *this += og;
}
return *this;
}
friend shash_t operator*(const shash_t a, const int t) {
return shash_t(a) *= t;
}
bool operator<(const shash_t &rhs) const {
if (sz < rhs.sz)
return true;
if (rhs.sz < sz)
return false;
if (h1 < rhs.h1)
return true;
if (rhs.h1 < h1)
return false;
return h2 < rhs.h2;
}
bool operator>(const shash_t &rhs) const {
return rhs < *this;
}
bool operator<=(const shash_t &rhs) const {
return !(rhs < *this);
}
bool operator>=(const shash_t &rhs) const {
return !(*this < rhs);
}
bool operator==(const shash_t &rhs) const {
return sz == rhs.sz &&
h1 == rhs.h1 &&
h2 == rhs.h2;
}
bool operator!=(const shash_t &rhs) const {
return !(rhs == *this);
}
};
struct hash_querier {
vmi hsh1, hsh2;
inline static vmi bp1{}, bp2{};
explicit hash_querier(const string &s) :
hsh1(s.size() + 1), hsh2(s.size() + 1) {
F0R(i, s.size()) {
hsh1[i + 1] = s[i] - 'a' + hsh1[i] * b1;
hsh2[i + 1] = s[i] - 'a' + hsh2[i] * b2;
}
bp1.reserve(s.size()+1);
bp2.reserve(s.size()+1);
if (bp1.empty()) {
bp1.eb(1);
bp2.eb(1);
}
FOR(i, bp1.size()-1, s.size()) {
bp1.pb(bp1[i] * b1);
bp2.pb(bp2[i] * b2);
}
}
// hash of substring [l, r] inclusive
shash_t query(int l, int r) const {
if (r < l) return {};
return {r - l + 1, hsh1[r + 1] - hsh1[l] * bp1[r - l + 1],
hsh2[r + 1] - hsh2[l] * bp2[r - l + 1]};
}
};
int m, n, k;
shash_t pad(const hash_querier & hq, int olen, int offset) {
return hq.query(offset, offset + olen - 1) * (k / olen) + hq.query(offset, offset + (k % olen) - 1);
}
vii dirs{{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> m >> n >> k;
smin(k, lcm(m, n));
vector<string> g(m);
F0R(i, m) cin >> g[i];
map<shash_t, ll> cnt;
using seen_t = array<int, 4>; // vis, offset, tot len, hashqi
vv<vector<seen_t>> seen(m, vv<seen_t>(n, vector<seen_t>(8)));
vector<hash_querier> hqs;
F0R(d, 8) {
auto[dr, dc] = dirs[d];
F0R(r, m) {
F0R(c, n) {
auto &[vis, offset, len, hqi] = seen[r][c][d];
if (!vis) {
if (abs(dr) + abs(dc) == 2) len = lcm(m, n);
else if (abs(dr) == 1) len = m;
else len = n;
hqi = hqs.size();
string s;
int cr = r, cc = c;
offset = 0;
F0R(off, len) {
s += g[cr][cc];
if (!seen[cr][cc][d][0])
seen[cr][cc][d] = {1, off, len, hqi};
cr = (cr + dr + m) % m;
cc = (cc + dc + n) % n;
}
hqs.eb(s + s);
vis = 1;
}
auto key = pad(hqs[hqi], len, offset);
cnt[key]++;
}
}
}
ll q = pow(m * n * 8, 2);
ll p = 0;
for (auto & [_, kcnt] : cnt) p += kcnt * kcnt;
ll gc = gcd(p, q);
p /= gc;
q /= gc;
cout << p << '/' << q << '\n';
// high level:
// 1) for each cell & direction get a "representative" string
// for each cell + direction store if we've visited that state,
// if we have we also need the offset + tot length of string
// we also need a reference to the relevant string/hash querier
// I can just make an array of hash queriers and store the index to be used
// 2) "extend" the string to length k
// 3) insert into map and continue as before
}
Compilation message
osmosmjerka.cpp: In constructor 'hash_querier::hash_querier(const string&)':
osmosmjerka.cpp:18:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | #define FOR(i, a, b) for (int i = (a); i < (b); ++i)
| ^
osmosmjerka.cpp:19:19: note: in expansion of macro 'FOR'
19 | #define F0R(i, a) FOR(i,0,a)
| ^~~
osmosmjerka.cpp:215:9: note: in expansion of macro 'F0R'
215 | F0R(i, s.size()) {
| ^~~
osmosmjerka.cpp:18:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | #define FOR(i, a, b) for (int i = (a); i < (b); ++i)
| ^
osmosmjerka.cpp:225:9: note: in expansion of macro 'FOR'
225 | FOR(i, bp1.size()-1, s.size()) {
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
2 ms |
588 KB |
Output is correct |
| 5 |
Correct |
5 ms |
1100 KB |
Output is correct |
| 6 |
Correct |
36 ms |
7296 KB |
Output is correct |
| 7 |
Correct |
477 ms |
51040 KB |
Output is correct |
| 8 |
Correct |
1528 ms |
145604 KB |
Output is correct |
