专栏文章

题解：纯蓝

喵喵仔牛奶
P13833题解参与者 8已保存评论 9

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
9 条
当前快照
1 份
快照标识符
@mip1bfto
此快照首次捕获于
2025/12/03 04:32
3 个月前
此快照最后确认于
2025/12/03 04:32
3 个月前
查看原文

Solution

令 V=max⁡liV=\max l_i。
Lem. 1：将 aa 从小到大排序，相邻数异或值的最小值即为 f(a)f(a)。
证明
这是经典问题。可以考虑 trie 求最小异或对的过程，或者也可以证明 a<b<c⇒min⁡(a⊕b,b⊕c)≤a⊕ca<b<c\Rightarrow\min(a\oplus b,b\oplus c)\le a\oplus c，总之易证。
Lem. 2：对于长度为 nn 的序列 aa，f(a)≤2max⁡ain−1f(a)\le\frac{2\max a_i}{n-1}。
证明
考虑如果 f(a)≥2kf(a)\ge 2^k，max⁡ai\max a_i 至少为多少。
f(a)≥2kf(a)\ge 2^k 的必要条件是 ⌊ai2k⌋\lfloor\frac{a_i}{2^k}\rfloor 两两不同，因此 max⁡ai≥(n−1)2k\max a_i\ge (n-1)2^k。故 2k≤max⁡ain−12^k\le\frac{\max a_i}{n-1}，得到 f(a)≤2max⁡ain−1f(a)\le\frac{2\max a_i}{n-1}。
设 g(k)g(k) 为 f(a)>kf(a)>k 的 aa 个数，有 ∑k=0max⁡f(a)g(k)=∑af(a)\sum_{k=0}^{\max f(a)} g(k)=\sum_a f(a)。原因是序列 aa 会在 g(0),g(1),⋯ ,g(f(a)−1)g(0),g(1),\cdots,g(f(a)-1) 中计算，总共算了 f(a)f(a) 次。
枚举 kk，考虑计算 g(k)g(k)。设 ci=∑j=1n[lj≥i]c_i=\sum_{j=1}^{n}[l_j\ge i]。对于一个从大到小排序的序列 bb，由于 f(b)>0f(b)>0，bb 中没有相同的数，因此根据经典的有上限排列计数，对应的 aa 的个数为 ∏i=1n(cbi−i+1)\prod_{i=1}^{n}\left(c_{b_i}-i+1\right)。
设 fi,jf_{i,j} 为确定了 b1,b2,⋯ ,bib_1,b_2,\cdots,b_i 且 bi=jb_i=j 的情况下，∏k=1i(cbi−i+1)\prod_{k=1}^{i}(c_{b_i}-i+1) 的和。转移： fi,j=(cj−i+1)∑x=jV[j⊕x>k]fi−1,xf_{i,j}=(c_j-i+1)\sum_{x=j}^{V}[j\oplus x>k]f_{i-1,x}
DP 的复杂度为 O(nV2)\mathcal O(nV^2)，根据 Lem. 2，枚举 kk 的复杂度为 O(Vn)\mathcal O(\frac{V}{n})，我们得到了一个 O(V3)\mathcal O(V^3) 做法。
考虑优化 DP 的转移，同时转移所有 jj：
  • 枚举 j⊕xj\oplus x 与 kk 最高的不同的位 hh，要求 kk 这位为 00，令 k′=⌊k′2h⌋k'=\lfloor\frac{k'}{2^h}\rfloor，类推 j′,x′j',x'。
  • 枚举 j′j'，得到 x′=(k′+1)⊕j′x'=(k'+1)\oplus j'。
  • 可以发现 j′≠x′j'\neq x'，我们通过 j′,x′j',x' 就确定了 j,xj,x 的大小。跳过 x′<j′x'<j' 的情况
  • j,xj,x 二进制下的低 hh 位是任意的，因此将 fif_i 的 [j′2h,(j′+1)2h)[j'2^h,(j'+1)2^h) 加上 ∑t=x′2h(x+1)2h−1fi−1,t\sum_{t=x'2^h}^{(x+1)2^h-1}f_{i-1,t}。
区间加与区间求和可以通过差分与前缀和实现，这样之后将 fi,jf_{i,j} 乘上 (cj−i+1)(c_j-i+1) 即可完成转移。
一次转移复杂度为 O(∑i=0log⁡2V2i)=O(V)\mathcal O(\sum_{i=0}^{\log_2V}2^i)=\mathcal O(V)。因此总复杂度为 O(V2)\mathcal O(V^2)，可以通过。
感谢 irris提出了 Lem. 2，将此题从 O(nV2)\mathcal O(nV^2) 优化到 O(V2)\mathcal O(V^2)。
闲话：这题叫纯蓝的很大一部分原因是赛前预估这题为蓝题。

评论

共 9 条评论，欢迎与作者交流。

正在加载评论...