CF1545B AquaMoon and Chess 题解

· · 题解

首先考虑最基础的地方，1 在棋盘中是怎么移动的。

跳来跳去看起来有些繁琐，我们考虑对操作进行简化:

这样操作就变成了 选择连续的 11 然后左右移动。

考虑这么一种特殊的情况：

如果棋盘上都是 11，显然它们都可以自由左右移动，那么就可以转化成是棋盘中放若干个 11 有多少种方案，这是排列组合的模板题，如果我们把所有 11 看扁成 1，如果有 a 个 1，总共有 n 个格子，那么答案显然是 \binom{n}{a}。那么如果有 a 个 11，总共有 n 个格子，如果要转化成前者那就是把看扁的格子去掉，也就是 n-a 个格子，答案是 \binom{n-a}{a}。

但是棋盘上不一定都能划分成若干个 11，那么我们就要考虑划分后留下的 1 和 11 有一些什么关系。

我们发现当 11 和 1 贴贴的时候，可以把 11 拆出来一个 1 和右边的 1 合并，这是一个棘手的问题，因为我们是打算把 11 看作一个整体而不可拆分的。

但是如果我们在这个步骤里加上一个中间过程，就可以避免这种现象了。

如果看作中途 11 和 1 交换了前后位置，而不是把 11 拆了，就可以继续使用前面的整体思想了。

观察上图中的 11 其实还是在自由移动的，去掉了 1 也是可以到达原来的那些位置，但是再看上图中的第 2，3 步，虽然 11 移动了位置，但是在棋盘上 11 在 1 的前后都是同一种方案，所以也就相当于棋盘上每出现一个 1，棋盘还要去掉一个格子。

那么当有a 个 11，b 个 1，棋盘上有 n 格的时候，还是可以按照前面特殊情况的方法得到答案，此时答案为 \binom{n-a-b}{a}。

完结撒花 qwq，代码太丑就不放了（）。

如果不会写组合数的计算，那么可以参考下这个公式：

\binom{m}{n} = \frac{m!}{n!(m-n)!}

如果不知道在取模的情况下怎么除以一个数，那么可以做下这题：

P3811 【模板】乘法逆元

在取模的情况下除以一个数就相当于乘上这个数的逆元。