4344. [国家集训队 2026]解开尘封的序列

【题目描述】

给定进制数 $p \in \{2, 3\}$。定义 $p$ 进制下的位运算如下：

- 对于 $0 \le x < p^d$，设 $x$ 的 $p$ 进制表示为 $\overline{(x_{d-1} \cdots x_1 x_0)}_p$（不足 $d$ 位的用前导 0 补齐），定义 $\text{popcount}_p(x)$ 为 $x$ 的 $p$ 进制表示下**非零位的个数**，即 $\sum_{i=0}^{d-1} [x_i > 0]$。

- 对于 $0 \le x, y < p^d$，设 $x, y$ 的 $p$ 进制表示分别为 $\overline{(x_{d-1} \cdots x_1 x_0)}_p, \overline{(y_{d-1} \cdots y_1 y_0)}_p$（不足 $d$ 位的用前导 0 补齐），定义如下三种运算：

 1. **$p$ 进制按位与**：$x \text{ and}_p y = \overline{(z_{d-1} \cdots z_1 z_0)}_p$，其中 $z_i = \min(x_i, y_i)$ ($0 \le i < d$)；

 2. **$p$ 进制按位或**：$x \text{ or}_p y = \overline{(z_{d-1} \cdots z_1 z_0)}_p$，其中 $z_i = \max(x_i, y_i)$ ($0 \le i < d$)；

 3. **$p$ 进制按位异或**（即 **$p$ 进制不进位加法**）：$x \text{ xor}_p y = \overline{(z_{d-1} \cdots z_1 z_0)}_p$，其中 $z_i = (x_i + y_i) \bmod p$ ($0 \le i < d$)。

给定两个长度为 $n$ 的序列 $a, w$ 和一个长度为 $p^d$ 的序列 $z$，其中对于所有 $1 \le i \le n$，$0 \le a_i < p^d$。对于所有 $0 \le u < p^d$，定义 $u$ 的生成序列 $F(u)$ 如下：

- 对于 $1 \le i \le n$，令$$b_i = A \cdot \text{popcount}_p(a_i \text{ and}_p u) + B \cdot \text{popcount}_p(a_i \text{ or}_p u) + C \cdot \text{popcount}_p(a_i \text{ xor}_p u),$$

 其中 $A, B, C$ 为给定的非负整数。

- 令 $F(u)$ 为将 $b$ **从小到大排序**后得到的序列，即 $F(u) = \text{sorted}([b_1, b_2, \dots, b_n])$。

有 $q$ 次询问，每次询问给定 $A, B, C, l_1, r_1, l_2, r_2$，求$$\left( \sum_{i=l_1}^{r_1} \sum_{j=l_2}^{r_2} z_i w_j F(i)_j \right) \bmod 2^{32}.$$

【输入格式】

输入的第一行包含三个非负整数 $n, d, p$。

输入的第二行包含 $n$ 个非负整数 $a_1, a_2, \dots, a_n$。

输入的第三行包含 $n$ 个非负整数 $w_1, w_2, \dots, w_n$。

输入的第四行包含 $p^d$ 个非负整数 $z_0, z_1, \dots, z_{p^d - 1}$。

输入的第五行包含一个正整数 $q$，表示询问次数。

输入的第 $i+5$ ($1 \le i \le q$) 行包含七个非负整数 $A, B, C, l_1, r_1, l_2, r_2$，表示第 $i$ 次询问。

【输出格式】

输出 $q$ 行，第 $i$ ($1 \le i \le q$) 行一个非负整数表示第 $i$ 次询问的答案。

【样例输入】

3 2 2
0 0 2
1 1 2
3 4 4 4
5
1 7 2 0 1 1 1
3 3 5 0 2 2 3
5 2 10 0 1 2 3
3 9 7 0 3 3 3
5 6 1 0 1 2 3

【样例输出】

36
304
312
736
182

【数据规模与约定】

对于所有测试数据，均有：

- $1 \le n \le 3 \times 10^5$，$0 \le d \le 12$，$p \in \{2, 3\}$；

- 对于所有 $1 \le i \le n$，均有 $0 \le a_i < p^d$；

- 对于所有 $1 \le i \le n$，均有 $0 \le w_i < 2^{32}$；

- 对于所有 $0 \le i < p^d$，均有 $0 \le z_i < 2^{32}$；

- $1 \le q \le 3 \times 10^5$；

- $0 \le A, B, C \le 10^9$，$0 \le l_1 \le r_1 < p^d$，$1 \le l_2 \le r_2 \le n$。

特殊性质 A：所有询问的给出的三元组 $(A, B, C)$ 均相同。

特殊性质 B：对于所有询问，均有 $l_1 = r_1$。

特殊性质 C：对于所有询问，均有 $l_1 = 0$ 且 $r_1 = p^d - 1$。

【提示】

本题输入输出规模较大，请使用较为快速的输入输出方式。

【来源】

IOI2026中国国家集训队集中培训 Day3 Task3