XIX Open Cup named after E.V. Pankratiev. Grand Prix of Siberia, Division 1.

Problem A

Solved by Xiejiadong. 0:14 (+1)

题意：判断一个数是否是其他数的乘积。

题解：判断一个数是否是其他数的乘积可以通过一个数的平方是否是所有数的乘积得到。

需要特判 $0$ 的情况。

因为每个数都不超过 $10^9$ ，所以如果乘积的过程中绝对值超过了 $10^{18}$ ，一定无解了。

Problem B

Solved by Kilo_5723. 4:23 (+16)

Problem C

Unsolved.

Problem D

Solved by Kilo_5723. 0:28 (+)

Problem E

Solved by Weaver_zhu. 3:59 (+7)

Problem F

Unsolved.

Problem G

Unsolved.

Problem H

Unsolved.

Problem I

Unsolved.

Problem J

Solved by Weaver_zhu. 0:36 (+)

Problem K

Solved by Xiejiadong. 2:00 (+)

题意：一个类似于分形嵌套构造的电路板，给出第一层的构造方式，求最外面的借口主要通过几个嵌套才能联通。

题解：我们对一开始有的边，设他们的边权为 $0$ ，因为通过他们直接连通的最外面的借口，显然只需要 $0$ 层嵌套。对于通过这些边连起来的最外层接口，显然可以在下一层的嵌套中直接连通。

也就是如果当前在第 $x$ 层嵌套中，有一对新的最外面的接口被联通，那么可以增加 $s$ 条边权为 $x+1$ 的边联通子模块中的这两对点。

如此构造，我们可以发现，联通 $k$ 个接口最多发生 $k-1$ 次，于是最多新增加 $s(k-1)$ 条边，而合并的操作最多显然执行 $(n-1)$ 次，那么对于这一过程，直接暴力处理即可。

接下来，我们可以在上面的合并过程中记录下所有合并的时候的边，于是就会变成一棵树（可能是森林，因为会有不联通的情况）。可以发现，对于询问，答案就是询问的那对边所在的链上的最大值（即这对点至少要在第几次嵌套的时候才会被联通）。

直接处理的话，可能需要树链剖分，我们考虑把所有的询问离线放入每一个结点，在合并的时候顺便处理询问，这样的时间复杂度就是 $O((n+q)logn)$ 。

Problem L

Solved by Xiejiadong. 3:54 (+7)

题意：可以将给定的字符串任意拼接，使得拼接后的字符串中本质不同的子序列个数为偶数。

题解：$n=20$ ，任意的拼接，显然可以通过状态压缩来做，关键是考虑如何本质不同的子序列个数位偶数的情况。

考虑求一个字符串中本质不同的子序列的方法：$f[i][j]$ 表示前 $i$ 位中，以字符 $j$ 结尾的本质不同的子序列个数，显然转移方程式：$f[i][j]=\left\{\begin{matrix} f[i-1][j] & s[i]\neq j\\ \sum_{j=a}^{z}f[i-1][j]+1 & s[i]=j \end{matrix}\right.$ .

可以发现对于 $f[i][j]$ 中同样的 $i$ 里面，至多只有一个奇数，于是我们可以用一个状态来表示奇数的位置，用 $0$ 表示全部都为偶数。

于是可以预处理出每一个字符串的以字母 $j$ 作为结尾的状态里面奇数出现在位置 $g[i][j]$ ，之后状态压缩转移即可。

有点卡常，需要各种位运算技巧。