我没有东西吃，饿死了饿死了饿死了

· · 生活·游记

每天去了3次厕所。

“饿死了啊喵。”我心里如此想着，在省选D2T2 13:00时。所幸看起来似乎只有半小时就可以逃逸了。饿死了饿死了饿死了，在吸收了D1没带食物的教训后，我延续了D1的做法。此时监考官：“延时15min。”嘤嘤嘤嘤嘤嘤嘤嘤嘤。

喵喵喵。

我也曾追忆过去，但记忆力太差，所以只能追忆到今年的省选。但可恶的是，今年的省选我都快追忆不起来了，只能摘取零星的片段。

话说来到了神秘的省选赛场，我周围的大神都在说着甚么要AK的话，周围充满了快乐的空气，我独自神伤，似乎，只有我将迎接既定的0pts命运。

开场。

我很快注意到了collector，并且开始思考，我会 n^3，这明显是简单的。我会 n^2\log n，但我不会。我并不会 NTT，之前学习 NTT 的时候我只是连蒙带猜地乱哈气，并且对着题解抄，半年前我并没有任何对此物的理解。

但是，我觉得我可以做到场上推出此物。

我开始追忆过去了喵。

我追忆到了：

$2.f(w_{2n}^x)$ 与 $f(w_{2n}^{x+n})$ 间有某些联系。 由此推了一下： $f(w^x_{2n})=(a_1+a_3w^x_n+a_5w^{2x}_n\ldots)+w^n_{2n}(a_2+a_4w^x_n+a_6w^{2x}_n\ldots) f(w^x_{2n})=f_1(w_n^x)+w_{2n}^nf_2(w_{n}^x) 即$f(w^{x+n}_{2n})=f_1(w_n^x)-w_{2n}^nf_2(w_{n}^x)

如此一来，我就能够将问题分成规模一半的小问题了喵，我只需要将 f_1 与 f_2 求出，就可以拼出当前的神秘东西了喵！

很好，我已经差不多会FFT了，接下来我需要知道原根为何物，这样我就会NTT了喵。

事实是直到最后一刻，我都不知道原根是甚么，但我会用它，这也太奇妙了喵，最后我成功拼凑出了 NTT。

NTT 后，我注意到我不会 INTT，但注意到把 NTT 倒着写一遍就行了，我成功在 3.5h 时调出了多项式乘法。

在调了 inf 秒后，它终于不 wa 了喵，但跑出来还没 n^3 代码快，真要哭了啊喵。（collector7：n^3 代码约 3.5s，n^2 \log n 代码约5s）

其间神秘 wa 若干，此不一一阐释。

喵喵喵。

我有一种神秘的症状喵，思考的时候会发热喵，并感到饥饿，于是一直喝水，越喝越饿，饿死了饿死了饿死了，并且想去厕所，每天3次厕所，太神秘了喵。

我真的很饿啊喵。

后面两题也是随便打打下播了喵。

[0,64]+后俩具体忘了=[0,87]

并不知道 T1 会不会 MLE。

喵喵喵。

D2。

被 T1 卡了 2.5h，没救了喵。每次二分找一个数 n\log n 次 -> 正一遍反一遍 2n 次 -> 找到 0 并正反均摊 n+\log n 次 -> 找到零这东西就不能二分啊喵，直接遍历，最终优化至 n 次喵。

后面俩东西是人做的吗。睡觉喵。

。。。

睡不着，悲，在草稿纸上写暴戾语言喵。

饿死了饿死了饿死了。

饿死了啊喵！！！！！！！

推迟15min释放是人类吗。

[0,100]+0+0=[0,100]

NOIP 141pts，进队本就无望，省选瞎打。WC 和 NOIP 同分的人这辈子有了喵。

省选最大收获：我们不应该使用二分，这可能劣化时间复杂度