快乐 HDU

· · 个人记录

team1121。

NOI 之后才开始打，号是从学长那里抢过来的学长给的，队友是 xzy 和 cjzyf，感谢他们愿意组队打这个 hnsdfz 的号。

第五场

这一场只有我和 xzy 打。

拖后腿了。

我开奇数题，xzy 开偶数题。

刚开场感觉没什么可做的题。看了一会儿之后发现 1007 过的人多，于是先去把 1007 过了。xzy 在冲 1002，估计是想抢个首杀。于是我就去做做签到，把 1012 1001 1009 1006 过了。xzy 很早就写完 1002 了，但是一直在卡常，我过完 1009 之后 xzy 就把 1002 过了，然后他去开 1005，我去开 1003 / 1004 了。这 1003 / 1004 怎么一个 pam 就搞完了，这么傻呗吗。花了不到半小时过了，这之前 xzy 已经过 1005 了。

1.5h 九题！来到排名巅峰 rk4！

只剩下 1008 1010 1011。决定先开 1008。xzy 猜测答案为 m 次多项式，但是我感觉不像，打表之后否定了。这时我发现 1008 其实就是组合数问题，然后多项式是伯努利数。组合数问题有 \mathcal{O}(m \log m) 做法吧？但是好像要多项式快速幂，感觉过不了啊。不管了，先擓一个代码开冲。经过很久之后过样例了，但是一组数据要跑 6s，寄。期间 xzy 开了 1010 并编出了 \mathcal{O}(n \log n \log V) 做法，我觉得很对，他就开写了，但是又被卡常了！！！

我觉得是我的多项式板子太慢了，尝试现场修改多项式板子，但是无果。尝试擓别人的多项式板子，无果。我在这里浪费了很久的时间，根本没有去想能不能优化做法。xzy 1010 一直在被卡常，非常难受。于是我建议他先去开 1011，他编得很快，但是写完发现又被卡常了。

很厉害，现在手上三个题全部被卡常。

xzy 1011 把 map 换成哈希表就过了，过了一会儿之后又把 1010 卡过去了，很厉害啊！！但是我一直没有卡过 1008，最后差一题阿克。最终排名 rk16，我们是排行榜上第一个没有过 1008 的队。拖后腿了！！！

后面看题解，看到 如何优雅地求和，发现我推的式子跟这个题完全一样，但是我忘记这个题了！！不过用这个题的做法也能做组合数问题，为什么后者题解中只有一篇使用多项式快速幂的 \mathcal{O}(m \log m) 做法的题解呢？

第六场

贡献大部分罚时。

xzy、我、zyf 分别开 \bmod \ 3 = 0, 1, 2 的题目。

我一上来开 1001 发现是傻呗题，但是降智怒拿三发罚时。之后看 1010 比较傻呗，写个倍增过了；又看 1004 比较傻呗，写个点分治，wa 了，发现忘记处去掉每个分支内部的贡献了，改完之后就过了。

此时队友已经把 1002 1006 都过了，并且在写 1005，我就去开 1008。以为数据范围是 10^5 想了好久，结果看到 3000 直接傻眼了。编了个 \mathcal{O}(n^2 \log n) 做法，t 掉了，想了想改成 \mathcal{O}(n^2)，过了。

队友不会 1003，于是我去看看。说起来去年杭电这种三维计算几何都是丢给我做的。

猜了个结论：若有解则必然存在一组解满足系数非 0 的向量线性无关。于是就简单了。写了一段时间，wa 了，上拍，改改改，改完过了。

此时还剩下 1007 1009 1011 三个题。我和 xzy 开 1007，zyf 开 1011。

做了很久不会。但是 zyf 很快就把 1011 切掉了！！很厉害啊！！！

讨论了一下要不要通过套数据过掉 1007，然后发现时限太长了，以至于可以通过卡时用 3 次提交确定一个 10^5 范围的数，于是决定开整。zyf 来套数据，而我已经把暴力写好了。不久之后过了。

只差 1009 了！很舒服啊！

但是这个 1009 题意怎么那么阴间啊？xzy 说可能是对偶什么的，我也往对偶的方面想，但是想不出什么东西，感觉没什么可以利用的性质。

看一眼榜，只有一个 nfls 队和一个杭二队过了，那大概是不可做的。换方向思考将近一小时无果，开摆。

最终排名 rk4，还是不错的，没有拿过这么高的名次。

第七场

今天是真的战犯了。

