#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <map>
#include <algorithm>
// Use long long for hash values and counts to avoid overflow.
using ll = long long;
// Constants for polynomial rolling hash. Using two different pairs of
// prime bases and moduli helps prevent hash collisions.
const ll P1 = 31, M1 = 1e9 + 7;
const ll P2 = 37, M2 = 1e9 + 9;
// Global vectors to store precomputed powers of the bases P1 and P2.
std::vector<ll> p_pow1, p_pow2;
// Grid dimensions, word length K, and the grid itself.
int R, C;
ll K;
std::vector<std::string> grid;
// --- Utility Functions ---
// Helper for modular addition.
ll add(ll a, ll b, ll m) { return (a + b) % m; }
// Helper for modular multiplication.
ll mul(ll a, ll b, ll m) { return (a * b) % m; }
// Helper for modular subtraction that handles negative results correctly.
ll sub(ll a, ll b, ll m) { return (a - b % m + m) % m; }
// Standard library functions for GCD and LCM.
ll gcd(ll a, ll b) {
return std::gcd(a, b);
}
ll lcm(ll a, ll b) {
if (a == 0 || b == 0) return 0;
// To prevent overflow, divide before multiplying.
return (a / gcd(a, b)) * b;
}
/**
* @brief Retrieves the character from the infinitely repeating grid.
* @param r The target row.
* @param c The target column.
* @return The character at the specified coordinates.
*/
char get_char(ll r, ll c) {
// The modulo operator in C++ can return negative results.
// Adding the dimension before the second modulo ensures the result is always positive.
ll final_r = (r % R + R) % R;
ll final_c = (c % C + C) % C;
return grid[final_r][final_c];
}
/**
* @brief Precomputes the powers of the hash bases up to a maximum length.
* @param max_len The maximum length for which to compute powers.
*/
void precompute_powers(ll max_len) {
p_pow1.resize(max_len + 1);
p_pow2.resize(max_len + 1);
p_pow1[0] = p_pow2[0] = 1;
for (int i = 1; i <= max_len; ++i) {
p_pow1[i] = mul(p_pow1[i - 1], P1, M1);
p_pow2[i] = mul(p_pow2[i - 1], P2, M2);
}
}
// --- Main Logic ---
void solve() {
// Read input dimensions and the grid pattern.
std::cin >> R >> C >> K;
grid.resize(R);
for (int i = 0; i < R; ++i) {
std::cin >> grid[i];
}
// Any word is a periodic sequence. The maximum possible period is lcm(R, C).
// Words longer than this length don't help distinguish unique sequences.
// So, we can cap K at lcm(R, C).
ll eff_K = K;
ll max_period = lcm(R, C);
if (max_period > 0) {
eff_K = std::min(K, max_period);
}
// If effective length is 0, all words are empty and thus identical.
if (eff_K == 0) {
std::cout << "1/1\n";
return;
}
precompute_powers(eff_K);
// Map to store counts of each unique hash pair.
std::map<std::pair<ll, ll>, ll> hash_counts;
// Define the 8 directions of travel (row_change, col_change).
int dr[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dc[] = {-1, 0, 1, -1, 1, -1, 0, 1};
// Iterate through each of the 8 directions.
for (int d = 0; d < 8; ++d) {
int current_dr = dr[d];
int current_dc = dc[d];
// This hash table stores computed hashes for the current direction.
std::vector<std::vector<std::pair<ll, ll>>> dir_hashes(R, std::vector<std::pair<ll, ll>>(C));
// Determine the grid traversal order. To use the rolling hash update,
// we must compute the hash for a cell (r,c) AFTER its predecessor
// (r-dr, c-dc) has been computed. This loop setup ensures that.
int r_start = (current_dr >= 0) ? 0 : R - 1;
int r_end = (current_dr >= 0) ? R : -1;
int r_step = (current_dr >= 0) ? 1 : -1;
int c_start = (current_dc >= 0) ? 0 : C - 1;
int c_end = (current_dc >= 0) ? C : -1;
int c_step = (current_dc >= 0) ? 1 : -1;
for (int r = r_start; r != r_end; r += r_step) {
for (int c = c_start; c != c_end; c += c_step) {
// A cell is on the "perimeter" for this direction if it's in the
// first row or column of our traversal. For these cells, we can't
// roll from a previous hash, so we compute it from scratch.
bool is_perimeter = (r == r_start) || (c == c_start);
ll h1, h2;
if (is_perimeter) {
// Full O(eff_K) hash calculation for perimeter cells.
h1 = 0;
h2 = 0;
for (int k = 0; k < eff_K; ++k) {
char ch = get_char(r + (ll)k * current_dr, c + (ll)k * current_dc);
h1 = add(mul(h1, P1, M1), ch - 'a' + 1, M1);
h2 = add(mul(h2, P2, M2), ch - 'a' + 1, M2);
}
} else {
// O(1) rolling hash update for interior cells.
int prev_r = (r - current_dr + R) % R;
int prev_c = (c - current_dc + C) % C;
ll prev_h1 = dir_hashes[prev_r][prev_c].first;
ll prev_h2 = dir_hashes[prev_r][prev_c].second;
char first_char_of_prev = get_char(prev_r, prev_c);
char last_char_of_curr = get_char(r + (ll)(eff_K - 1) * current_dr, c + (ll)(eff_K - 1) * current_dc);
// The rolling hash formula: H_new = (H_old - val(first) * P^(K-1)) * P + val(last)
ll term1_h1 = mul(first_char_of_prev - 'a' + 1, p_pow1[eff_K - 1], M1);
h1 = sub(prev_h1, term1_h1, M1);
h1 = mul(h1, P1, M1);
h1 = add(h1, last_char_of_curr - 'a' + 1, M1);
ll term1_h2 = mul(first_char_of_prev - 'a' + 1, p_pow2[eff_K - 1], M2);
h2 = sub(prev_h2, term1_h2, M2);
h2 = mul(h2, P2, M2);
h2 = add(h2, last_char_of_curr - 'a' + 1, M2);
}
// Store the computed hash and increment its count in the global map.
dir_hashes[r][c] = {h1, h2};
hash_counts[{h1, h2}]++;
}
}
}
// Calculate the final probability.
// The probability of two independent events (picking the same word) is the sum
// of the squares of the individual probabilities for each unique word.
// P(same) = sum over all unique words w [ (count(w)/total)^2 ]
// This simplifies to (sum of count(w)^2) / total^2
ll total_strings = (ll)R * C * 8;
ll numerator = 0;
for (auto const& [key, val] : hash_counts) {
numerator += val * val;
}
ll denominator = total_strings * total_strings;
// Simplify the fraction by dividing by the greatest common divisor.
ll common_divisor = gcd(numerator, denominator);
std::cout << numerator / common_divisor << "/" << denominator / common_divisor << "\n";
}
int main() {
// Fast I/O
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
solve();
return 0;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
