题解 AT2006 【[AGC003F] Fraction of Fractal】

ez_lcw

2020-10-16 13:55:44

Solution

先说一下下文会用到的定义或称呼的意思: - 称单位分形为题目给出的 $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; } /* ....#.... ...###... ...#.#... .#..#..#. ######### #.##.##.# .#.....#. ###...### #.#...#.# */ ```