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\) 级分形时，\(n\cdot m\)个 \(i\) 级分形之间连通的个数（因为之间多连通一对，那最终联通块个数减一）
则有
\[f_i=\begin{cases}
\ d, & i=1\\
\ f_{i-1}\cdot c, & i\geq 2
\end{cases}\]
由于在 \(i\) 级分形到第 \(i+1\) 级分形中合并的数量在 \(k\) 级分形中会被复制 \(S^{k-1-i}\) 次
所以答案为
\[Ans=S^{k-1}-\sum_{i=1}^{k-1}f_i\cdot 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}-d\cdot c^{-1}\cdot S^{k-1}\cdot \sum_{i=1}^{k-1}c^i\cdot S^{-i}
\]
\[Ans=S^{k-1}-d\cdot c^{-1}\cdot S^{k-1}\cdot \sum_{i=1}^{k-1}(\frac cS)^i
\]
\[Ans=S^{k-1}-d\cdot 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\n",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\n",qm(qpow(S,k-1)-ans));
return 0;
}
