[??记录]AT2006 [AGC003F] Fraction of Fractal
command_block
2021-04-21 11:37:49
**题意** ： 给出一张 $n\times m$ 的黑白点阵。定义其为初始图。
定义 $0$ 级分型为单独一个黑格。
定义 $k$ 级分型 ： 将初始图的每个黑格替换为 $k-1$ 级分型，而将白格替换为纯白的，和 $k-1$ 级分型同样大小的区域。
求 $k$ 级分型中黑格形成的四联通块个数，答案对 $10^9+7$ 取模。
保证 $1$ 级分型中的黑格四连通。
$n,m\leq 10^3,k\leq 10^{18}$ ，时限 $\texttt{2s}$。
------------
- 初始图上下连通，左右也连通。
答案是 $1$。
- 初始图上下不连通，左右也不连通。
设 $c$ 为初始图中的黑格个数，答案是 $c^{k-1}$。
- 初始图仅上下连通或仅左右连通。
考虑仅上下联通的情况，另一种情况只需翻转初始图。
此时，只有上下两个相邻的初始图之间可能联通，以初始图为单元，边集为森林（若干条竖链）。
于是，联通块个数等于点数减边数，即 $c^{k-1}-$ 上下相邻的初始图对数。
记 $a$ 为初始图中上下相邻的黑格对数，$b$ 为跨越上下边界的相邻的黑格对数。
对于 $k$ 级分型，记 $a_k$ 为分型中上下相邻的初始图对数， $b_k$ 为跨越上下边界相邻的初始图对数，$c_k$ 为含有的初始图数目。
则有如下递推关系 ：
$$
\begin{aligned}
a_k&=a_{k-1}*c+b_{k-1}*a\\
b_k&=b_{k-1}*b\\
c_k&=c_{k-1}*c\\
\end{aligned}
$$
不难用矩阵快速幂加速计算。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 1050
using namespace std;
const int mod=1000000007;
ll powM(ll a,ll t){
ll ret=1;
while(t){
if (t&1)ret=ret*a%mod;
a=a*a%mod;t>>=1;
}return ret;
}
struct Matrix{
ll a[3][3];
void I(){
for (int i=0;i<3;i++)
for (int j=0;j<3;j++)
a[i][j]=(i==j);
}
};
Matrix operator * (const Matrix &A,const Matrix &B)
{
Matrix C;
for (int i=0;i<3;i++)
for (int j=0;j<3;j++){
C.a[i][j]=0;
for (int k=0;k<3;k++)
C.a[i][j]=(C.a[i][j]+A.a[i][k]*B.a[k][j])%mod;
}
return C;
}
Matrix powM(Matrix A,ll t){
Matrix R;R.I();
while(t){
if (t&1)R=R*A;
A=A*A;t>>=1;
}return R;
}
ll calc(int a,int b,int c,ll k)
{
Matrix A;
A.a[0][0]=c;A.a[1][0]=a;A.a[2][0]=0;
A.a[0][1]=0;A.a[1][1]=b;A.a[2][1]=0;
A.a[0][2]=0;A.a[1][2]=0;A.a[2][2]=c;
A=powM(A,k-1);
return (A.a[1][0]+A.a[2][0])%mod;
}
int n,m;long long k;
char s[MaxN][MaxN];
int main()
{
scanf("%d%d%lld",&n,&m,&k);
if (k<=1){puts("1");return 0;}
for (int i=1;i<=n;i++)
scanf("%s",s[i]+1);
int b1=0,b2=0,c=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
c+=s[i][j]=='#';
for (int i=1;i<=n;i++)
b1+=s[i][1]=='#'&&s[i][m]=='#';
for (int j=1;j<=m;j++)
b2+=s[1][j]=='#'&&s[n][j]=='#';
if (!b1&&!b2){printf("%lld",powM(c,k-1));return 0;}
if (b1&&b2){puts("1");return 0;}
int a=0;
if (b1){
for (int i=1;i<=n;i++)
for (int j=1;j<m;j++)
a+=s[i][j]=='#'&&s[i][j+1]=='#';
printf("%lld",(powM(c,k-1)-calc(a,b1,c,k)+mod)%mod);
}else {
for (int i=1;i<n;i++)
for (int j=1;j<=m;j++)
a+=s[i][j]=='#'&&s[i+1][j]=='#';
printf("%lld",(powM(c,k-1)-calc(a,b2,c,k)+mod)%mod);
}return 0;
}
```