Submission #1212385

#TimeUsernameProblemLanguageResultExecution timeMemory
1212385uranium235Osmosmjerka (COCI17_osmosmjerka)Java
160 / 160
927 ms119692 KiB
// 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 timeMemoryGrader output
Fetching results...