题解 AT2006 【[AGC003F] Fraction of Fractal】
ez_lcw
2020-10-16 13:55:44
先说一下下文会用到的定义或称呼的意思:
- 称单位分形为题目给出的 $1$ 级分形。
- 称一种分形左右联通,则说明将两个这种分形左右放在一起时,至少有一个连通块是跨越这两个分形的。
设一种分形的左右联通个数 $side_0$ 表示,当两个这种分形左右放在一起时,所贡献的连通块个数,即有多少个连通块是跨越左右两个分形的。显然,当一种分形左右不连通时,$side_0=0$。
设一种分形的 $tot_0$ 表示有多少组黑色单元格是左右相邻的。
比如下图中,这个分形是左右联通的,且 $side_0=2$,$tot_0=9$。
![](https://cdn.luogu.com.cn/upload/image_hosting/6m8krc53.png)
- 同理定义:一种分形的上下联通个数 $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_0$ 表示单位分形左右拼接之后相邻的黑块对数。
容易得到状态转移方程:
$$
\begin{aligned}
ans_i&=\underbrace{cnt\times ans_{i-1}}_{\text{上一级分形复制 $cnt$ 遍}}-\underbrace{tot\times s_{i-1}}_{\text{减去多出来的连通块个数}}\\
s_i&=s_{i-1}\times uside_0
\end{aligned}
$$
更详细的解释自己画个图就好了。
然后就可以用 $ans_1$、$s_1$ 设计初始矩阵,用 $cnt$、$tot$、$uside$ 设计转移矩阵,最后矩阵快速幂得到 $ans_k$。
由于矩阵的大小是常数级别的,所以总时间复杂度 $O(\log k)$。
代码如下:
```cpp
#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],uside[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++) uside[0]+=(s[i][1]=='#'&&s[i][m]=='#');
for(int i=1;i<=m;i++) uside[1]+=(s[1][i]=='#'&&s[n][i]=='#');
if(uside[0]&&uside[1])
{
puts("1");
return 0;
}
if(!uside[0]&&!uside[1])
{
printf("%lld\n",fastpow(cnt,k-1));
return 0;
}
tag=uside[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]=uside[tag];
Matrix ans=st*poww(trans,k-1);
printf("%lld\n",ans.a[1][1]);
return 0;
}
/*
....#....
...###...
...#.#...
.#..#..#.
#########
#.##.##.#
.#.....#.
###...###
#.#...#.#
*/
```