Atcoder [AGC003F] Fraction of Fractal

本文主要是介绍Atcoder [AGC003F] Fraction of Fractal，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

Snuke从他的母亲那里得到了生日礼物——一个网格。网格有H行W列。每个单元格都是黑色或白色。所有黑色单元格都是四联通的，也就是说，只做水平或垂直移动且只经过黑色单元格即可从任何黑色单元格移动到任何其他黑色单元格。

第i行第j列的单元格的颜色由字符si,j表示。如果si,j是 #，该单元格为黑色；如果si,j是 .，该单元格为白色。至少一个单元格是黑色的。

我们定义「分形」如下:0级分形是一个 1×1的黑色单元格.k级分形由H行W列较小一级的分形按照 Snuke 的网格的样式拼成：与Snuke 网格中的黑色单元格对应的位置是一个k级分形；与Snuke 网格中的白色单元格对应的位置是一个单元格全部为白色，尺寸与k级分形相同的网格。

您将得到 Snuke 的网格的描述和整数 K。请求出K级分形中黑色单元格组成的连通分量数，模 $10^9+7$ 。

Input

    第一行三个整数H，W，K如题目描述接下来H行，每行W个字符

Output

    输出K级分形中黑色单元格组成的连通分量数，模109+7。

Solution

一眼矩阵快速幂。

首先，一个网格的上下左右都连通，那么不管怎么分它都是连通的，所以答案是 1。
如果一个网格上下左右都不连通，那么不管怎么分都是不连通的，所以答案是 $x^{k−1}$ （给定网格连通），x 为黑块总个数。

剩下就是行连通，列不连通了。
列联通行不连通的转90度处理。

x[k] 表示 k 级分型有多少个黑块。
y[k] 表示 k 级分型有多少个黑块满足右边一个也是黑块。
z[k] 表示 k 级分型有多少行是连通的。
有
$x[k]=x[k−1]^2\\y[k]=x[k−1]y[k−1]+z[k−1]y[k−1]\\z[k]=z[k−1]^2$
自己画个图就知道了，z[k-1][y-1]是更多行连通多出来的数量。
直接矩阵快速幂即可。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
char ch[1010][1010];
char a[1010][1010];
int n,m,bl,c[3],nxt[3]; 
struct Matrix{ll mat[3][3];Matrix(){memset(mat,0,sizeof(mat));}Matrix operator*(const Matrix &b)const{Matrix c;for(int i=1;i<=2;i++)for(int j=1;j<=2;j++){for(int k=1;k<=2;k++)c.mat[i][j]+=mat[i][k]*b.mat[k][j];c.mat[i][j]%=mod;}return c;}Matrix operator^(long long x)const{Matrix a(*this),ans;for(int i=1;i<=2;i++)ans.mat[i][i]=1;while(x){if(x&1)ans=ans*a;x>>=1,a=a*a;}return ans;}
}u,v;
ll k;
int qpow(int x,ll y){int s=1,bas=x;while(y){if(y&1) s=(s*1ll*bas)%mod;bas=(bas*1ll*bas)%mod;y>>=1;}//cout<<x<<" "<<y<<" "<<s<<endl;return s;
}
void turn(){for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)ch[m-j+1][i]=a[i][j];swap(n,m);memcpy(a,ch,sizeof(a));
}
int main(){scanf("%d%d%lld",&n,&m,&k);for(int i=1;i<=n;i++){scanf("%s",a[i]+1);for(int j=1;j<=m;j++){if(a[i][j]=='#') bl++;if(j<m&&a[i][j]=='#'&&a[i][j+1]=='#') nxt[1]++;}if(a[i][1]=='#'&&a[i][m]=='#') c[1]++;}turn();for(int i=1;i<=n;i++){for(int j=1;j<m;j++)if(a[i][j]=='#'&&a[i][j+1]=='#') nxt[2]++;if(a[i][1]=='#'&&a[i][m]=='#') c[2]++;}if(c[1]&&c[2]){printf("%d",1);return 0;}//cout<<"???\n";if(c[1]==0&&c[2]==0){//cout<<"?\n";printf("%d",qpow(bl,k-1));return 0;}//cout<<c[1]<<" "<<c[2]<<" "<<nxt[1]<<" "<<nxt[2]<<endl;int cl=c[2],nt=nxt[2];if(c[1]) turn(),cl=c[1],nt=nxt[1];u.mat[1][1]=bl,u.mat[1][2]=nt;u.mat[2][1]=0,u.mat[2][2]=cl;//cout<<u.mat[1][1]<<" "<<u.mat[1][2]<<" "<<u.mat[2][1]<<" "<<u.mat[2][2]<<endl;u=u^(k-1);printf("%lld",(u.mat[1][1]-u.mat[1][2]+mod)%mod);//cout<<u.mat[1][1]<<" "<<u.mat[1][2]<<" "<<u.mat[2][1]<<" "<<u.mat[2][2]<<endl; 
}`