题解

思路

固定一个二进制位 $x$，序列中下标只在该位不同的两个元素会形成一对；一次 $Y=0$ 或 $Y=1$ 的查询分别等价于用一个固定的 $2\times2$ 矩阵左乘每一对元素。

做法

作用于不同位的查询彼此可交换，因此可以按 $x$ 分组，同时保持同组查询的原顺序，先求出每一位对应的矩阵乘积，再把它应用到所有下标对上。

复杂度

矩阵累乘共需 $O(Q)$，每一位扫描整个序列需要 $O(2^N)$，故总时间复杂度为 $O(Q+N2^N)$，空间复杂度为 $O(2^N+N)$。