// package ojuz;
import java.io.*;
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
import java.util.function.ToLongBiFunction;
public class osmosmjerka {
public static final long mod = (1L << 61) - 1, b1 = ThreadLocalRandom.current().nextLong(mod), b2 = ThreadLocalRandom.current().nextLong(mod);
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] first = reader.readLine().split(" ");
int n = Integer.parseInt(first[0]), m = Integer.parseInt(first[1]), k = Integer.parseInt(first[2]);
char[][] grid = new char[n][];
for (int i = 0; i < n; i++) grid[i] = reader.readLine().toCharArray();
int gcd = gcd(n, m);
int lcm = n / gcd * m;
k = Math.min(k, lcm);
// using one base worst case is about (8 * 500 ** 6) / mod -> about 1 in 20
// using two bases just in case
long[] pow1 = new long[lcm + 1], pow2 = new long[lcm + 1];
pow1[0] = pow2[0] = 1;
for (int i = 1; i <= lcm; i++) {
pow1[i] = mult(pow1[i - 1], b1);
pow2[i] = mult(pow2[i - 1], b2);
}
long inv1 = pow(1 - b1 + mod, mod - 2);
long inv2 = pow(1 - b2 + mod, mod - 2);
Functional subhash = (start, len, bound, hash, pow) -> (hash[start + len] - mult(pow[len], hash[start]) + mod) % mod;
Functional get = (start, len, bound, hash, pow) -> {
if (start + len > bound) {
int last = bound - start;
return (mult(pow[len - last], subhash.hash(start, last, bound, hash, pow)) + subhash.hash(0, len - last, bound, hash, pow)) % mod;
} else return subhash.hash(start, len, bound, hash, pow);
};
Map<Hash, Integer> freq = new HashMap<>();
int[][] deltas = {{1, 1}, {n - 1, 1}, {n - 1, m - 1}, {1, m - 1}};
// im worried about memory limit(lie) so dont use concat for circular arrays
long[] hash1 = new long[lcm + 1];
long[] hash2 = new long[lcm + 1];
for (int t = 0; t < 4; t++) {
for (int i = 0; i < gcd; i++) {
int[] pos = {0, i};
for (int j = 0; j < lcm; j++) {
hash1[j + 1] = (mult(hash1[j], b1) + grid[pos[0]][pos[1]]) % mod;
hash2[j + 1] = (mult(hash2[j], b2) + grid[pos[0]][pos[1]]) % mod;
pos[0] = (pos[0] + deltas[t][0]) % n;
pos[1] = (pos[1] + deltas[t][1]) % m;
}
for (int j = 0; j < lcm; j++) freq.merge(new Hash(get.hash(j, k, lcm, hash1, pow1), get.hash(j, k, lcm, hash2, pow2)), 1, Integer::sum);
}
}
int floor = k / m;
int remain = k % m;
for (int delta = -1; delta < 2; delta += 2) {
for (int i = 0; i < n; i++) {
int[] pos = {i, 0};
for (int j = 0; j < m; j++) {
pos[1] = (pos[1] + m + delta) % m;
hash1[j + 1] = (mult(hash1[j], b1) + grid[pos[0]][pos[1]]) % mod;
hash2[j + 1] = (mult(hash2[j], b2) + grid[pos[0]][pos[1]]) % mod;
}
for (int j = 0; j < m; j++) {
long sum1 = get.hash(j, m, m, hash1, pow1);
sum1 = mult(sum1, 1 - pow1[floor] + mod);
sum1 = mult(sum1, inv1);
sum1 = mult(sum1, pow1[remain]);
sum1 = (sum1 + get.hash(j, remain, m, hash1, pow1));
long sum2 = get.hash(j, m, m, hash2, pow2);
sum2 = mult(sum2, 1 - pow2[floor] + mod);
sum2 = mult(sum2, inv2);
sum2 = mult(sum2, pow2[remain]);
sum2 = (sum2 + get.hash(j, remain, m, hash2, pow2));
freq.merge(new Hash(sum1, sum2), 1, Integer::sum);
}
}
}
floor = k / n;
remain = k % n;
for (int delta = -1; delta < 2; delta += 2) {
for (int i = 0; i < m; i++) {
int[] pos = {0, i};
for (int j = 0; j < n; j++) {
pos[0] = (pos[0] + n + delta) % n;
hash1[j + 1] = (mult(hash1[j], b1) + grid[pos[0]][pos[1]]) % mod;
hash2[j + 1] = (mult(hash2[j], b2) + grid[pos[0]][pos[1]]) % mod;
}
for (int j = 0; j < n; j++) {
long sum1 = get.hash(j, n, n, hash1, pow1);
sum1 = mult(sum1, 1 - pow1[floor] + mod);
sum1 = mult(sum1, inv1);
sum1 = mult(sum1, pow1[remain]);
sum1 = (sum1 + get.hash(j, remain, n, hash1, pow1));
long sum2 = get.hash(j, n, n, hash2, pow2);
sum2 = mult(sum2, 1 - pow2[floor] + mod);
sum2 = mult(sum2, inv2);
sum2 = mult(sum2, pow2[remain]);
sum2 = (sum2 + get.hash(j, remain, n, hash2, pow2));
freq.merge(new Hash(sum1, sum2), 1, Integer::sum);
}
}
}
long numer = 0;
for (int i : freq.values()) numer += (long) i * i;
long denom = 64L * n * m * n * m;
long divide = gcd(numer, denom);
System.out.println((numer / divide) + "/" + (denom / divide));
}
public static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
public static long gcd(long a, long b) {
return b == 0 ? a : gcd(b, a % b);
}
public static long mult(long a, long b) {
long low = a * b;
return ((low & mod) + ((low >>> 61) | (Math.multiplyHigh(a, b) << 3))) % mod;
}
public static long pow(long a, long b) {
long result = 1;
while (b > 0) {
if (b % 2 == 1) result = mult(result, a);
a = mult(a, a);
b /= 2;
}
return result;
}
static class Hash {
public final long hi, lo;
public Hash(long hi, long lo) {
this.hi = hi;
this.lo = lo;
}
@Override
public boolean equals(Object o) {
if (o instanceof Hash) {
Hash h = (Hash) o;
return h.hi == hi && h.lo == lo;
}
return false;
}
@Override
public int hashCode() {
// hi and lo should all be random since theyre hashes themselve
return Long.hashCode(hi) ^ Long.hashCode(lo);
}
@Override
public String toString() {
return "Hash{" +
"hi=" + hi +
", lo=" + lo +
'}';
}
}
@FunctionalInterface
interface Functional {
long hash(int start, int len, int bound, long[] hash, long[] pow);
}
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
