首页 题解

# Description

Luogu传送门

说实话我感觉这题说的还挺迷的，看了好久题意才看懂 QwQ

这里稍微解释一下吧，就是初始的时候给你一个字符矩阵，上面有黑白两种格子，保证黑格子四联通。

然后你需要扩展这个字符矩阵。

简单来说，假设当前矩阵为 kk 级矩阵，要扩展成 k+1k + 1 级矩阵，我们把黑格子变成当前字符矩阵（kk 级矩阵）的样子，白格子就变成当前字符矩阵大小的全白格子。

这是样例一的 2 级分形：

1
2
3
4
5
6
7
8
9
10
11
...|.#.|...
...|###|...
...|#.#|...
-----------
.#.|.#.|.#.
###|###|###
#.#|#.#|#.#
-----------
.#.|...|.#.
###|...|###
#.#|...|#.#

最后计算 kk 级分形的黑色格子连通块个数

# Solution

我们要考虑一下每次扩展之后会多出来哪些黑色连通块，又有哪些黑色连通块会彼此连在一起。

分类讨论：

  • 扩展时上下左右都会相连，答案显然就是 1。

  • 扩展时上下左右都不会相连，答案就是 cntk−1cnt^{k - 1}。

  • 上下或左右相连，我们以样例一为例好好分析一下（图见上）。

样例一属于左右会相连，上下不相连的情况。

连通块个数从 1 变为了 4。

简单推一下规律，不难发现：

连通块个数=原图黑色格子个数−左右相邻都是黑色格子的对数连通块个数 = 原图黑色格子个数 - 左右相邻都是黑色格子的对数

然后我们再扩展一次，发现这个结论还是对的！

那么这个东西如何计算呢？

设 aka_k 表示黑色格子个数，bkb_k 表示总的相邻黑点对数，ckc_k 表示拼接时两个相邻的大块之间形成的黑色点对数。

ak=ak−1×ak−1bk=bk−1×ak−1+bk−1×ck−1ck=ck−1×ck−1a_k = a_{k - 1} \times a_{k - 1}\\ b_k = b_{k - 1} \times a_{k - 1} + b_{k - 1} \times c_{k - 1}\\ c_k = c_{k - 1} \times c_{k - 1}

第一条式子和第三条式子应该不难理解吧。

第二条：原本有的相邻黑点对数在所有黑点扩展出的图形中都会出现一遍（bk−1×ak−1b_{k - 1} \times a_{k - 1}），然后再加上边界上出现的次数（bk−1×ck−1b_{k - 1} \times c_{k - 1} 这个可以手推一下）。

于是我们就得到了递推式子。

不难发现，这东西可以矩阵快速幂优化一下。矩阵长这个样子：

∣ab0c∣\begin{vmatrix}a&b\\0&c\end{vmatrix}

快速幂计算它的 k−1k - 1 次方即可。

# Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 1010;
const int mod = 1e9 + 7;
int n, m;
ll k;
char t[N];
int s[N][N];

inline int qpow(int a, ll b){
    int res = 1;
    while(b){
        if(b & 1) res = 1ll * res * a % mod;
        a = 1ll * a * a % mod, b >>= 1;
    }
    return res;
}

/*
|a,b|
|0,c|
*/
struct matrix{
    int a, b, c;
    
    matrix(int _a = 0, int _b = 0, int _c = 0) {a = _a, b = _b, c = _c;}

    friend matrix operator * (matrix A, matrix B){
        matrix C;
        C.a = 1ll * A.a * B.a % mod;
        C.b = (1ll * A.a * B.b + 1ll * A.b * B.c) % mod;
        C.c = 1ll * A.c * B.c % mod;
        return C;
    }

    matrix operator ^ (ll p) const{
        matrix r(1, 0, 1), B(a, b, c);
        for(; p; B = B * B, p >>= 1)
            if(p & 1) r = r * B;
        return r;
    }
}f;

int main(){
    scanf("%d%d%lld", &n, &m, &k);
    if(!k) return puts("1"), 0;
    for(int i = 1; i <= n; ++i){
        scanf("%s", t + 1);
        for(int j = 1; j <= m; ++j)
            s[i][j] = (t[j] == '#');
    }
    int cnt = 0, ud = 0, lr = 0, UD = 0, LR = 0;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j){
            cnt += s[i][j];
            if(i == 1) UD += s[1][j] & s[n][j];
            else ud += s[i][j] & s[i - 1][j];
            if(j == 1) LR += s[i][1] & s[i][m];
            else lr += s[i][j] & s[i][j - 1];
        }
    if(!UD && !LR) printf("%d\n", qpow(cnt, k - 1));
    else if(UD && LR) puts("1");
    else{
        if(UD) f = matrix(cnt, ud, UD) ^ (k - 1);
        else f = matrix(cnt, lr, LR) ^ (k - 1);
        printf("%d\n", (f.a - f.b + mod) % mod);
    }
    return 0;
}