Problem
题意：给出(n)行(m)列的01矩阵，一开始所有 (1) 连通，称此为(1)级分形，定义(i)级分形为(i-1)级分形中每个标示为 (1) 的格子中放一个 (i-1) 级分形（结合样例理解），求(k)级分形的连通块数量
Solution
网上好像都是矩阵快速幂的解法，然后一位集训中认识的dalao告诉我还有一种不用矩阵快速幂的解法：
首先发现分形中相接的地方一定是01矩阵某一行的左右端点或某一列的上下端点，我们管这些叫“接口”；在开始前先特判(k=0)或(k=1)
如果一个01矩阵既有上下接口又有左右接口，那么这个图形不管在几级分形下总会只有一个联通块；同样的，如果上下接口和左右接口都没有的话，那么这个图形不管在几级分形下不会相接，即设图形中 (1) 的数量为 (S)，则 (k) 级分形的联通块个数为(S^{k-1})（分形一次联通块个数乘(S)）。现在剩下的情况中两种接口必定存在一个
设 (c) 为接口总数（一对算一个），(S)为01矩阵中 (1) 的数量，(d) 为块内连通个数（若仅有左右接口，则(d)为01矩阵中左右相邻两格都是 (1) 的对数；若仅有上下接口，则(d)为01矩阵中上下相邻两个都是 (1) 的对数）
设 (f_i) 表示 (i) 级分形到 (i+1) 级分形时，(ncdot m)个 (i) 级分形之间连通的个数（因为之间多连通一对，那最终联通块个数减一）
则有
[f_i=egin{cases}
d, & i=1\
f_{i-1}cdot c, & igeq 2
end{cases}]
由于在 (i) 级分形到第 (i+1) 级分形中合并的数量在 (k) 级分形中会被复制 (S^{k-1-i}) 次
所以答案为
[Ans=S^{k-1}-sum_{i=1}^{k-1}f_icdot S^{k-1-i}
]
将 (f_i=dc^{i-1}) 代入，化简得
[Ans=S^{k-1}-sum_{i=1}^{k-1}dc^{i-1}cdot S^{k-1-i}
]
[Ans=S^{k-1}-dcdot c^{-1}cdot S^{k-1}cdot sum_{i=1}^{k-1}c^icdot S^{-i}
]
[Ans=S^{k-1}-dcdot c^{-1}cdot S^{k-1}cdot sum_{i=1}^{k-1}(frac cS)^i
]
[Ans=S^{k-1}-dcdot c^{-1}cdot S^{k-1}cdot frac {frac cS-(frac cS)^k}{1-frac cS}
]
[Ans=S^{k-1}-frac {d(S^{k-1}-c^{k-1})}{S-c}
]
这样就只需要快速幂而非矩阵快速幂了
Code
#include <cstdio>
typedef long long ll;
const int N=1010,p=1e9+7;
char s[N][N];
int n,m,d,c,S,col,row;
ll k;
inline int qm(int x){return x<0?x+p:x;}
template <typename _tp> inline int qpow(int A,_tp B){
int res(1);while(B){
if(B&1)res=1ll*res*A%p;
A=1ll*A*A%p,B>>=1;
}return res;
}
int main(){
scanf("%d%d%lld",&n,&m,&k);
for(int i=1;i<=n;++i){
scanf("%s",s[i]+1);
for(int j=1;j<=m;++j)
if(s[i][j]=='#')++S;
}
for(int i=1;i<=n;++i)if(s[i][1]=='#'&&'#'==s[i][m])++row;
for(int i=1;i<=m;++i)if(s[1][i]=='#'&&'#'==s[n][i])++col;
if(!row&&!col){printf("%d
",qpow(S,k-1));return 0;}
if(!k||(row&&col)){puts("1");return 0;}
if(row)
for(int i=1;i<=n;++i)
for(int j=1;j<m;++j)
d+=(s[i][j]=='#'&&s[i][j+1]=='#');
else
for(int i=1;i<n;++i)
for(int j=1;j<=m;++j)
d+=(s[i][j]=='#'&&s[i+1][j]=='#');
c=row?row:col;
int ans=qm(qpow(S,k-1)-qpow(c,k-1));
ans=1ll*ans*d%p;
ans=1ll*ans*qpow(qm(S-c),p-2)%p;
printf("%d
",qm(qpow(S,k-1)-ans));
return 0;
}