WC2020

别人在放暑假的时候，我却在参加 冬 令 营 。

不愧是冬眠营，前面四天的授课和营员交流都没听懂啥，真就冬眠去了。。。

第一天上来就是松松松手把手教你写一个路由器？

营员交流 20 分钟 100 页 ppt ？

授课讲的东西太多是 OI 无关的，营员交流信息量又太大（把课件蒯走就完事了），还好是线上冬令营，掉线了反正也重连不上，干脆颓废折腾去了。

总而言之，前四天全都在划水，一点也不夸张。所以重点就全在 Day5 的考试上了。

Day5.0

花 30min 把题目都读了一遍，感觉大概是 T1 数据结构，T2 数学/图论，T3 贪心/DP （嗯？怎么和省选 D1 有点像）。不过今年 WC 怎么三道传统题啊，昨天还在担心会不会有什么奇奇怪怪的题目。

于是 T2 -> T3 -> T1 的顺序开题。

有根树

问题很诡异，先写了个裸暴力，写完后发现可以优化，优化完后还是暴力，但是这个优化的过程让我发现了这个问题的一个看上去可做的转换。

但还是遇到了瓶颈，有一个部分很难维护，最后仍然 10 分暴力。

update: 不过由于我暴力写了很多优化，虽然上界很高但是一般数据跑不满，所以好像多水了一些分数？

猜数游戏

开场肝数学题总没错，按照题目描述的关系建图，这个图就很有性质，可以对每个团单独算贡献。想了想感觉图论的模型没错并且不难，那么问题的瓶颈就在于数学的部分，也就是怎么确定连边。容易想到 BSGS ，但是复杂度太大。如果是质数的话可以用原根来解，但是是 \(O(p)\) 的。仔细想了想发现固定底数是对多个数做 BSGS 的复杂度并不是单次 \(O(\sqrt{p})\) 的，预处理的部分可以共用。然后就写了质数的 50 分。

想了想合数 \(q^k\) 虽然不存在原根，但是如果一个数如果是 \(q\) 的倍数那么可以 \(O(k)\) 暴力枚举幂次，否则对于 \(q\) 的原根 \(g\) ，\(g\) 的幂次覆盖了所有与 \(q\) 互质的数。

意识到这个结论后感觉很 amazing ，但是不会证，不过对拍没有出错，应该是对的。

两个特殊性质给的提示还是挺明显的。

update: 事实上这个结论是错的，但绝大多数情况下成立，根据某篇论文，\(q \le 10^{12}\) 内的反例仅有 \(q=2, q=40487, q=6692367337\) 。而非常辛运的是，原题的数据范围使得这样的反例不可能出现。

选课

感觉题目很复杂，数据范围也很复杂，费好大劲才弄明白这是个什么东西。

一开始以为是费用流或者模拟费用流，否掉了，然后就没思路了，便去打 \(p=0\) 的部分分，这部分每段贪心然后背包合并就可以了，但是由于时间原因放弃了 \(\sum_s = T\) 的部分，写了 30 分。

Day5.1

卧槽听了 T2 才知道原来原根的定义就是幂次覆盖 \(\phi(p)\) 个数的数，之前一直以为只有 \(p\) 为质数的时候覆盖 \(p-1\) 个数的数才叫原根。。。

而且 \(p\) 有原根当且仅当 \(p=2 \lor p=4 \lor p = q^a \lor p = 2q^a\) ，其中 \(q\) 是奇质数。

而且这玩意还只是弱化版。。。

神仙群友，甚至不需要 BSGS ，可以利用原根证明两个点有边当且仅当它们的阶有整除关系，一个点集是团当且仅当这些数的阶相等，用试除法把每个数的阶求出来就行了，据此可以得到一个 \(O(n\log^2p)\) 的做法，可以通过第一个加强版。不过对于第二个加强版当 \(p\) 任意的时候这个做法似乎就不行了。

流下了没有数理基础的泪水。。。

T3 完全不会。

T1 连链的答案都没有注意到，自闭了。

Day6

上午的讲座听了一会，听的时候看到了一道 NOI 的提答题《旷野大计算》，卧槽真好玩，然后就咕掉了讲座去玩提答了。

下午闭幕式进不去，又咕了，在机房划水，还是通过看了闭幕式的 compu 才知道自己水到了金牌。暴力拿金，妙啊妙啊，我还以为 T1 完全把我区分掉了。

一开始听说我是 135 分，金牌线 130 ，心想自己是压线金牌了，不过完全不能理解自己为什么挂了分（我特意留了 40 分钟进行全面的检查，调试，对拍等工作以确保得分稳定）。后来又听说自己是 165 ，再后来有了数据自测又是 155 分。到现在都没搞清我的分数，不过排在了 rk11 ，湖南 rk2 ？

终于有个还算能看的排名了！