9月记录

282.CF2001

D

贪心做不明白了。

按照字典序贪心。

比如说奇数位，让颜色最大。

有一种说法是选择一个最大的颜色填入，使得填入后剩余颜色都可填入。

形式些表述，我们已经构造了 \(b_1,b_2,\cdots,b_j\)，其中 \(b_j=a_i\)，设 \(l_x\) 是颜色 \(x\) 出现在 \(a[i+1,n]\) 的最后一个位置，那么我们可以选择 \(a[i + 1,\min_{1\le x\le n}(l_x)]\) 中的任何位置，找到里面的最小/最大颜色，更新即可，可以用线段树。

E1

记 \(g_{i,j},h_{i,j}\) 分别表示深度为 \(i\) 的大根堆，使用了 \(j\) 次操作，可以进行一次 pop 的数量，以及深度为 \(i\) 的大根堆，使用了 \(j\) 次操作，的数量。

转移简单，可以用前缀和优化。

E2

可以使用两次 pop 了，需要记录每个点最大儿子的这个信息。

记 \(f_{i,j,k}\) 表示深度为 \(i\) 的大根堆，使用 \(j\) 次操作，最大儿子为 \(k\)，可以进行两次 pop 的方案数。

记 \(g_{i,j,k}\) 表示深度为 \(i\) 的大根堆，使用 \(j\) 次操作，最大儿子为 \(k\)，可以进行一次 pop 的方案数。

\(h_{i,j}\) 同理。

转移考虑 \(f\)，的两次 pop，可以两次都在同一个子树，也可以两次在不同子树，讨论一下即可。

前缀和优化，\(\mathcal O(nk^2)\)。

283.[ABC367G] Sum of (XOR^K or 0)

考虑每种异或和的方案数。

则

其中 \(x\) 作异或卷积，\(y\) 作循环卷积。

考虑 FWT，记 \(x\oplus y=\operatorname{popcnt}(x\and y)\bmod 2\)

那么 \(A'\) 中的每个位置只能是 \(1+y\) 或 \(1-y\)，即 \((1+y)^a(1-y)^b\)。

其中我们知道 \(a+b=n\)，考虑求出 \(a-b\)，得到 \(a,b\)。

然后我们只需要知道 \(a,b\) 下式子 \(y^0\) 的系数，因为 IFWT 做的是线性变换，所以次方不会改变。

根据定义，有 \(A=\sum [A_i\oplus w=0],b=\sum[A_i\oplus w =1]\)。

那么将 \(A_i\) 扔到一个桶中，做 FWT 就能得到每一位上 \(a-b\) 的值了。

时间复杂度 \(\mathcal O(nm+mV+V\log V)\)。