[CF1368G]Shifting Dominoes

壹、题目描述 ¶

  传送门 to CF.

贰、题解 ¶

  考察空格子的移动方式 —— 把一个牌动一步,再在后面接上一个牌,再......中途的任意一步都可以停下,具体地,就是下面这一幅图:

[CF1368G]Shifting Dominoes

  不难看出,这种移动方式具有很强的图论性质,并且,从图论上看,每个点的出度均为 \(1\),所以这个特别地图似乎是一个基环树?

  的确,如果你从基环树上直接开始树 \(\mathrm{DP}\),其实也是可以的,不过,对于环的处理是没有必要的,因为它并不存在环,接下来我们想要证明,这个图中是不存在环的:

  首先确定出现环的情况,其实无非就是出现了一个长这样的图:

[CF1368G]Shifting Dominoes

  如果我们将每个格子的中心看成是一个点,那么这样一个环实际上构成了一个点阵多边形,而该多边形的面积我们是可以计算的:

\[S=I+\frac{B}{2}-1 \]

  其中 \(I\) 为内部的点,\(B\) 为边界上的点,\(S\) 为该点阵多边形的面积。

  不妨使用反证法,假设这样的环存在,我们想要考察其内部是否存在矛盾,不妨从奇偶性上入手:

  • \(B\) 显然为 \(2\) 的倍数,更强地,\(B\) 实际上为 \(4\) 的倍数,因为每个骨牌长度为 \(2\),而我们想要围成这样的多边形一定需要偶数的骨牌;
  • 由假设得,\(I\) 也一定为偶数,因为内部需要被骨牌覆盖完全;
  • 多边形内部可以被分为多个 \(2\times 2\) 的部分,因此 \(S\) 一定为 \(4\) 的倍数;
  • 根据上述条件,\(S-\frac{B}{2}+1\) 一定为奇数,不过,\(I=S-\frac{B}{2}+1\) 又须得为偶数,这与前提矛盾,故假设不成立;

  由此,我们论述了这个图不存在环。

  现在,我们考虑如何统计方案数。先考虑一个问题:一个骨牌的两个格子是否会相互影响?

  答案是否定的,若我们将棋盘黑白染色,显然,空格的移动只会存在于相同颜色之间,所以,对于同一个骨牌,移除它之后,会在黑白中同时产生一个空格,而一个颜色的空格可以沿着我们建出来的树移动到某个子树中去,从 \(\mathrm{dfs}\) 序上讲,这个格子可以移动到某个区间中去。从黑白两个维度上讲,就是覆盖了一个矩阵中的任意一个点。

  移除一个骨牌,一个矩阵都可以被实现,我们考虑每一个骨牌,事实上就是矩阵的并,这个就不难了,用扫描线加上线段树实现即可。

  然而并没有代码

上一篇:2021-01-25


下一篇:838. Push Dominoes