[AGC003F] Fraction of Fractal 题解
一道很好的矩阵题，可以尝试作为矩阵转移的优质练习题。
思路
考虑由于黑点在原图中处于联通的状态。
分三种情况讨论。
-
上下左右联通。
考虑这种情况下，不断分形后。
最终产生的依然是一整个的大连通块。
故，答案为一。
-
上下左右都不连通。
那么每一次分形后就会产生黑色点个连通块。
最终答案为黑色点的数量的 \(k-1\) 次方。
-
上下，左右中有一个点联通。
容易发现上下，左右都是等价。
那么我们只要统计左右相邻的，在两侧相邻的，以及黑色点的数量。
推一推式子，就可以看见这玩意可以用矩阵优化。
最后使用矩阵快速幂即可。
Code
AC记录。