AT_agc003_f [AGC003F] Fraction of Fractal 题解

zrl123456 · 2025-10-22 09:12:14 · 题解

:::::info[题目基本信息] 考察：矩阵加速，构造（3344）。
题目简介：
给定一个 n\times m 的黑白网格 a，定义 k 级分形如下：

• 当 k=0 时，k 级分形是一个黑色网格。
• 否则，对于 k-1 级分形的每一个网格：
  • 如果该格为黑色网格，那么整体替换为所给网格。
  • 否则，整体替换为 n\times m 的白色网格。

问最后的 k 级分形有几个黑色网格四联通分量（对 10^9+7 取模）。
数据范围：

• 1\le n,m\le 1000
• 0\le k\le 10^{18}

• 保证当 k=1 时，答案是 1。
  注意到有一个 k\le 10^{18} 的限制，说明要么是结论要么是矩阵加速，我们开始找性质。

1. 当 k=0 时，答案为 1。
2. 当两个所给网格上下拼接或左右拼接均有连通块发生拼接，则无论 k 为几，答案均是 1。
   容易发现上面“两个所给网格上下拼接或左右拼接均有连通块发生拼接”的充要条件是 \exist i\in[1,n],a_{i,1} 和 a_{i,m} 均为黑色且 \exist j\in[1,m],a_{1,j} 和 a_{n,j} 均为黑色。
3. 当两个所给网格上下拼接或左右拼接均无连通块发生拼接，则无论 k 为几，答案均是 sum^{k-1}，其中，sum 表示所给网格中黑色网格的个数。
   该性质充要条件根据 2 同理可得。

上面是比较显然的性质，现在还剩两个所给网格上下拼接或左右拼接其中有一种拼接使得有连通块发生拼接的情况，容易发现左右拼接和上下拼接类似，以上下拼接为例。
:::::success[小技巧] 在代码实现时可以使用矩阵交换行的方式统一成上下拼接。
::::: 由于左右不发生拼接，所以我们可以一行一行考虑。
设 ans_k 为 k 级分形的黑色网格四联通块数量。
正推不好做，考虑容斥，先算出 sum\cdot ans_{k-1} 再减去算重的，就是上下拼接减少的联通块数量，容易发现每个拼接处本质相同，就等于所给网格的上下相邻黑格对数乘上 k-1 级分形的上下拼接减少的联通块个数，前面这项设为 num，后面这项设为 s_{k-1}，可以直接和 ans 一起算。
最终得到转移方程式：

其中，numud 表示所给网格上下拼接时新相拼接的黑格对数。
然后开一个 siz=2 的矩阵加速一下即可。
时间复杂度为 \Theta(siz^3\log k+nm)，空间复杂度为 \Theta(nm+siz^3)。

code