[CEOI2020 D2T3 / CF1403C] 象棋世界Chess Rush 题解

这道题分为三个不同的子任务.

这个部分直接暴力即可,注意 (T = 'Q') 的部分有一点细节.

首先先判掉 (1+R+c1+cr) 是奇数的情况 . 这样的情况必然无解 .

枚举第一步是往左走然后往右走,然后贪心的往下跳,每一步都撞到边界,直到当前坐标 ((x,y)) 满足 (xgeq R,y=cr)

那么我们就求出了最优的步数。

方案数实际上就是考虑，记 (d=frac{x-R}{2}) , (t) 为转弯的次数,即步数 (-1.)

然后相当于在每个转弯的地方我可以缩进去一些距离，这些距离的和为 d ，那么这就是一个经典组合问题 , 答案为 (inom{t+d-1}{d}).

因为 d 是多出来的距离 , 不会超过 (O(C)) 级别 , 但是 t 是 (O(frac{R}{C})) 的 , 可能很大 , 所以我们使用 (O(C)) 的方法求组合数 .

那么就能做到每组询问 (O(C)) 查询了 .

一个 (O((C+Q)C^2 + Q imes C log C log R)) 做法

(O(C^3)) 暴力dp,然后使用 (O(Q)) 次BM算法求出递推式,总复杂度 (O((C+Q)C^2)) ，每次查询使用【模板】常系数齐次线性递推的科技来查询答案.

优化1:减少跑BM的次数

因为特征多项式 (F) 只有一个,并且只要求 (x^R) 对 (F) 取模的结果,并且 (R) 是一个定值,所以可以先 (O(C^2log R)) 或 (O(C^2+C log C log R)) 的复杂度求出取模之后的多项式,查询的时候直接 (O(C)) 就可以了.

复杂度上线性递推部分少了一个 (O(C)) (,)不过还是需要 (O(C^3)) 的暴力DP,所以复杂度实际上并没有变优.

优化2:优化掉暴力DP的 (O(C^3))

因为前 (C) 步不可能上下同时越界(,)所以就分别容斥掉越上界/下界的情况就可以了.需要 (O(C^2)) DP一下容斥的结果,然后就可以支持 (O(1)) 查询暴力 DP 的结果了.

那么查询还是 (O(C)) ,不过预处理的复杂度从 (O(C^3)) 降到了 (O(C^2))

优化3:优化求特征多项式的复杂度

特征多项式 (F_C=(λ-1)F_{C-1}-F_{C-2},) 所以可以 (O(C^2)) 直接计算,不需要使用BM了.

并且可以发现,把 (n) 个单位根的点值带进去,然后IDFT,就可以直接获得所求多项式的系数,复杂度 (O(Clog C).)

如果使用线性递推的科技,可以获得 (O(C^2 + C log C log R)-O(C)) 的复杂度.

优化4:进一步优化暴力DP解的计算/预处理

EI 对暴力 DP的解解出了一个封闭形式.

理论上可以优化到(O(Clog Clog R)-O(C)) 大家快来膜EI

我写的是不用NTT的做法,是 (O(C^2 log R)-O(C)) 的.