模拟赛 8 题解

哈希+对顶堆+倍增+矩阵乘法+dp+MTT

A.完全平方数

判断几个数的乘积是完全平方数：每个素因子的出现次数是偶数。

考虑一个新加的数，如果我们把它素因子的 $val$ 都异或 $1$。

那么判断一种方案是否合法，只需要看是不是所有 $val$ 都为 $0$，即前缀异或为 $0$。

考虑到异或出来只有 $0$ 和 $1$，我们考虑状压解决这个问题。

但是 $\pi(10^5)=9981$，位数太多不好处理。

那么我们可以选择一个大质数 $P$，每次把压好的状态 $\mod P$，这样就达到了 $Hash$ 的效果。

我们在得到一个新的状态时，要先加上它之前的出现次数，再更新它的次数，这个可以用 $map$ 维护。

每次把新加的质数对应的状态都异或一遍就好了。

B.K优先队列

正解是对顶堆，这里我采用平衡树实现。

C.宝藏

观察题面给出的串，可以发现它是通过倍增来构造的。

考虑到 $n\leqslant 500$，我们想到可以用矩阵乘法来表示每次的行走过程。

可以构造两个矩阵，一个只包含 $1$ 边，一个包含 $0$ 边，那么我们可以通过这两个矩阵互相乘来构造走 $2^i$ 步的转移矩阵。

统计答案是能走就走，记录上一次走得是哪边的矩阵，最后记录步数即可。

记得用bitset优化。