先说一下下文会用到的定义或称呼的意思：
-
称单位分形为题目给出的 \(1\) 级分形。
-
称一种分形左右联通，则说明将两个这种分形左右放在一起时，至少有一个连通块是跨越这两个分形的。
设一种分形的左右联通个数 \(side_0\) 表示，当两个这种分形左右放在一起时，所贡献的连通块个数，即有多少个连通块是跨越左右两个分形的。显然，当一种分形左右不连通时，\(side_0=0\)。
设一种分形的 \(tot_0\) 表示有多少组黑色单元格是左右相邻的。
比如下图中，这个分形是左右联通的，且 \(side_0=2\)，\(tot_0=9\)。
-
同理定义：一种分形的上下联通个数 \(side_1\) 和 \(tot_1\)。
-
设单位分形中的黑色单元格数为 \(cnt\)，如上面那张图的 \(cnt=16\)。
看到 \(k\leq10^{18}\) 容易想到这题是结论或者快速幂，想了一会发现了以下的两个结论：
-
如果单位分形的 \(side_0\) 或 \(side_1\) 都大于 \(0\)，即单位分形上下和左右都联通，那么 \(k\) 级的联通块数肯定是 \(1\)。
-
如果单位分形的 \(side_0\) 或 \(side_1\) 都大于 \(0\)，即单位分形上下和左右都不联通，那么 \(k\) 级的联通块数肯定是 \(cnt^{k-1}\)。
那么剩下的情况只有单位分形左右联通或者上下联通了。
这两种情况是类似的，现在只拿左右联通的情况来讨论：
考虑设计 \(dp\)，然后用矩阵快速幂来优化。
设 \(ans_i\) 表示 \(i\) 级分形时的答案，\(s_i\) 表示 \(i\) 级分形的 \(side_0\)，\(uside\) 表示单位分形的 \(side_0\)。
容易得到状态转移方程：
\[\begin{aligned} ans_i&=\underbrace{cnt\times ans_{i-1}}_{\text{上一级分形复制 $k$ 遍}}-\underbrace{tot\times s_{i-1}}_{\text{减去多出来的连通块个数}}\\ s_i&=s_{i-1}\times uside \end{aligned} \]更详细的解释自己画个图就好了。
然后就可以用 \(ans_1\)、\(s_1\) 设计初始矩阵，用 \(cnt\)、\(tot\)、\(uside\) 设计转移矩阵，最后矩阵快速幂得到 \(ans_k\)。
由于矩阵的大小是常数级别的，所以总时间复杂度 \(O(\log k)\)。
代码如下：
#include<bits/stdc++.h>
#define N 1010
#define ll long long
#define mod 1000000007
using namespace std;
struct Matrix
{
ll a[3][3];
Matrix(){memset(a,0,sizeof(a));}
void init(){a[1][1]=a[2][2]=1;}
}st,trans;
Matrix operator * (Matrix a,Matrix b)
{
Matrix c;
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
for(int k=1;k<=2;k++)
c.a[i][j]=((c.a[i][j]+a.a[i][k]*b.a[k][j])%mod+mod)%mod;
return c;
}
Matrix poww(Matrix a,ll b)
{
Matrix ans;
ans.init();
while(b)
{
if(b&1) ans=ans*a;
a=a*a;
b>>=1;
}
return ans;
}
int n,m;
int cnt,tot[2],side[2];//0左右相连，1上下相连
char s[N][N];
bool tag;
ll k;
ll fastpow(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
int main()
{
scanf("%d%d%lld",&n,&m,&k);
for(int i=1;i<=n;i++)
scanf("%s",s[i]+1);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(s[i][j]=='#')
{
cnt++;
if(j>1) tot[0]+=(s[i][j-1]=='#');
if(i>1) tot[1]+=(s[i-1][j]=='#');
}
}
}
for(int i=1;i<=n;i++) side[0]+=(s[i][1]=='#'&&s[i][m]=='#');
for(int i=1;i<=m;i++) side[1]+=(s[1][i]=='#'&&s[n][i]=='#');
if(side[0]&&side[1])
{
puts("1");
return 0;
}
if(!side[0]&&!side[1])
{
printf("%lld\n",fastpow(cnt,k-1));
return 0;
}
tag=side[1];
st.a[1][1]=1;
st.a[1][2]=1;
trans.a[1][1]=cnt;
trans.a[2][1]=-tot[tag];
trans.a[2][2]=side[tag];
Matrix ans=st*poww(trans,k-1);
printf("%lld\n",ans.a[1][1]);
return 0;
}
/*
....#....
...###...
...#.#...
.#..#..#.
#########
#.##.##.#
.#.....#.
###...###
#.#...#.#
*/