syfima

题解 I题题解

题解

/ 注册

I题题解

29 浏览 0 回复 2026-05-04

syfima

+关注

The Yakumo Family

https://ac.nowcoder.com/acm/contest/133507/I

我们考虑一个更广义的情况，不是选取 $3$ 个区间，而是要选取 $m$ 个区间. 设 $\omega$ 是各个 $a_i$ 二进制位数的上界（在本题中可取 $32$ ），再设 $p_i = \bigoplus_{j = 1}^i a_j$ 是 $a$ 数组的前缀异或， $x_{i, b} \in \{0, 1\}$ 表示 $p_i$ 从小到大的第 $b$ 个二进制位，那么题目所求可以列为如下式子：

\begin{align} &\mathrel{\phantom{=}} \sum_{1 \le l_1 \le r_1 < l_2 \le r_2 < \dots < l_m \le r_m \le n} \prod_{k = 1}^m \bigoplus_{i = l_k}^{r_k} a_i \\ &= \sum_{1 \le l_1 \le r_1 < l_2 \le r_2 < \dots < l_m \le r_m \le n} \prod_{k = 1}^m (p_{r_k} \oplus p_{l_k - 1}) \\ &= \sum_{1 \le l_1 \le r_1 < l_2 \le r_2 < \dots < l_m \le r_m \le n} \prod_{k = 1}^m \left(\bigoplus_{b = 0}^{\omega - 1} 2^b x_{r_k, b} \oplus \bigoplus_{b = 0}^{\omega - 1} 2^b x_{l_k - 1, b}\right) \\ &= \sum_{1 \le l_1 \le r_1 < l_2 \le r_2 < \dots < l_m \le r_m \le n} \prod_{k = 1}^m \bigoplus_{b = 0}^{\omega - 1} \left(2^b x_{r_k, b} \oplus 2^b x_{l_k - 1, b}\right) \\ &= \sum_{1 \le l_1 \le r_1 < l_2 \le r_2 < \dots < l_m \le r_m \le n} \prod_{k = 1}^m \bigoplus_{b = 0}^{\omega - 1} 2^b (x_{r_k, b} \oplus x_{l_k - 1, b}) \\ &= \sum_{1 \le l_1 \le r_1 < l_2 \le r_2 < \dots < l_m \le r_m \le n} \prod_{k = 1}^m \sum_{b = 0}^{\omega - 1} 2^b (x_{r_k, b} \oplus x_{l_k - 1, b}) \\ &= \sum_{1 \le l_m \le r_m \le n} \dots \sum_{1 \le l_2 \le r_2 < l_m} \sum_{1 \le l_1 \le r_1 < l_2} \prod_{k = 1}^m \sum_{b = 0}^{\omega - 1} 2^b (x_{r_k, b} \oplus x_{l_k - 1, b}) \\ &= \sum_{1 \le l_m \le r_m \le n} \dots \sum_{1 \le l_2 \le r_2 < l_m} \sum_{1 \le l_1 \le r_1 < l_2} \sum_{b_1 = 0}^{\omega - 1} \sum_{b_2 = 0}^{\omega - 1} \dots \sum_{b_m = 0}^{\omega - 1} \prod_{k = 1}^m 2^{b_k} (x_{r_k, b_k} \oplus x_{l_k - 1, b_k}) \\ &= \sum_{1 \le l_m \le r_m \le n} \sum_{b_m = 0}^{\omega - 1} \dots \sum_{1 \le l_2 \le r_2 < l_m} \sum_{b_2 = 0}^{\omega - 1} \sum_{1 \le l_1 \le r_1 < l_2} \sum_{b_1 = 0}^{\omega - 1} \prod_{k = 1}^m 2^{b_k} (x_{r_k, b_k} \oplus x_{l_k - 1, b_k}) \\ &= \sum_{1 \le l_m \le r_m \le n} \sum_{b_m = 0}^{\omega - 1} 2^{b_m} (x_{r_m, b_m} \oplus x_{l_m - 1, b_m}) \left(\dots \sum_{1 \le l_2 \le r_2 < l_m} \sum_{b_2 = 0}^{\omega - 1} \left(2^{b_2} (x_{r_2, b_2} \oplus x_{l_2 - 1, b_2}) \sum_{1 \le l_1 \le r_1 < l_2} \sum_{b_1 = 0}^{\omega - 1} 2^{b_1} (x_{r_1, b_1} \oplus x_{l_1 - 1, b_1}) \right) \right) \\ &= f[n][m] \end{align}

我们可以引入由如下定义的 $f[i][k]$ 来表示上式递归的结构

\begin{align} & f[i][0] := 1 \\ & f[i][k] := \sum_{1 \le l \le r \le i} \sum_{b = 0}^{\omega - 1} 2^{b} (x_{r, b} \oplus x_{l - 1, b}) f[l - 1][k - 1] \\ \end{align}

继续推式子：

\begin{align} f[i][k] &= \sum_{1 \le l \le r \le i} \sum_{b = 0}^{\omega - 1} 2^{b} (x_{r, b} \oplus x_{l - 1, b}) f[l - 1][k - 1] \\ &= \sum_{r = 1}^i \sum_{l = 1}^r \sum_{b = 0}^{\omega - 1} 2^{b} (x_{r, b} \oplus x_{l - 1, b}) f[l - 1][k - 1] \\ &= \sum_{r = 1}^i \sum_{b = 0}^{\omega - 1} 2^{b} \sum_{l = 1}^r (x_{r, b} \oplus x_{l - 1, b}) f[l - 1][k - 1] \\ &= \sum_{r = 1}^i \sum_{b = 0}^{\omega - 1} 2^{b} \sum_{\substack{l = 1 \\ x_{l - 1, b} \ne {x_{r, b}}}}^r f[l - 1][k - 1] \\ &= \sum_{r = 1}^i \sum_{b = 0}^{\omega - 1} 2^{b} \sum_{\substack{l = 0 \\ x_{l, b} \ne {x_{r, b}}}}^{r - 1} f[l][k - 1] \\ &= \sum_{r = 1}^i \sum_{b = 0}^{\omega - 1} 2^{b} s[r - 1][k - 1][b][x_{r, b} \oplus 1] \\ \end{align}

当 $i \ge 1$ 时，上式还可以写为 $f[i][k]$ 的递推式如下：
$f[i][k] = f[i - 1][k] + \sum_{b = 0}^{\omega - 1} 2^{b} s[i - 1][k - 1][b][x_{i, b} \oplus 1]$

我们为方便计算，再定义一个东西：

\begin{align} s[i][k][b][w] = \sum_{\substack{t = 0 \\ x_{t, b} = w}}^i f[t][k] \end{align}

其中第四个参数 $w \in \{0, 1\}$

利用滚动数组交替计算 $f$ 与 $s$ 即得答案

数学前缀和动态规划位运算

举报

收藏

赞

评论加载中...