这道题目是香蕉的加强版

当m=100w时矩阵会很大,而且又有多组询问,所以这道题用原来香蕉的程序会T

所以我们需要更好点的做法

我们考虑优化我们的状态

首先考虑这道题的隐藏性质,考虑不合法的情况

那么A至少是B的2倍,我们考虑不合法的一段,容易证明这段的最大长度不会超过logm

不妨设s[i]表示长度为i的每个位置都不合法的方案数

由于长度是logm,所以对于s的求解是m*log^2m的

用一些奇技淫巧可以优化一下常数,使得复杂度接近m*logm

之后我们考虑容斥

设f[i][0]表示长度为i的不合法的位置至少为偶数个的方案数

f[i][1]表示长度为i的不合法的位置至少为奇数个的方案数

这是很容易的DP的,DP的时候枚举末尾一段有多少个连续不合法的即可

根据枚举的长度分奇数偶数讨论转移

之后我们发现这个转移是固定的,而且转移涉及的状态数只有2*logm个

所以我们可以考虑构造矩阵来优化转移

这样矩阵乘法一次的时间复杂度为8*log^3m,远远比上一道香蕉的做法要优秀

最后的答案显然是f[n][0]-f[n][1],对于每个询问暴力矩阵乘法就可以了

总时间复杂度O(logn*log^3m+mlogm)

就这样,我们就可以完美的解决这道题目了

在CTSC的时候,徐明宽大爷说矩阵乘法在求单行或单列的时候是可以做到n^2的

那么我们可以用这个方法继续优化EX_香蕉,这样就可以把T扩大,变成EX_EX_香蕉了

05-02 14:26