【比赛记录】EDU014（周测 #12）

· · 个人记录

记录

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 的方案数即可。