#P12903. [AGC003F] Fraction of Fractal

    ID: 12088 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-自相似递归结构缩点线性递推矩阵快速幂快速幂

[AGC003F] Fraction of Fractal

题目描述

高桥君从妈妈那里得到了一张网格。这张网格由 HH 行 WW 列的格子组成,每个格子被涂成黑色或白色。所有黑色格子在纵横方向上是连通的。

第 ii 行第 jj 列 (1≤i≤H, 1≤j≤W)(1 \leq i \leq H,\ 1 \leq j \leq W) 的格子的信息由字符 sijs_{ij} 表示,sijs_{ij} 为 # 时表示该格子为黑色,为 . 时表示该格子为白色。至少有一个格子是黑色。

“等级 00 的分形”是指仅包含一个黑色格子的 1×11 \times 1 网格。“等级 k+1k+1 的分形”是指,将等级 kk 的分形分别放置在妈妈给的网格中所有黑色格子对应的位置上,白色格子对应的位置用白色格子填充而成。

给定妈妈给的网格信息和整数 KK,请你求出等级 KK 的分形中由黑色格子组成的连通分量的个数,并对 109+710^9+7 取模输出。

输入格式

输入以以下格式从标准输入读入。

HH WW KK
s11…s1Ws_{11}\ldots s_{1W}
⋮\vdots
sH1…sHWs_{H1}\ldots s_{HW}

输出格式

输出等级 KK 的分形中黑色格子组成的连通分量的个数,对 109+710^9+7 取模。

输入输出样例 #1

输入 #1

3 3 3
.#.
###
#.#

输出 #1

20

输入输出样例 #2

输入 #2

3 3 3
###
#.#
###

输出 #2

1

输入输出样例 #3

输入 #3

11 15 1000000000000000000
.....#.........
....###........
....####.......
...######......
...#######.....
..##.###.##....
..##########...
.###.....####..
.####...######.
###############
#.##..##..##..#

输出 #3

301811921

说明/提示

限制条件

  • 1≤H,W≤10001 \leq H, W \leq 1000
  • 0≤K≤10180 \leq K \leq 10^{18}
  • sijs_{ij} 只可能是 # 或 .。
  • 所有 # 格子在纵横方向上是连通的。
  • 至少存在一个 # 格子。

样例解释 1

根据本输入样例构造出的分形如下。黑色格子的连通分量数为 2020,因此输出 2020。

.............#.............
............###............
............#.#............
..........#..#..#..........
.........#########.........
.........#.##.##.#.........
..........#.....#..........
.........###...###.........
.........#.#...#.#.........
....#........#........#....
...###......###......###...
...#.#......#.#......#.#...
.#..#..#..#..#..#..#..#..#.
###########################
#.##.##.##.##.##.##.##.##.#
.#.....#..#.....#..#.....#.
###...######...######...###
#.#...#.##.#...#.##.#...#.#
....#.................#....
...###...............###...
...#.#...............#.#...
.#..#..#...........#..#..#.
#########.........#########
#.##.##.#.........#.##.##.#
.#.....#...........#.....#.
###...###.........###...###
#.#...#.#.........#.#...#.#

由 ChatGPT 4.1 翻译