| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1291042 | vk3601h | Osmosmjerka (COCI17_osmosmjerka) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
// 使用 64 位哈希（自然溢出，相当于 mod 2^64）
using ull = unsigned long long;
using ll = long long;
// 8 个方向
const int DX[8] = {-1, 1, 0, 0, -1, 1, -1, 1};
const int DY[8] = { 0, 0,-1, 1, -1, -1, 1, 1};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int M, N;
long long K;
if (!(cin >> M >> N >> K)) return 0;
vector<string> g(M);
for (int i = 0; i < M; ++i) cin >> g[i];
const ull P = 911382323ull; // 哈希基数（随便选个大的奇数）
int MN = M * N;
// 预处理 P^i，i 最大用到 MN（周期长度不会超过 MN）
vector<ull> powP(MN + 1);
powP[0] = 1;
for (int i = 1; i <= MN; ++i) {
powP[i] = powP[i - 1] * P;
}
vector<ull> all_hashes;
all_hashes.reserve(8ll * MN);
// 遍历 8 个方向
for (int d = 0; d < 8; ++d) {
int dx = DX[d], dy = DY[d];
// 计算这个方向在 MxN 环面上的“步长周期” L_dir：
// 找最小 t > 0 使得 t*dx ≡ 0 (mod M) 且 t*dy ≡ 0 (mod N)
// 这个 t 就是沿该方向走回原位需要的步数，即每个轨道（cycle）的长度
auto gcd = [](ll a, ll b) {
while (b) { ll t = a % b; a = b; b = t; }
return a;
};
auto lcm = [&](ll a, ll b) {
return a / gcd(a, b) * b;
};
ll a, b;
if (dx == 0) a = 1;
else a = M / gcd(std::llabs(dx), (ll)M);
if (dy == 0) b = 1;
else b = N / gcd(std::llabs(dy), (ll)N);
ll L_dir = lcm(a, b); // 每条 cycle 的长度
vector<char> visited(MN, 0);
// 在这个方向上，把所有格子分解成若干条“环上的一维周期串”
for (int start = 0; start < MN; ++start) {
if (visited[start]) continue;
// 收集当前 cycle 上的所有格子 id
vector<int> nodes;
nodes.reserve((int)L_dir);
int x = start / N;
int y = start % N;
for (int step = 0; step < L_dir; ++step) {
int id = x * N + y;
visited[id] = 1;
nodes.push_back(id);
x += dx; if (x < 0) x += M; else if (x >= M) x -= M;
y += dy; if (y < 0) y += N; else if (y >= N) y -= N;
}
int L = (int)nodes.size(); // 本周期串长度（应等于 L_dir）
// 构造这个周期串 S 的前缀哈希：pref[i] = hash(S[0..i-1])
// 哈希定义：h = (((c0)*P + c1)*P + ... )*P + c_{L-1}
vector<ull> pref(L + 1);
pref[0] = 0;
for (int i = 0; i < L; ++i) {
int id = nodes[i];
char ch = g[id / N][id % N];
ull v = (ull)(ch - 'a' + 1);
pref[i + 1] = pref[i] * P + v;
}
// 整个周期串 S 的哈希和长度对应的 P^len
ull H_S = pref[L];
ull powL = powP[L]; // P^L
// 预处理 S^(2^k) 的哈希与对应的 P^{len}，用于快速幂
vector<pair<ull, ull>> basePow; // (hash, P^{len})
vector<ll> lenPow; // len = L * 2^k
basePow.reserve(64);
lenPow.reserve(64);
basePow.push_back({H_S, powL});
lenPow.push_back(L);
while ((ll)lenPow.back() * 2 <= K) {
ull h = basePow.back().first;
ull p = basePow.back().second;
ll len = lenPow.back();
// S^{2*len} = (S^len)(S^len)
ull h2 = h * p + h; // hash(A+A) = hash(A)*P^{|A|} + hash(A)
ull p2 = p * p; // P^{2*len} = (P^{len})^2
ll l2 = len * 2;
basePow.push_back({h2, p2});
lenPow.push_back(l2);
}
// 快速求 S^t 的 (hash, P^{len})，使用二进制分解
auto pow_repeat = [&](ll t) -> pair<ull, ull> {
ull h_res = 0; // 空串 hash = 0
ull p_res = 1; // 空串 P^{len} = 1 (len=0)
int bit = 0;
while (t > 0) {
if (t & 1) {
ull h1 = h_res, p1 = p_res;
ull h2 = basePow[bit].first;
ull p2 = basePow[bit].second;
// 拼接: res = res + block
// hash(res+block) = h1 * P^{len(block)} + h2
h_res = h1 * p2 + h2;
p_res = p1 * p2;
}
t >>= 1;
++bit;
}
return {h_res, p_res};
};
// 对于这个周期上的每一个起点 p，构造长度为 K 的单词的哈希
for (int p = 0; p < L; ++p) {
ll rem = K; // 剩余要取的长度
ull h_cur = 0; // 当前已拼单词的哈希
ull p_cur = 1; // 当前单词长度对应的 P^{len}
// 1) 先取从位置 p 到周期末尾的那一段（最多 L-p，不能超过 rem）
ll len1 = min(rem, (ll)L - p);
if (len1 > 0) {
// 子串 S[p .. p+len1-1] 的哈希：
// hash = pref[p+len1] - pref[p]*P^{len1}
ull hFirst = pref[p + len1] - pref[p] * powP[len1];
ull pFirst = powP[len1]; // P^{len1}
// 拼接：cur = cur + first
ull h1 = h_cur, pp1 = p_cur;
ull h2 = hFirst, pp2 = pFirst;
h_cur = h1 * pp2 + h2;
p_cur = pp1 * pp2;
rem -= len1;
}
if (rem > 0) {
// 2) 中间部分是若干个完整的周期串 S
ll t_full = rem / L; // 完整周期串个数
ll lenLast = rem % L; // 最后剩余的一小段
if (t_full > 0) {
auto mid = pow_repeat(t_full); // (hash(S^t), P^{lenMid})
ull h1 = h_cur, pp1 = p_cur;
ull h2 = mid.first, pp2 = mid.second;
h_cur = h1 * pp2 + h2;
p_cur = pp1 * pp2;
}
// 3) 最后再取从 S[0..lenLast-1] 的那一段
if (lenLast > 0) {
ull hLast = pref[lenLast]; // 从 0 开始的子串
ull pLast = powP[lenLast];
ull h1 = h_cur, pp1 = p_cur;
ull h2 = hLast, pp2 = pLast;
h_cur = h1 * pp2 + h2;
p_cur = pp1 * pp2;
}
}
all_hashes.push_back(h_cur);
}
}
}
// 统计每个单词出现次数 X，累加 X^2
sort(all_hashes.begin(), all_hashes.end());
ll num = 0;
for (size_t i = 0; i < all_hashes.size(); ) {
size_t j = i + 1;
while (j < all_hashes.size() && all_hashes[j] == all_hashes[i]) ++j;
ll cnt = (ll)(j - i);
num += cnt * cnt;
i = j;
}
ll T = 8ll * M * N; // 所有起点+方向总数
ll den = T * T; // T^2
ll g = std::gcd(num, den);
num /= g;
den /= g;
cout << num << "/" << den << "\n";
return 0;
}