Contest Info
[Practice Link](https://www.jisuanke.com/contest/3098?view=challenges)
| 9/11 | O | O | - | - | Ø | O | Ø | O | Ø | O | O |
- O 在比赛中通过
- Ø 赛后通过
- ! 尝试了但是失败了
- - 没有尝试
Solutions
A. Attack
题意：
有\(n\)个城市，\(m\)条路可以建造，每条路有边权，现在要使得四对城市之间连通(每对城市连通就行，不用四对相互连通)，问建造路的最小代价，如果有共同的路，那么不会重复建造。
思路：
- 如果是四对城市互相连通，那么就是裸的斯坦纳树
- 那么考虑这个问题中不好处理的就是有重复边使得答案更优的情况，怎么避免重复计算贡献？
- 考虑如果在最优答案中有重复边，那么这条重复边所关联的几对城市放在一起做斯坦纳树，不会增加新的边
- 那么就暴力组合一下，更新答案即可。
代码：
B. Polynomial
题意：
给出一个多项式的第\(0\)项到第\(n\)项，询问：
\sum\limits_{i = l}^r f(i) \bmod 9999991
\end{eqnarray*}
\]
思路：
- 考虑一个\(n\)次多项式的前缀和是一个\(n + 1\)次的多项式。
- 插值出第\(n + 1\)项，就可以再插值出前缀和了
代码：
E. Interesting Trip
题意：
询问有多少条长度为\(D\)的路径中，满足这条路径上所有点的点权的\(gcd > 1\)。
思路：
我们先统计出所有长度为\(D\)的路径，然后减去点权的\(gcd = 1\)的路径即为答案。
怎么统计点权\(gcd = 1\)的路径？
我们可以考虑莫比乌斯反演，统计\(gcd \;|\; d\)的路径，即将所有点权为\(d\)的倍数的点构成的森林中长度为\(D\)的路径条数。
然后就是经典的容斥，容斥系数是莫比乌斯函数。
考虑到点权在\(10^4\)以下的数的不含有平方因子的因数最多有\(32\)个，也就是说每个点最多会被放到\(32\)个森林中，那么所有森林的总点数大概是\(O(32n)\)的。
那么考虑求定长路径条数可以用基于深度的\(dp\)解决，那么可以做到\(O(n)\)的合并。
所以总复杂度为\(O(32n)\)
代码：
F. Sequence
题意：
定义：
f(l, r) &=& \oplus_{i = l}^r a_i \\
F(l, r) &=& \oplus_{i = l}^r \oplus_{j = i}^r f(i, j)
\end{eqnarray*}
\]
给出一个序列\(a_i\)，要求支持两种操作：
- 将\(a_x\)修改成\(y\)
- 询问\(F(l, r)\)
思路：
我们发现直接去计算这个式子比较不好计算，但是注意到异或的一个性质就是一个数异或偶数次就没了，异或奇数次就是本身。
那么我们不妨去考虑一个\(F(l, r)\)这个过程最终\(a_l, \cdots, a_r\)这每个数最终异或了多少次。
打表发现如下规律：
- \(r - l + 1\)为偶数那么每个数异或次数都是偶数
- 否则，\(l, l + 2, l + 4, \cdots\)这些位置上的数异或次数是奇数，其它位置上的数异或次数为偶数
那么只需要维护两个序列，一个是奇数位置上的前缀和，一个是偶数位置上的前缀和，就可以做了。
代码：
G. Winner
题意：
有一种游戏，三个模式，每个玩家在每个模式中都有一个力量值。现在要进行\(n - 1\)轮游戏，每一轮要挑出两个未被淘汰的人选择一种模式进行决斗，
在那个模式中，力量值小的人会被淘汰，直到最后剩下一个人。
数据保证每种模式中不同玩家的力量值不同。
现在上帝可以选择每一轮游戏参与决斗的两人(未被淘汰的)，以及游戏模式，现在询问在上帝的操作下，第\(x\)个人是否可以成为最后留下来的人？
思路：
我们考虑先排个序，然后用\((a, b, c)\)表示要成为最后留下来的人的三种模式的力量的最小值，如果有人有某种大于等于这个三元组中对应的那个，那么就可以用它的其他两个属性去更新这个三元组。
按从大到小的顺序去更新即可。
代码：
H. Another Sequence
题意：
给出一个长度为\(n\)的序列\(a_i\)和另一个长度为\(n\)的序列\(b_i\)，现在\(c_i\)的生成方式如下：
- \(c_i\)的长度为\(n * n\)
- \(c_{i * (n - 1) + j} = a_i | b_j\)
- 将\(c_i\)升序排序
现在要求支持两种操作： - 将\(c_i\)中\([l, r]\)区间内的数开根
- 询问\(c_x\)的数值。
思路：
- 对于\(c_i\)数组，我们肯定不能直接生成它，但是注意到\(1 \leq a_i, b_i \leq 10^5\)，那么\(c_i\)中数的种类不会超过\(2 \cdot 10^5\)，那么我们可以用\(FWT_or\)处理出每个数的个数
- 那么对于询问，我们只需要处理出\(x\)位置上的数被开根了多少次，然后找到原本\(x\)位置上的数是什么即可
- 我们考虑\(x\)位置上的数被开根了多少次？即在它前面出现的操作\(1\)中，\(l \leq x\)的区间个数减去\(r < x\)的区间个数
- 考虑怎么找到\(x\)位置上的数是什么，维护一个前缀和，表示前\(i\)个数的出现次数，然后直接二分。
代码：
I. Hamster Sort
题意：
给出一个排列\(p_i\), 给定一种排序操作：
- 选择一个\(k\)，令\(p_k = 1\)，\(T = 1\)
- 然后遍历序列\(a_i\)，寻找\(p_k\)
- 如果找到了，就令\(p_k = p_k + k\)，遍历指针往后挪一个位置，然后回到步骤\(2\)
- 如果没有找到，就令\(T = T + 1\)，然后遍历指针指向序列的开头，回到步骤\(2\)
现在要支出两种操作：
- 交换\(p_x\)和\(p_y\)
- 给出\(k\)，询问上述排序操作的\(T\)是多少
思路：
- 考虑\(k > \sqrt{n}\)的时候，我们可以直接暴力跳，不会跳超过\(\sqrt{n}\)次
- 考虑\(k \leq \sqrt{n}\)的时候，\(k\)的取值只有\(\sqrt{n}\)种，可以直接预处理答案，交换的时候注意一下\(a_x\)和\(a_y\)都是同一个\(k\)的情况的贡献不要多加或者多减
- 预处理答案的时候把\(1\)的贡献剔除出来，最后再加上即可
代码：
J. Prefix
题意：
给出\(n\)个字符串\(s_i\)：
- 维护一个字符串集合，把这个字符串加进去。
- 再将所有字符串替换成他们的\(|s_i|\)个前缀。
定义一个字符串的困难度为：
\prod\limits_{i = 1}^{|str|} d_{str_i} \bmod m
\end{eqnarray*}
\]
现在询问每个原字符串在那个字符串集合中，有多少字符串是它的前缀，并且困难度比它高？
思路：
先将所有字符串\(Hash\)，存入\(map\)。
然后遍历每个字符串的前缀，如果前缀的困难度比它本身高，那么就统计有字符串集合中有多少个这样的前缀。
代码：
K. A Good Game
签到题。
代码：