大家好。
我刚才做了一道题,AT_arc064_d。我想要计算长度恰好为 k 的没有周期的回文串数量,然后我想了一会没想出来。于是我往我们队伍的群里发了。
@隔壁泞2的如心 告诉我,可以用一些神秘的记数法算出来,然而我并没有听懂。这个时候,我打开了 bilibili 网站看视频去了。
到 21:05 分的时候,我发现我往 QQ 群里转的题意是错的。然后我认真的对它进行了思考。
21:24 的时候,我在群里说有没有什么容斥的方法。同时,我对我自己给出了精准的定位:智力比较低下。
到 21:33 分,我在群里说了一句什么呢,我说了一句 哦,上帝!这句话深刻地体现了我当时的心境。因为我意识到:长度为 k 的没有周期的回文串的个数 = 长度为 k 的回文串的个数 - 所有长度为 k 的因数的没有周期的回文串的个数之和。但是我竟然:
- 没有意识到这个东西不会算重。
- 没有意识到平方的复杂度是正确的。
其实我早在七点多洗澡的时候,就想到了这个做法,但是因为上面两个原因被我否决掉了。
哦,上帝!
然后我试图写个暴力证明这是正确的,但是由于懒得写 dfs 而放弃了。在 21:42 的时候,我通过了这道题。
我想以这个帖子向大家庄严的宣称:

再见。