和上一场一样的开题分配，但是我手上的题好像没一个可做的。

过了一会儿有人过 1011 和 1002，队友开了 1011，我就去看看 1002，秒掉了，过了。开 1013，观察一会儿之后发现就是可以任意异或 \equiv 0, 1 \pmod 4 的数，那就只用考虑二进制的 2^1 这一位了。写，wa，发现没判 1，改，过。

这时候 zyf 在冲 1005，没多久就过了，然后拿到了手刹，很快啊！

xzy 刚开场就秒掉了 1006，因为精通离散对数所以很快也过了，又拿了个手刹，膜拜！

然后我开 1010，麻了，怎么跟广为人知题这么像。往基本子串结构的方面想，但是觉得这个题实在是和基本子串结构不搭，其实是我啥都没想出来，就放弃了。想能不能直接 sam，无果。放弃。

然后我去开 1008，队友去开 1004 1012 和其他题。编了个很傻呗的贪心，wa 了。改了个错误之后还是 wa，于是求助。xzy 说可能需要舍弃最优解往下走来逼迫对手做出更劣的选择，zyf 说可以模拟博弈的过程。我恍然大悟！改改改，wa 了一发，又因为没删调试 ole 了一发才过。

好像队友不会 1004，我去看看。感受了一下，答案至少是根号级别。队友搜出了 n \le 13 的答案，去 oeis 上找，没找到什么靠谱的。自己编了一个方案，大概是用 2 \ 2 去分割 1 \ 3 \ 1 \ 3 ...，发现和队友之前编的一样！看这么多队过，直接猜测这就是最优方案，写个二分，wa。发现有细节可以优化，改了改，过了。

zyf 不知道什么时候把 1012 过掉了。这时候还不到 3h，只有我们 8 题，来到 rk1！主要是 1006 没什么人过。

然后看剩下的题中只有三个 998244353 有人过。我去开开 1003 和 1007。1003 感觉太神秘了，1007 有点搞头。编了个类似 Japanese Knowledge 的做法，但是要下降幂多项式转普通多项式，以及多点求值！不说能不能跑过去，我前两天才重构的 poly 板子中还没来得及加上这两个东西，并且 Japanese Knowledge 和下降幂多项式转普通多项式我从来没有写过啊！但是 1003 实在不会啊，1009 1010 队友在看，于是硬着头皮开写。

写了一会儿之后被一些细节搞得很烦，重构了 >1 次，但是依然花了很久的时间。期间 1001 好像突然过了很多人，队友去看，好像秒掉了，于是我继续写。下降幂多项式转普通多项式直接用无脑快速插值吧？我真的怕常数太大啊。不管了没时间了先试试吧。过了一万年之后终于过编了，样例肯定是 wa 了，不管，先测速，发现测速也寄了，毫无希望。无论是改下降幂多项式转普通多项式还是先把代码改对时间都不够我用了。于是围观 xzy 写 1001，可惜他到最后也没调出来。

以为寄得很惨，结果打开榜居然能够还在 rk2，尤其是银河战舰这场好像被 1006 困了很久，只有一个杭二的队在我们上面。

rk2 完全归功于队友。这场我的发挥只能说是个谁来都行的签到机器。下一场不能这样了！！！

第八场

答辩场。

和上一场一样的开题分配。

我一上来开 1010，因为题面最短，然后好像秒掉了啊！于是开写。写到一半发现好像假了，又瞪了一眼，发现可以直接分类讨论，然后过掉了。

期间队友说 1007 比 1010 还签，然后帮我签了。然后队友去开 1005 1006，我去开 1004。但是 1004 好像不会啊，发现过的三个队都是杭二的，不排除科技题可能性，于是就去看 1001。怎么 1001 又是离散对数啊？找 xzy 要了个板子，再擓了个任意模数 NTT 就过了。

但是队友开两个题好像没过，于是我去看看 1005。猜一手状态数很少，自信提交，t 了。发现没记忆化，加上之后自信提交，又 t 了。然后发现 \texttt{101010...} 这种简单数据就能把我叉掉，难受。再观察了一下，发现博弈的策略是简单的，不需要 dp，正好之前写了暴力，写完新做法和暴力拍上了就交，然后过了。

那你的至多 50 组数据 n > 100 有什么用呢？

xzy 开 1006，但是好像看小范围了，以为单组数据只到 10^6，开了若干 vector。但是不久之后发现可以直接哈希做，于是就交给我开写，他去开 1008，然后直接秒掉了，花了不到五分钟过了。

