0427

今天还是打了号爸的模拟赛，T3 一个小时没调出来……只能说概率期望还是太抽象，而我又太缺少脑子了……（赛后5分钟发现T3就是个小细节错了）。

过程

花了 10 分钟看题，T1 是个简单数数题，讨论了一下，先写了个暴力验证正确性，再优化到 O(T(x+y))，大概在 8:40 搞定。

T2 要数旋转同构的东西，肯定要 burnside，然后发现求不来直接算的方案数。就写了个暴力打表，发现结果的根号是个斐波那契，就写了个线性递推快速幂，又发现在卡满的情况下要跑6s，想了一会把快速幂换成了三次根号光速幂。还发现long double乘法远没有int128快……又颠覆了我的世界观。

还剩下两个多小时刚T3，想了一下感觉很pkusc2022D1T1 rating，然后设出状态开写，写完过不了大样例，每个答案都比大样例少且只少一点点，很难绷……调了一会，决定写个暴力对拍，结果暴力写了巨久，拍出错后还是没调出来，最后就寄了。

吃完午饭回来一下就调出来了……

我是小丑，不会概率期望，/难过。

T1 Ⓥ - [模拟赛20230425] 回文 | CQNK

首先可以写出式子：\(g(n)=\sum_{i=1}^n k^i \cdot k^{n-i}\) ，这个式子与答案 \(f(n)\) 相比，如果某一个串在多个位置合法，那么就会被计算多次。

然后观察这些会被多次计算的串，手玩一下以后猜测这样的串一定存在合法串周期的，即一定是一合法串多次重复得到的。假设最小的 合法周期长度为 \(m\) 那么就会被算 \(\frac n m\) 次，令 \(h(n)\) 为最小合法周期就为自身的长度为 \(n\) 的合法串个数，则： \(g_n=\sum _{m |n } h(m) \cdot \frac n m\)，写成狄利克雷卷积的形式就是 \(g=h \times ID\)。而每个 \(h(m)\) 实际只会给答案 \(f(n)\)贡献 \(1\)，所以 \(f(n)=\sum_{m|n} h(m)\) ，即 \(f=h \times I\)。

于是 \(O(n\log n)\) 的算法就做完了，当然，可以把狄利克雷卷积优化到 \(O(n\log\log n)\)。

据说可以再此基础上硬上杜教筛：如果能快速算出 \(g\) 的前缀和，就可以筛出 \(f\) 的前缀和来计算答案。但是我好像不会算 \(g\)？

T2 Ⓦ - [模拟赛20230425] 雨 | CQNK

旋转重构十分简单：令不考虑旋转重构的情况下长度为 \(n\) 的答案为 \(F(n)\)，burnside旋转重构传统套路，答案应该就是 \(\sum _{d | n} F(d) \cdot \varphi (\frac n d)\) 。于是我们对 \(n\) 分解质因数再枚举因数，接下来就只用考虑如何计算 \(F(d)\) 就行了。

如果是一条链，那么它的 \(F\) 应该很好算：就是把 \(n\) 个位置分成若干段，每一段再选一个代表。但是是在环上，所以还需考虑 1 位置实际上是在第一段的哪个位置，所以还需再乘一个第一段的长度。这个东西线性算是容易的，然后通过打表找规律/头铁推导可以得出递推式，然后就可以矩乘了。但是如果卡满因数个数，还是会T，于是把快速幂换成三次根号快速幂，每次大概都只需算几千次矩阵乘法，然后就OK了。

T3 Ⓧ - [模拟赛20230425] 括号 | CQNK

这个题和PKUSC2022 D1T1 rating有些相似，本质思想都是为了避免环的转移，每次将往回走和走出去视为可行状态，其它的都是循环状态，然后就可以算……

好抽象，好像只有我看得懂……

具体式子比较麻烦，但是掌握了思想就能推出来吧(除了今天的我）。