题解：P12911 [POI 2020/2021 R2] 棋盘 / Projekt planszy

· · 题解

分析

构造棋盘使走法数满足题意，一开始想的是类似递归的方法，每次将棋盘分成几个部分，最后将各部分方案数整合起来，但有些麻烦，最后还是另起炉灶，利用了三条特性：

  1. 不相交的路的方案数是互相独立的，计算的时候总方案数为各路方案数之和；
  2. 如果将一条路拆分成若干个部分且相邻两部分仅由一条路相连，则方案数为各部分方案数之积；
  3. 用某种方法拆分走法数 K。

举个例子：

设现在 K 等于 1234，则借助特性 2，猜想是否可以将棋盘分出 4 条路，使得各条路的走法数依次为 1000，200，30，4。又借助特性 3，思考将 1000 拆成 3 个走法数均为 10 的小图。200 则可以拆成 1 个走法数为 2 的小图和 2 个走法数为 10 的小图。为了整体的统一性（更好写），在数位上的数字为 1 时，应多一个走法数为 1 的图。

这里小图用 4 \times 4 的规格。

空白处均为障碍，灰色均为通道，4 \times 4 的红色块代表一个走法数为该数字的部分，列举几种情况：

走法数为 1 的小图：

....
###.
###.
###.

走法数为 5 的小图：

....
....
.##.
....

记得最后要补 4 行 #，因为棋盘是正方形的。

粗略计算边长最大为 90 左右，满足要求。