ABC232 部分题目题解

• A

不讲，代码。

• B

挨个判断每一位需要做多少次即可，$O(|S|)$。

代码。

• C

题目已经给你判断相同图的方法了，注意到 $n\leq 8$ 所以直接阶乘枚举编号即可，$O(n^2\cdot n!)$。

代码。

• D

典型的标数法。

设 $f[i][j]$ 表示从 $(1,1)$ 走到 $(i,j)$ 中经过的最多的空方块个数。若无法走到则 $f[i][j]$ 设为 $-1$。

初始化：处理出第一行和第一列，如果当前格为障碍，则其再往右或往下均为 $-1$。

状态转移：
如果 $f[i-1][j]$ 和 $f[i][j-1]$ 均为 $-1$ 或者 $(i,j)$ 本身就是障碍，则 $f[i][j]$ 也应设为 $-1$。

否则，取 $f[i-1][j]$ 和 $f[i][j-1]$ 中的那个不是 $-1$ 的转移，不妨设 $f[i-1][j] \neq -1$，则 $f[i][j] = f[i-1][j] +1$。

时间复杂度：$O(nm)$。

代码。

• E

假设一矩阵 $M_k$ 表示車从 $(x1,y1)$ 出发后移动 $k$ 步后到每一个格子的方法种数。

易知：

$$M_0= \begin{bmatrix} 0 & \cdots & 0\\ \vdots& \vdots & \vdots\\ 0&\cdots 1\cdots &0\\ \vdots& \vdots & \vdots\\ 0&\cdots & 0\\ \end{bmatrix}$$

且 $M_k$ 中的 $(i,j)$ 上的数即为 $M_{k-1}$ 中第 $i$ 行 与第 $j$ 列上所有数的和（不算 $(i,j)$）。

可以发现一个事实：对于任意 $M_k$，第 $x1$ 行上的数（不算 $(i,j)$） 全部相同，第 $y1$ 列上的数（不算 $(i,j)$） 全部相同，其余所有的数也全部相同。

那么可以设：

$$M_k= \begin{bmatrix} d & d& \cdots b& \cdots d&\\ d & d& \cdots b& \cdots d&\\ \vdots& \vdots& \cdots \vdots&\cdots\vdots& \\ c & c& \cdots a& \cdots c&\\ d & d& \cdots b& \cdots d&\\ \vdots& \vdots& \cdots \vdots& \cdots\vdots& \\ d & d& \cdots b& \cdots d&\\ \end{bmatrix}$$

则可得出递推式子：

$$\begin{cases} a=(n-1)b_0+(m-1)c_0\\ b=a_0+(n-2)b_0+(m-1)d_0\\ c=a_0+(m-2)c_0+(n-1)d_0\\ d=b_0+c_0+(n+m-4)d_0 \end{cases}$$

复杂度 $O(k)$，可以过，代码。

优化

这个式子显然可以矩阵递推。

设 $A_k=\begin{bmatrix}a,b,c,d\end{bmatrix}$。

$$A_k=A_{k-1}* \begin{bmatrix} 0&n-1&m-1&0\\ 1&n-2&0&m-1\\ 1&0&m-2&n-1\\ 0&1&1&n+m-4 \end{bmatrix}$$

那么就可以 $O(\log k)$ 了。