[AGC003F] Fraction of Fractal 题解

一道很好的矩阵题，可以尝试作为矩阵转移的优质练习题。

思路

考虑由于黑点在原图中处于联通的状态。

分三种情况讨论。

1. 上下左右联通。

   考虑这种情况下，不断分形后。

   最终产生的依然是一整个的大连通块。

   故，答案为一。

2. 上下左右都不连通。

   那么每一次分形后就会产生黑色点个连通块。

   最终答案为黑色点的数量的 \(k-1\) 次方。

3. 上下，左右中有一个点联通。

   容易发现上下，左右都是等价。

   那么我们只要统计左右相邻的，在两侧相邻的，以及黑色点的数量。

   推一推式子，就可以看见这玩意可以用矩阵优化。

   最后使用矩阵快速幂即可。

Code

AC记录。