这道题目是香蕉的加强版
当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_香蕉了