LOJ #3353. 「CEOI2020」象棋世界

题面传送门

什么缝合怪（

以下默认判掉一步走到。

Section 1: P

容易发现不会改变纵坐标，简单判断即可。

Section 2: R

两步，两种方案。

Section 3: Q

因为 \(n\geq m\)，所以直走两种方案，先斜着走再竖着走两种方案是一定有的。

以下默认其先往左下走，往右下走翻转再做一遍就好了。

如果上面的点在 \(m\) 处且 \(n=m\)，则可以先走对角线走到 \((n,1)\)，然后横着走走到终点。

如果黑白染色一样且不越界，则可以走两步斜着走到终点。

Section 4: B

特判黑白染色不一致的情况

枚举起点第一步往哪里走，终点最后一步往哪个方向走，则步数，以及路线的形状已经确定了。

现在有一个问题在于，路线不一定能经过终点，这时需要将某一些转弯的地方不要碰到边界再转，而是提前 \(x\) 步转，这样能对终点造成 \(2x\) 的偏差。

计算出需要提前的部署，然后组合数计算方案数即可。

你等会，如果有些转弯的地方不足 \(x\) 步，但是你给它分配了减少 \(x\) 步，那怎么办？

但是你会发现，如果出现这种情况，说明步数可以减少，则不会计算到最终的答案中，因此是正确的。时间复杂度 \(O(C)-O(1)\)，我偷懒写了个 \(O(1)-O(C\log p)\) 的（

Section 5: K

因为 \(n\geq m\)，所以步数为 \(n-1\)，然后问题相当于，从 \(r_1\) 开始，每次可以走到 \(x-1,x,x+1\) 三个地方，要求不能跑出 \([1,m]\)，求最后走到 \(r_c\) 的方案数。

考虑反射容斥的 DP 形式：将 \([1,m]\) 翻转赋值一份放到 \([m+2,2m+1]\)，并将系数变成 \(-1\)，并规定 \(2m+1\) 右边是 \(0\)，则初始设 \(r_1\) 处为 \(1\)，翻转处为 \(-1\)，则走 \(n-1\) 步就是方案数。因为在 \(0\) 处和 \(m+1\) 处两个值之间会相互抵消。

在预处理的时候对这个循环序列做快速幂，即可做到 \(O(C^2\log n)-O(C)\)，实现的好可以做到 \(O(C\log C\log n)-O(1)\) 不过我懒（

submission