题意
给定一个由黑白组成的网格。
保证黑子四联通。
规定一次操作为使用最初的网格图替换当前网格图的所有黑色格子。
操作 \(k\) 次。
问最终有多少个黑色连通块，对 \(10 ^ 9 + 7\) 取模。
\(k \le 10 ^ {18}\)。
Sol
先不难注意到这个东西只和原网格图是否左右联通和上下联通有关。
注意到若左右上下都联通，那么最终只有一个连通块，若都不联通，那么最终的连通块数为 \(cnt ^ {k - 1}\)。
考虑只有左右或者只有上下联通的情况。
不难想到那个很 \(trivial\) 的结论，即 连通块数 = 点数 - 边数。
考虑进行的最后一次替换操作，那么显然 连通块数 即为 点数 减去 图中左右黑色点相邻的对数。
设点数为 \(a\)，黑色点相邻对数为 \(b\)，最初的图的黑色点相邻对数为 \(c\)，最初的图的左右联通相邻对数为 \(d\)。
不难发现：\(b' = a \times c + b \times d\)。
不妨构造矩阵：
\[\begin{pmatrix} a & b \end{pmatrix} \times \begin{pmatrix} c \cr d \end{pmatrix} \]注意到因为每次都是乘一个原始矩阵，因此 \(b\) 和 \(c\) 直接合并不管就行了。
因此答案为：
\[\begin{pmatrix} a & b \cr 0 & d \end{pmatrix} ^ {k - 1} \]复杂度 \(O(\log k)\)。
标签：连通,联通,end,网格,AGC003F,pmatrix,Fraction,对数,Fractal From： https://www.cnblogs.com/cxqghzj/p/18413008