1 条题解

  • 0
    @ 2026-11-15 16:51:18

    20pts

    O(n2)O(n^2) 求解出每个位置的权值,对于每次询问 O(1)O(1) 输出。

    40pts

    首先注意到每一位是独立的。

    如果用第 00 行来计算 (x,y)(x, y),(0,i)(0, i) 对 (x,y)(x, y) 的贡献系数是 (xi−y)mod  2\binom{x}{i-y} \mod 2.

    对于 (nk)mod 2\binom{n}{k} \text{mod}\ 2,可以利用 lucas 定理知道 $\binom{n}{k} \mod 2 = \binom{n / 2}{k / 2} \times \binom{n \% 2}{k \% 2}$.

    其实就是要求 (n%2k%2)mod 2\binom{n \% 2}{k \% 2} \text{mod}\ 2 总是为 11,才能使得 (nk)mod 2\binom{n}{k} \text{mod}\ 2 为 11.

    也就是 kk 应当是 nn 的子集,所以有贡献的位置仅有 2popcount(x)2^{popcount(x)} 个,至此我们可以通过枚举子集得到一个 2popcount(x)2^{popcount(x)}​ 的单次做法。

    因为数据随机生成,复杂度为 E(2popcount(x))×qE(2^{popcount(x)}) \times q,可以通过。

    100pts

    那么更一般的,我们可以用第 tt 行来计算 (x,y)(x, y),对于 (t,i)(t, i) 对 (x,y)(x, y) 的贡献系数是 (x−ti−y)\binom{x-t}{i-y},这启发我们可以令 t=xmod  512t = x\mod 512.

    通过预处理 [0,512)[0, 512) 行,我们可以得到一个 2popcount(x/512)2^{popcount(x/512)} 的单次做法.

    总复杂度 O(NB+QNB)O(NB + \frac{QN}{B})可以通过本题(其中 B=512B = 512)。

    • 1

    信息

    ID
    144
    时间
    1000ms
    内存
    512MiB
    难度
    4
    标签
    递交数
    1
    已通过
    1
    上传者