现在的情况是：我写 1006，队友开 1004 和 1009。

不久之后写完了，一交上去发现 t。于是尝试卡常，卡到本机 1.5 s 左右再交，还是 t。于是继续卡常，卡到本机 0.7 s 左右再交，还是 t。

期间队友把 1004 和 1009 秒掉了。不知道什么时候 1002 突然过了一堆人，但是看榜发现其实还是只过了 3 个。于是我自信跟队友说 1006 没问题，他们就去开 1003。

现在的情况是：我卡 1006，队友开 1003。

队友好像会得挺快的，框框就过了。但是我还是没有把 1006 卡过去。

时间剩得不多了。队友说试试改成单哈希，于是我就去改自然溢出，想着 wa 总比 t 好。

很快改完了，交，还是 t。

很厉害啊。

继续卡，把代码改得面目全非，把代码改得支离破碎，还是 t。

队友也开始帮忙卡，无济于事。

现在的情况是：三个人一起卡 1006。

代码中已经没有取模了，也把那些差分求哈希值的操作都改成边循环边求了。哈希表？那真不是瓶颈。

但是还是 t。还剩 5 秒，还剩 4 秒，还剩 3 秒，还剩 2 秒，还剩 1 秒，结束了。rk20。

第九场

这一场只有我和 zyf 打。

我开奇数题，zyf 开偶数题。

首先我和 zyf 分别把 1005 和 1002 签了。之后看到 1011 有人过，就去开 1011。想了一会儿没有结果，准备放弃的时候发现 直接容斥就行了，然后立马开写，很快过掉了。

zyf 在卡 1004 的常，我先去开 1007。一个显然的性质是答案的长度不会超过 2k。立马可以得到一个 \mathcal{O}(n k^2 + q k^3) 的做法。具体来说就是维护每个点往下走 i 步的最大值和次大值，修改的时候暴力维护即可。但是我 没有看到 q \le 10^4，以为这个东西过不了。但是想着正解必然是基于这个做法的，于是就先写了，看看能不能优化。写完之后交了一发，果然 T 了。

发现 1008 过了一车子人，于是去开 1008。想了一年之后想到可以对于每个人计算涉及到这个人的交换次数的期望，变为 n = 2 的问题，之后又想了一年，才发现 a_1 = x, a_2 = y 的期望步数就是 xy。感觉这个东西实在是太典了，为什么我会不知道呢？因为没有清空 ans wa 了一发才过。

回来看 1007，猛然看到 q \le 10^4，意识到我当前的做法就是对的。突然看到我的分数类构造函数中硕大的 __gcd，此乃复杂度平添 \log 之术。去掉之后又交了一发，wa 了。改了改再交，还是 wa。看不出什么错误，写个拍，过了半个小时左右终于过拍了，然后过了。

zyf 好像还在卡 1004 /ll

于是我去开 1012，发现英语水平低下，完全读不懂题意。尝试猜测题意，但是感觉不对劲，于是放弃了，让 zyf 在过了 1004 之后去开 1012。

我去开 1009。编了一下，发现每个 \bmod \ n 的剩余类只有两种选择，即全选奇数位置和全选偶数位置。于是问题变成了一个类似于环染色的东西。推了一会儿之后没什么结果，因为还有两端的颜色段长度和 < d 的限制。过了一年之后终于意识到可以常系数齐次线性递推，但是这个东西我的新 poly 板子还没加上去。于是把重构之前的代码拉过来，发现巨慢无比。拉了个快的，能跑了。交了若干发，都是 T，我一度十分怀疑 hdu 机子的速度。但是之后发现竟然是我的 read() 没开 long long，在 n 大的时候就直接寄了。

改过来了，但是为什么还在 wa。

看不出错误，又硬着头皮写了个拍，拍出错来了。但是已经不剩什么时间了，我这么急急急自然看不出错误。期间 zyf 把 1012 过了，但是他好像还是没有把 1004 卡过去 /ll

于是今天 6 题下播，纯纯娱乐选手，rk23 再创新低。

结束之后我就发现自己常系数齐次线性递推的初值预处理错了！改过来就过掉了 /ll/ll

第十场

这一场只有我和 zyf 打。

今天我们两个想尝试一点新的打法，然后寄惨了。我在 1005 和 1011 之间反复横跳，一个编了巨大复杂做法，另一个不断枚举假做法。最后我摆烂了，被我校二队薄纱。