P8340 [AHOI2022] 山河重整
JSOI2022 联合省选游记
JSOI2022 联合省选游记摆烂寄
$\text{Day}\,-???$
开始为期 $2$ 个月的停课集训，打了 $40+$ 场模拟赛。文化课寄
$\text{NOIp}$ 考的太烂连 $200$ 都没上居然还指望着省选能翻盘。
$\text{Day}\,-7+$
有小道消息说今年疫情原因要 $\text{NOIp}$ $230+$ 选手才能参加省选（我成为最早一批开始准备 $\text{NOIp}$ $2022$ 的？）。
$\text{Day}\,-5$
正式通知说要 $210+$ 才给参加 $\text{JSOI}$。一起停课的 $7$ 个人里有 $5$ 个去不了，只有 jth 和 qlz 能去了。看来这次得在旁边看着他俩进队了。
晚上开会，教练说会举办一个同步赛让我们参加，但是不算省选成绩。
$\text{Day}\,-4\sim -1$
继续正常训练，打了 $2$ 场模拟赛，最后一场打了 $200+$，看来是把 $\text{Rp}$ 碰完了。
$\text{Day}\,-1$
事情出现反转，教练说让我们去参加考场的志愿者，并且可以到现场去考（尽管还是不算成绩）。这么说，能到现场我已经很激动了（毕竟自己太菜了，这还是第一次能去现场的省选）。
$\text{Day}\,0$
早上教练跟我们说要
Day1 保住 $150$ 冲 $200$，Day2 保住 $100$ 冲 $150$
上午写了几个板子，下午直接就去华山饭店报道当志愿者，并有幸成为第一批发现现场没有 Windows 而需要全程使用 NOI-Linux 虚拟机的人之一（尽管对我一个老 Linuxer 来说有没有 Windows 都无所谓，而且应该不会有人因为不会用 NOI-Linux 而暴零的吧）。
并且有幸膜到了即将 AKIOI 的戴老师！$\text{sto djq_cpp orz}$
然后是试机环节。作为资深小白 Linuxer，我教会了周围的几个同学们使用命令行编译和运行程序。然后我深感 VS Code 手敲命令行过于美好于是转而投向 Sublime 的怀抱。经过配置，可以 ctrl+b 编译和 ctrl+shift+c 停止程序。
晚上很早就睡了。明天 $\text{Rp++}$！
$\text{Day}\,1$
早上 $6:50$ 就起来了。$7:50$ 左右到了华山饭店，在外面等了 $20$ 多分钟才进去，期间膜了王队和 cy 等人。
$8:10$ 进入考场，敲了板子，发现自己的电脑时钟比标准时间快了 $15min$（幸好不是慢了 $15min$）。
不一会拿到题目，看完 T1 震惊到了，这不是直接模拟就能过吗？看了很久发现没有坑才动键盘。由于之前稍微了解过编译原理，所以这种字符串题对我来说也不是特别难，只需要把一行串转成一个一个 $\text{token}$ 再处理即可。$30min$ 就敲完了，过了非常水的大样例，数据不太好自己造就丢掉看 T2 了。
T2 看完不会做，而且完全不会。推了好久发现由 $L_i$ 和 $R_i-K$ 将值域分割开以后，每一段的贡献都是关于最小值 $mn$ 的多项式（不是说好的省选不考多项式吗？）。我定睛一看：好家伙，模数取 1e9+7，做个屁的多项式。然后我就只会枚举最小值做 dp 了，然后还要枚举一下路径，$O(n^2a)$，期望得分 $20pts$（连 $K$ 和 $K-1$ 容斥都没想到的我实在是太菜了）。
看完 T2 看 T3。一样的感觉不可做。$8pts$ 的 $n \le 16$ 应该是简单的状压 dp，赶紧敲完。然后想办法乱搞骗分，好像特殊性质 B 稍微好弄些的样子。于是我写了个瞎搞程序，没想到过了 $m=2000$ 的大样例（是不是太水了？）。
考试快要结束时，坐在我不远处的 jcy 对着我摇了摇头，于是我也无奈地摇了摇头。
交卷后，跟 jcy 交流得知他 T2 拿了 $40pts$，非常简单地容斥一下就能多拿 $20pts$，所以我是真的菜。还听说 T3 直接输出 $m$ 和随机排列可以拿到性质 B 的 $20pts$（我人都傻了，原来保证有解的意思是说 $Ans=m$ 啊！又犯了和 度数为 3 的点周围只有 3 个点 一样的 sb 错误）。看来 Day1 被诸神吊打了。
jcy 说 T3 状压 dp 只给了 $8pts$ 太不尊重选手了，于是他打了模拟退火。
下午没吃中饭就去考口语加试，等待时一直在思考 T2 到底怎么做。想了很久觉得还是要 $O(n^3)$ 把多项式推出来然后做自然数幂和，而且我当时觉得自然数幂和不是很好推（后来知道可以拉格朗日插值）。我考前才复习了拉插怎么当时还没想到啊啊
晚上打了会儿 generals，最后一局打上 $77.2$ 星，成功将我 Day2 的 $\text{Rp}$ 也给碰完惹。
期待 Day2.
$\text{Day}\,2$
晚上没睡好，昨天没怎么喝水导致左臂酸痛。不过好在早上就没事了。
这次比 Day1 晚了点才到华山饭店，所以没有等太久就进去了。
听戴老师说 D1T3 的性质 A 是给欧拉回路乱搞而且数据比较随机？希望能骗到分。
看了 T1 感觉好难啊！为什么今年省选只有一道可做的题啊！
$2000$ 以内质数不难想到根号分治，因为 $\le \sqrt{2000}$ 的质数只有 $14$ 个，所以考虑状压。
不难想到对每个 $> \sqrt{2000}$ 的大质数 $p$ 分类进行dp。维护 $f[p][0][S]$ 表示在所有最大的因子为 $p$ 的 $n$ 个数中，不一定包含 $p$ 但是一定包含 $S$ 集合内的小质数的方案数，$f[p][1][S]$ 表示要求一定包含因子 $p$。然后发现直接 $O(n \times 2^{14})$ 扫过去就炸掉了。
但是转念一想，这 $n$ 给到 $10^6$ 似乎是来诈骗的，因为值域只有 $2000$ 就意味着只有 $\le 2000$ 个不同的数。而 $O(2000 \times 2^{14})$ 就是可以接受的了。
然后考虑对于每个询问暴力扫一遍 $289$ 个质数，将分别维护的 dp 合并起来就能得到答案。这样的复杂度是 $O(m \times 289 \times 4^{14})$ 的，绝对要爆炸。而这个 $4^{14}$ 看起来非常不顺眼，考虑怎么优化它。发现合并两个质数的 dp 实际上就是将它们进行或卷积，于是可以用 FMT 进行优化。于是我在考场上推了 FMT 的式子（其实还蛮好推的）然后成功优化到了 $O(m \times 289 \times 2^{14} \times 14)$。然而还是过不去，注意到可以预处理出分别维护的 dp 的 FMT，所以复杂度变成 $O(2000 \times 2^{14} + 289 \times 2^{14} \times 14 + m \times 289 \times 2^{14})$，优化掉了 $14$。
这样仍然无法 AC。看到题目给了 $\sum c_i$ 肯定是有用的。将所有 $f[p][0]$ 的卷积预处理出来然后每次询问 $O(c_i)$ 进行替换，具体地，将 $dp[s]$ 除以 $f[p][0][s]$ 并乘上 $f[p][1][s]$，逆元可以预处理，复杂度变为 $O(2000 \times 2^{14} + 289 \times 2^{14} \times (14 + \log M) + \sum c_i \times 2^{14})$ 就可以通过此题。
于是我在考场上推导+码了 $2h$ 总算过了大样例，跟暴力对拍也没有出锅，于是 $100pts$ 到手！
然后开始做 T2。有了 WC2022 的经验就知道可以把括号序列转化成树。在草稿纸上画了几下发现就是转化成一条链呗，而且每个节点的贡献独立，就是原来的深度和新的深度组成的左闭右开区间 $[dep_i,dep_i’)$ 的贡献相加。
于是看到 $n=8$ 就是最裸的 $n!$ 暴力，然后 $n=20$ 就是状压 dp（这个不太好写，我最后 $30min$ 才码出来的），然后所有权值相同就是直接计算贡献，很快 $32pts$ 到手。
T3 一看就不可做，什么乱七八糟的东西，看到有 $(n-1)!$ 的暴力打完走人，$12pts$，比 D1T3 良心许多。
赛后出来交流，ducati 和我一样写出了 T1，jcy 就比较可惜。似乎 cy 也搞了 $100$ 多分。lxr 直接切掉了 T1 和 T2 成为本场标准分。%%% 但是看起来整体得分都不高啊，大部分人都 $\lt 200$ 的样子。跟 wjz 交流后得知 T1 正解就是我那个复杂度，能过。
Day2 期望得分 $144$，而且很可能实际得分比 Day1 高。
算是翻盘了吧。
$\text{Day}\,2+$
滚回去学文化课喽！
$\text{NOIp}$ $2022$ $\text{Rp}++$
