Submission #848046


Source Code Expand

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskF solver = new TaskF();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskF {
        static final long MODULO = (long) (1e9 + 7);

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int height = in.nextInt();
            int width = in.nextInt();
            long k = in.nextLong();
            if (k <= 1) {
                out.println(1);
                return;
            }
            String[] field = new String[height];
            for (int r = 0; r < height; ++r) {
                field[r] = in.next();
            }
            boolean horz = false;
            boolean vert = false;
            for (int r = 0; r < height; ++r) {
                if (field[r].charAt(0) == '#' && field[r].charAt(width - 1) == '#') {
                    horz = true;
                }
            }
            for (int c = 0; c < width; ++c) {
                if (field[0].charAt(c) == '#' && field[height - 1].charAt(c) == '#') {
                    vert = true;
                }
            }
            if (horz && vert) {
                out.println(1);
                return;
            }
            if (!horz && !vert) {
                long cells = 0;
                for (int r = 0; r < height; ++r) {
                    for (int c = 0; c < width; ++c) {
                        if (field[r].charAt(c) == '#')
                            ++cells;
                    }
                }
                out.println(pow(cells, k - 1));
                return;
            }
            if (!horz) {
                String[] flipped = new String[width];
                for (int c = 0; c < width; ++c) {
                    StringBuilder b = new StringBuilder();
                    for (int r = 0; r < height; ++r) {
                        b.append(field[r].charAt(c));
                    }
                    flipped[c] = b.toString();
                }
                field = flipped;
                int tmp = height;
                height = width;
                width = tmp;
            }
            long[] start = new long[2];
            for (int r = 0; r < height; ++r) {
                for (int c = 0; c < width; ++c)
                    if (field[r].charAt(c) == '#') {
                        if (c > 0 && field[r].charAt(c - 1) == '#')
                            ++start[1];
                        else
                            ++start[0];
                    }
            }
            long[][] a = new long[2][2];
            for (int r = 0; r < height; ++r) {
                for (int c = 0; c < width; ++c)
                    if (field[r].charAt(c) == '#') {
                        if (c > 0) {
                            int have = field[r].charAt(c - 1) == '#' ? 1 : 0;
                            ++a[have][0];
                            ++a[have][1];
                        } else {
                            ++a[0][0];
                            int have = field[r].charAt(width - 1) == '#' ? 1 : 0;
                            ++a[have][1];
                        }
                    }
            }
            long[] fin = mul(pow(a, k - 2), start);
            out.println(fin[0]);
        }

        private long[][] pow(long[][] a, long k) {
            if (k == 0) {
                long[][] res = new long[a.length][a.length];
                for (int i = 0; i < res.length; ++i) {
                    res[i][i] = 1;
                }
                return res;
            }
            if (k % 2 == 0) {
                return pow(mul(a, a), k / 2);
            }
            return mul(a, pow(a, k - 1));
        }

        private long[][] mul(long[][] a, long[][] b) {
            int n = a.length;
            long[][] c = new long[n][n];
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    long s = 0;
                    for (int k = 0; k < n; ++k) {
                        s += a[i][k] * b[k][j];
                    }
                    c[i][j] = s % MODULO;
                }
            }
            return c;
        }

        private long[] mul(long[][] a, long[] b) {
            int n = a.length;
            long[] c = new long[n];
            for (int i = 0; i < n; ++i) {
                long s = 0;
                for (int k = 0; k < n; ++k) {
                    s += a[i][k] * b[k];
                }
                c[i] = s % MODULO;
            }
            return c;
        }

        private long pow(long a, long k) {
            if (k == 0) {
                return 1;
            }
            if (k % 2 == 0) {
                return pow(a * a % MODULO, k / 2);
            }
            return a * pow(a, k - 1) % MODULO;
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }
}

Submission Info

Submission Time
Task F - Fraction of Fractal
User Petr
Language Java8 (OpenJDK 1.8.0)
Score 1700
Code Size 6425 Byte
Status AC
Exec Time 914 ms
Memory 22844 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1700 / 1700
Status
AC × 3
AC × 47
Set Name Test Cases
Sample s1.txt, s2.txt, s3.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt AC 250 ms 13712 KB
02.txt AC 298 ms 12956 KB
03.txt AC 361 ms 22820 KB
04.txt AC 301 ms 13608 KB
05.txt AC 352 ms 22552 KB
06.txt AC 261 ms 13760 KB
07.txt AC 265 ms 12840 KB
08.txt AC 233 ms 12580 KB
09.txt AC 310 ms 13076 KB
10.txt AC 354 ms 22688 KB
11.txt AC 222 ms 12564 KB
12.txt AC 282 ms 13860 KB
13.txt AC 296 ms 14044 KB
14.txt AC 263 ms 13764 KB
15.txt AC 268 ms 12688 KB
16.txt AC 272 ms 13444 KB
17.txt AC 295 ms 13860 KB
18.txt AC 297 ms 13608 KB
19.txt AC 297 ms 13732 KB
20.txt AC 354 ms 22800 KB
21.txt AC 343 ms 22240 KB
22.txt AC 272 ms 13764 KB
23.txt AC 344 ms 22816 KB
24.txt AC 338 ms 22796 KB
25.txt AC 343 ms 22648 KB
26.txt AC 290 ms 13432 KB
27.txt AC 682 ms 22844 KB
28.txt AC 914 ms 13556 KB
29.txt AC 153 ms 8276 KB
30.txt AC 155 ms 8148 KB
31.txt AC 151 ms 8268 KB
32.txt AC 154 ms 8144 KB
33.txt AC 150 ms 8148 KB
34.txt AC 156 ms 8272 KB
35.txt AC 155 ms 8272 KB
36.txt AC 158 ms 8276 KB
37.txt AC 151 ms 8148 KB
38.txt AC 151 ms 8268 KB
39.txt AC 151 ms 8148 KB
40.txt AC 149 ms 8272 KB
41.txt AC 153 ms 8268 KB
42.txt AC 152 ms 8148 KB
43.txt AC 153 ms 8144 KB
44.txt AC 151 ms 8144 KB
s1.txt AC 151 ms 8148 KB
s2.txt AC 154 ms 8144 KB
s3.txt AC 150 ms 8276 KB