5.24 被卡常了

· · 个人记录

A

维护前缀和直接查，复杂度为 \mathcal O(n)

B

考虑 i\to j 的贡献，等价于 i 走到 j 的路径条数，如果为奇数那么有贡献。

写出来邻接矩阵 A，初始矩阵 T，我们等价于计算 T\cdot A^{t} 的每一项 \% 2 的值。

注意到只有 0/1，那么将运算改为位运算就可以使用 bitset 优化做到 \mathcal O(q\cdot \frac{n^3\log n}{32})

貌似可以通过预处理次幂矩阵然后通过向量 \times 矩阵乘法做到 \mathcal O(n^3\log n+qn^2\log n)，不过懒人没有心思写了。

C

首先把 0 去除掉，问题等价于允许使用若干个数，使得任意两个数 \rm and 值为 0，求或值 =x 的方案数。

注意到 \rm and=0，或值 =x 的形式很像子集 dp / FST，本题范围较小，通过限制最后一个填入的数的最高位和 S 相同的方式可以轻易去重，复杂度为 \mathcal O(3^{17})

不知道为啥逐渐觉得没啥意思了......