#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <set>
#include <map>
#include <numeric>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <tuple>
#include <cassert>
#include <array>
#include <list>
#include <random>
#include <initializer_list>
#include <chrono>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using db = double;
using ld = long double;
const i64 inf = i64(1E18);
template<class T>
constexpr T power(T a, i64 b) {
T res = 1;
for (; b; b /= 2, a *= a) {
if (b & 1) {
res *= a;
}
}
return res;
}
i64 mul(i64 a, i64 b, i64 p) {
i64 res = a * b - i64(1.L * a * b / p) * p;
res %= p;
if (res < 0) {
res += p;
}
return res;
}
template<i64 P>
struct MLong {
i64 x;
constexpr MLong() : x{} {}
constexpr MLong(i64 x) : x{ norm(x % P) } {}
constexpr i64 norm(i64 x) const {
if (x < 0) {
x += P;
}
if (x >= P) {
x -= P;
}
return x;
}
constexpr MLong inv() const {
assert(x != 0);
return power(*this, P - 2);
}
constexpr i64 val() const {
return x;
}
constexpr MLong& operator*=(MLong rhs)& {
x = mul(x, rhs.x, P);
return *this;
}
constexpr MLong& operator+=(MLong rhs)& {
x = norm(x + rhs.x);
return *this;
}
constexpr MLong& operator-=(MLong rhs)& {
x = norm(x - rhs.x);
return *this;
}
constexpr MLong& operator/=(MLong rhs)& {
return *this *= rhs.inv();
}
friend constexpr MLong operator*(MLong lhs, MLong rhs) {
MLong res = lhs;
res *= rhs;
return res;
}
friend constexpr MLong operator+(MLong lhs, MLong rhs) {
MLong res = lhs;
res += rhs;
return res;
}
friend constexpr MLong operator-(MLong lhs, MLong rhs) {
MLong res = lhs;
res -= rhs;
return res;
}
friend constexpr MLong operator/(MLong lhs, MLong rhs) {
MLong res = lhs;
res /= rhs;
return res;
}
friend constexpr istream& operator>>(istream& is, MLong& a) {
i64 v;
is >> v;
a = MLong(v);
return is;
}
friend constexpr ostream& operator<<(ostream& os, const MLong& a) {
return os << a.val();
}
friend constexpr bool operator==(MLong lhs, MLong rhs) {
return lhs.val() == rhs.val();
}
friend constexpr bool operator!=(MLong lhs, MLong rhs) {
return lhs.val() != rhs.val();
}
};
constexpr i64 P = i64(1E18) + 9;
using Z = MLong<P>;
i64 gcd(i64 a, i64 b) {
return (b ? gcd(b, a % b) : a);
}
i64 n, m, K;
vector<string> s(501);
vector<vector<vector<Z>>> h(501, vector<vector<Z>> (501, vector<Z> (31)));
vector<Z> pw(31);
map<i64, i64> f;
void work(i64 di, i64 dj) {
for (i64 i = 0; i < n; ++i) {
for (i64 j = 0; j < m; ++j) {
h[i][j][0] = s[i][j];
}
}
pw[0] = 1;
for (i64 k = 1; k < 31; ++k) {
for (i64 i = 0; i < n; ++i) {
for (i64 j = 0; j < m; ++j) {
h[i][j][k] = h[i][j][k - 1] * pw[k - 1] + h[(i + di * (1 << (k - 1)) % n + n) % n][(j + dj * (1 << (k - 1)) % m + m) % m][k - 1];
}
}
pw[k] = pw[k - 1] * pw[k - 1];
}
for (i64 i = 0; i < n; ++i) {
for (i64 j = 0; j < m; ++j) {
i64 l = K;
i64 ci = i, cj = j;
Z H;
for (i64 k = 30; k >= 0; --k) {
if ((1 << k) <= l) {
l -= (1 << k);
H = H * pw[k] + h[ci][cj][k];
ci = ((ci + di * (1 << k)) % n + n) % n;
cj = ((cj + dj * (1 << k)) % m + m) % m;
}
}
f[H.val()]++;
}
}
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
void solve() {
const Z B = rng() % (P - 100) + 50;
cin >> n >> m >> K;
for (i64 i = 0; i < n; ++i) {
cin >> s[i];
}
for (i64 di = -1; di <= 1; ++di) {
for (i64 dj = -1; dj <= 1; ++dj) {
if (di == 0 && dj == 0) {
continue;
}
work(di, dj);
}
}
i64 a = 0;
i64 b = (8 * n * m) * (8 * n * m);
for (auto _ : f) {
a += _.second * _.second;
}
i64 g = gcd(a, b);
a /= g;
b /= g;
cout << a << "/" << b << '\n';
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t = 1;
/*cin >> t;*/
while (t--) {
solve();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |