题解 CF1403C 【Chess Rush】
s_r_f
·
·
题解
我的CEOI作战记录&题解-洛谷博客
我的CEOI作战记录&题解-cnblogs
这道题分为三个不同的子任务.
subtask1 : T = 'P'/'R'/'Q'
这个部分直接暴力即可,注意 T = 'Q' 的部分有一点细节.
subtask2 : T = 'B'
首先先判掉 1+R+c1+cr 是奇数的情况 . 这样的情况必然无解 .
枚举第一步是往左走然后往右走,然后贪心的往下跳,每一步都撞到边界,直到当前坐标 (x,y) 满足 x\geq R,y=cr
那么我们就求出了最优的步数。
方案数实际上就是考虑，记 d=\frac{x-R}{2} , t 为转弯的次数,即步数 -1.
然后相当于在每个转弯的地方我可以缩进去一些距离 ，这些距离的和为 d ，那么这就是一个经典组合问题 , 答案为 \binom{t+d-1}{d}.
因为 d 是多出来的距离 , 不会超过 O(C) 级别 , 但是 t 是 O(\frac{R}{C}) 的 , 可能很大 , 所以我们使用 O(C) 的方法求组合数 .
那么就能做到每组询问 O(C) 查询了 .
subtask3 : T = 'K'
一个 O((C+Q)C^2 + Q \times C \log C \log R) 做法
**优化1:减少跑BM的次数**
因为特征多项式 $F$ 只有一个,并且只要求 $x^R$ 对 $F$ 取模的结果,并且 $R$ 是一个定值,所以可以先 $O(C^2\log 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(C\log C).
如果使用线性递推的科技,可以获得 O(C^2 + C \log C \log R)-O(C) 的复杂度.
优化4:进一步优化暴力DP解的计算/预处理
EI 对暴力 DP的解解出了一个封闭形式.
理论上可以优化到O(C\log C\log R)-O(C) 大家快来膜EI
我写的是不用NTT的做法,是 O(C^2 \log R)-O(C) 的.
代码 : 见云剪贴板