#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) {
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
modint pow(const ll k) const {
return k < 0 ? _pow(v, M-1-(-k%(M-1))) : _pow(v, k);
}
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);
using shash_t = pair<mi, mi>;
struct hash_querier {
vmi hsh1, hsh2, bp1, bp2;
explicit hash_querier(const string &s) :
hsh1(s.size() + 1), hsh2(s.size() + 1),
bp1(s.size() + 1, 1), bp2(s.size() + 1, 1) {
F0R(i, s.size()) {
hsh1[i + 1] = s[i] - 'a' + hsh1[i] * b1;
hsh2[i + 1] = s[i] - 'a' + hsh2[i] * b2;
bp1[i + 1] = bp1[i] * b1;
bp2[i + 1] = bp2[i] * b2;
}
}
// hash of substring [l, r] inclusive
shash_t query(int l, int r) {
return {hsh1[r + 1] - hsh1[l] * bp1[r - l + 1],
hsh2[r + 1] - hsh2[l] * bp2[r - l + 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);
int m, n, k;
cin >> m >> n >> k;
vector<string> g(m);
F0R(i, m) cin >> g[i];
map<shash_t, int> cnt;
for (auto [dr, dc] : dirs) {
F0R(r, m) {
F0R(c, n) {
string s;
int cr = r, cc = c;
F0R(_, min(max(m, n), k)) {
s += g[cr][cc];
cr = (cr + dr + m) % m;
cc = (cc + dc + n) % n;
}
hash_querier rh(s);
cnt[rh.query(0, s.size()-1)]++;
}
}
}
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';
}
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:135:9: note: in expansion of macro 'F0R'
135 | F0R(i, s.size()) {
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
2 ms |
344 KB |
Output is correct |
| 4 |
Correct |
5 ms |
312 KB |
Output is correct |
| 5 |
Correct |
41 ms |
444 KB |
Output is correct |
| 6 |
Incorrect |
377 ms |
1720 KB |
Output isn't correct |
| 7 |
Execution timed out |
4051 ms |
4716 KB |
Time limit exceeded |
| 8 |
Execution timed out |
4017 ms |
3616 KB |
Time limit exceeded |
