本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-20 10:59:42

记录

BC 恶心题一共被卡一个小时，DEF 切得挺顺的，总体不难。

题解

B. s-palindrome

预处理出所有本身左右对称的字母，判断左右对应位置字母，要求是 pq 或 bd 或相同且自身对称，同时若长度为奇数，正中间的字母本身也需要自身对称。

C. Exponential notation

基本分讨，分别处理小数点左右两边，略过不表。

D. Swaps in Permutation

发现如果把 $u,v$ 可交换看作 $u,v$ 之间连了一条边，那么每个连通块内的元素都可以任意交换。用并查集维护连通性，在每个连通块中尽可能用大的 $p_i$ 填到小的 $i$ 中，这样字典序一定最大。

E. Xor-sequences

从朴素 dp 入手，设 $f_{i,j}$ 表示填了 $i$ 个数，第 $i$ 个数是 $a_j$ 的方案数，有转移 $f_{i,j}=\sum_{k=1}^n[{popcount(a_j\oplus a_i)}\mod 3=0]f_{i-1,k}$，发现系数一直不变，可以用矩阵优化，把系数填成转移矩阵，用矩阵快速幂加速即可，时间复杂度 $O(n^3\log k)$

F. Couple Cover

发现 $a_i$ 值域以及询问值域 $P$ 很小，所以先开桶 $t_i$，枚举倍数也能维护出 $[1,P]$ 内所有数会作为乘积多少次，时间复杂度 $O(P\log P)$。计算答案时考虑容斥，先把上面所说的次数预处理前缀和 $s_i$，用总方案数 $n(n-1)$ 减去询问的 $s_{k-1}$，也就是不到 $k$ 的方案数即可。