[AGC003]F - Fraction of Fractal

发表于 | 分类于

Time limit : 2sec / Memory limit : 256MB

Problem Statement

Snuke got a grid from his mother, as a birthday present. The grid has $H$ rows and $W$ columns. Each cell is painted black or white. All black cells are $4$-connected, that is, it is possible to traverse from any black cell to any other black cell by just visiting black cells, where it is only allowed to move horizontally or vertically.

The color of the cell at the $i$-th row and $j$-th column ($1≦i≦H,1≦j≦W)$ is represented by a character $s{ij}$. If $s{ij}$ is #, the cell is painted black. If $s_{ij}$ is ., the cell is painted white. At least one cell is painted black.

We will define fractals as follows. The fractal of level $0$ is a $1×1$ grid with a black cell. The fractal of level $k+1$ is obtained by arranging smaller grids in $H$ rows and $W $columns, following the pattern of the Snuke’s grid. At a position that corresponds to a black cell in the Snuke’s grid, a copy of the fractal of level $k$ is placed. At a position that corresponds to a white cell in the Snuke’s grid, a grid whose cells are all white, with the same dimensions as the fractal of level $k$, is placed.

You are given the description of the Snuke’s grid, and an integer $K$. Find the number of connected components of black cells in the fractal of level $K$, modulo $10^9+7$.

Constraints

  • $1≦H,W≦1000$
  • $0≦K≦1018$
  • Each $s_{ij}$ is either # or ..
  • All black cells in the given grid are 4-connected.
  • There is at least one black cell in the given grid.

Input

The input is given from Standard Input in the following format:

$H W K$
$s{11}..s{1W}$
:
$s{H1}..s{HW}$

Output

Print the number of connected components of black cells in the fractal of level $K$, modulo $10^9+7$.

Sample Input 1

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

Sample Output 1

20

Sample Input 2

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

sample output 2

301811921

题意

把当前的整图当做当前图的#，不断扩大，循环k次
求最后图的联通块个数

分析

显然上下左右都不连通或上下左右都联通的直接算答案
只上下或只左右联通视为一种情况
设f[x]为边缘能联通的个数
g[x]为图内已经消掉的联通线个数
二者的dp方程很好推，而且可以用矩阵快速幂优化
最后总数-消掉联通线个数就是答案

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
const ll mod=1e9 +7;
int n,m;
ll K,xx,yy,a,s;
int mp[1010][1010];
ll aa[3][3],bb[3][3],ss[3][3];
bool bx,by;
ll power(ll x,ll k)
{
	ll sss=1;
	while (k)
	{
		if (k%2) sss=sss*x%mod;
		x=x*x%mod;
		k/=2;
	}
	return sss;
}
void init()
{
	aa[1][1]=ss[1][1]=s;
	aa[1][2]=ss[1][2]=1;
	aa[2][1]=ss[2][1]=0;
	aa[2][2]=ss[2][2]=a;
}
void square_mul()
{
	for (int i=1;i<=2;++i)
		for (int j=1;j<=2;++j)
		{
			bb[i][j]=0;
			for (int k=1;k<=2;++k)
				bb[i][j]=(bb[i][j]+aa[i][k]*ss[k][j]%mod)%mod;
		}
	for (int i=1;i<=2;++i)
		for (int j=1;j<=2;++j)
		ss[i][j]=bb[i][j];
}
void square_self()
{
	for (int i=1;i<=2;++i)
		for (int j=1;j<=2;++j)
		{
			bb[i][j]=0;
			for (int k=1;k<=2;++k)
				bb[i][j]=(bb[i][j]+aa[i][k]*aa[k][j]%mod)%mod;
		}
	for (int i=1;i<=2;++i)
		for (int j=1;j<=2;++j)
		aa[i][j]=bb[i][j];
}
void square_power(ll k)
{
	--k;
	while (k)
	{
		if (k%2) square_mul();
		square_self();
		k/=2;
	}
}
int main()
{
	scanf("%d%d%lld",&n,&m,&K);
	char ch[1010];
	for (int i=1;i<=n;++i)
	{
		scanf("%s",ch+1);
		for (int j=1;j<=m;++j)
			if (ch[j]=='#') 
				mp[i][j]=1,++s;
	}
	for (int i=1;i<=n;++i)
		if (mp[i][1]&&mp[i][m])
			++a,bx=1;
	for (int i=1;i<=m;++i)
		if (mp[1][i]&&mp[n][i])
			++a,by=1;
	if ((bx==1 && by==1) || K==1)
	{
		printf("1\n");
		return 0;
	}
	if (bx==0 && by==0)
	{
		printf("%lld\n",power(s,K-1));
		return 0;
	}
	if (by==1)
	{
		int mmp[1010][1010];
		swap(mmp,mp);
		swap(n,m);
		for (int i=1;i<=n;++i)
			for (int j=1;j<=m;++j)
				mp[i][j]=mmp[j][i];
	}
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j)
			if (mp[i][j]==1&&mp[i][j+1]==1)
				++xx;
	yy=xx*a;
	if (K==2)
	{
		printf("%lld\n",s-xx);
		return 0;
	}
	init();
	square_power(K-2);
	xx=(xx*ss[1][1]%mod+yy*ss[1][2]%mod)%mod;
 
	printf("%lld\n",( (power(s,K-1)-xx)%mod + mod)%mod);
	return 0;
}
--------------------------