总 复杂度证明比起 SAM 较简单（虽然我还是没想出来），用学长魏忠浩的一句话就行了： 考虑当前点 fail 指针指向的节点的长度，跳一次至少减，插入至多加常数 难点在于代码细节，想不去讨论初始情况的一坨就必须注意细节。 CODE fail 必须在 ch 之前算，而且偶数根必须是 0，这样单字母的节点才可以老老实实把 fail 指向 0，也才不会出现一个点莫名其妙就把 fail 指针指自己。 #include<bits/stdc++.h>#define fru(i,j,k) for(int i=j;i<=k;++i)#define frd(i,j,k) for(int i=j;i>=k;--i)#define pc(x) putchar(x)#define fio(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout)using namespace std;using ll = long long;namesp ...

总 这是个人向笔记的第一篇。 个人向笔记主要为了自己看懂，初学的读者建议看 OI Wiki。 当然，遇到和我相同的困惑点可以阅读。 我学习的时候遇到的困难无非正确性和复杂度证明。 状态数和转移数的证明倒是很简单，OI Wiki 也讲得相对详细。 正确性证明 设 SSS 为一个字符串，ccc 为任意一个字符。 代表 SSS 的点和代表 ScScSc 的点之间一定有边。 SSS 的 ccc 出边的点对应的字符串一定以 ScScSc 作为后缀 初始节点到每个点的路径集合就是这个点的字符串区间集合 现在的所有点就是 parent tree 中的所有点 正确性的证明只要盯着这些个结论证就可以了，具体方法就是一步步对照构建方法是否能维护这些性质，而有这些性质 SAM 的合法性是显然的。 复杂度证明 其他都可以看 wiki，但是复杂度中没有新建边或点的那一部分的证明，wiki 上写得极为简略。 记号见图（图中为 aaba 加上 b 后的结果，显然为 case3，注意 depltdep_{lt}deplt​ 就是上一次的 depudep_udepu​）： 设 depdepdep ...

总 100+100+0=200100+100+0=200100+100+0=200 分，9/229/229/22 名。 T1 H2O\mathrm{H_2O}H2​O T2 PAM 的结论和最小链覆盖缝在一起的唐题。 T3 提交答案题竟然 0 分，大失败！ 前两题花了比较多的时间，这题只剩不足半小时。 我赛后又额外想了 1H10min 没想出 P 是质数那个部分，因为一直在想这个部分所以 T3 没有分，看来这么久没学数论的我就不该对自己太自信，剩下一点时间提交答案题的前几个点搞一下弃赛才是正道。

质因数分解 A∗BA*BA∗B 只要分别分解 A,BA,BA,B 然后吧相同的质数指数相加就可以了。 把 AAA 个东西分成两堆共有 A+1A+1A+1 种方案，所以指数加一在相乘即可。 注意分讨 >A>\sqrt A>A​ 或 >B>\sqrt B>B​ 的质因数。 CODE： #include<bits/stdc++.h>#define fru(i,j,k) for(int i=j;i<=k;++i)#define frd(i,j,k) for(int i=j;i>=k;--i)#define pc(x) putchar(x)#define fio(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);using namespace std;using ll = long long; namespace ugi{char c=' ';ll in(voi ...

总 100+90+40+0=230100+90+40+0=230100+90+40+0=230 分，11/1911/1911/19 名。 怎么一堆人 300300300 分啊，不过在没有 A 出前 3 题的人中排第二。 应该赛时还是搞出了不少有用思路的，但人菜，救不了。 反思：纯菜，LQH，HYT 和一票学长 300300300 多分，我完全被吊打。 T1 搞了快两小时，想得属实有一点太久，考虑的时候就应该从这种消元而又不能直接上高斯的形式中开始手动消元，然后一步步降维的想法就出来了。 T2 我写的假做法最像真做法的一集。 swap(x,y) 后乱跑竟然有 909090 分，数据最假最弱的一集。 T3 T4 不怎么看得懂，剩余时间考虑 T3。 拿了所有有特殊性质的分，听说随机能过掉 n⩽105n\leqslant 10^5n⩽105 的点，我的随机看来比较弱，只过了 subtask 里的 11 个点。 不过拿到 60 分的两位提交次数是不是有点多了…… T4 最后的时间，我选了 T3，真抱歉 QWQ。

总 100+100+0+0=200100+100+0+0=200100+100+0+0=200 分，18/2418/2418/24 名。 我最唐的一集，同时也是 cjwen\color{red}\texttt{c}\color{black}\texttt{jwen}cjwen 最强的一集，他阿克了。 反思：以后 A 完 T1 不要只会纲 T2，容易陷入思维定式，卡死就寄了。 这次 cjwen\color{red}\texttt{c}\color{black}\texttt{jwen}cjwen 就先搞的 T3，以前也有一次他 T2T3 都拿了不少部分分，于是加起来比我 A 了 T2 还高。 T1 水，在 T1 中都是水的。 T2 开始纲，没想到一直纲到了第三小时，贪心和随机都没啥头绪，这才意识到可以上欧拉回路过掉偶数的部分分，然后正解就出来了。 T3 上 DP，还假了，不如拿纯度暴力，这样还有分。 T4 没怎么看，前面都烂完了 😢 。

总 100+100+100+0=300100+100+100+0=300100+100+100+0=300 分，7/257/257/25 名。 666 个第一，555 个第7，最没有区分度的一集。 反思：前面题被诈骗了搞得有点旧，T4 没有分，这不好。 T1 相似裸题，差点全场 AC，可惜有个人 707070 分。 T2 题面写的十分抽象，被硬控 909090 分钟后发现 chy2021\color{black}\texttt{c}\color{red}\texttt{hy2021}chy2021 AC了，觉得这题应该可做，然后就突然发现一个点的子节点最多 222 个，然后暴力 DP 结束硬控。 T3 相比 T2 反而不怎么诈骗？ 线性的概率 DP 很好推，然后分成两段优化即可。 T4 没时间看。

总 100+100+45+0=245100+100+45+0=245100+100+45+0=245 分，4/224/224/22 名。 第 444 名都有 555 位，最没有区分度的一集。 T1 硬控我快一个小时，想了各种奇葩，最后发现是前缀和。 T2 一眼边权为 111，有用点也不多，那连图都不用建出来了，直接BFS就可以了，用时比 T1 还少（真·T1）。 T3 暴力边DFS边KMP拿到 454545 分，然后正解就各种抽象了…… T4 试图暴力，没调出来。 恭喜这题拿到分的 Zaunese\color{black}\texttt{Z}\color{red}\texttt{aunese}Zaunese 和 Watware\color{black}\texttt{W}\color{red}\texttt{atware}Watware。

总 100+60+0+0=160100+60+0+0=160100+60+0+0=160 分，14/2214/2214/22 名。 cjwen\color{red}\texttt{c}\color{black}\texttt{jwen}cjwen 拿到了 300300300 分，非常厉害。 T1 没啥好说的，暴力题。 T2 写了一个显然的决策单调性拿了 606060 就走了，没想着继续考虑特殊性质，于是没想出“每层一个转移点”的结论，成功被诈骗题诈骗掉 222 个小时还没做出来。 T3 相比以前正解已经不算完全不可做了，但我只想了链分，还没调出来，最失败的一集。 T4 哈，看都没时间看。

总 100+100+5+10=215100+100+5+10=215100+100+5+10=215 分，12/2212/2212/22 名。 最有素质的一集，但我比较摆，一题都没做过（来自赛时公告）： 各位同学请注意，距离比赛结束还有半小时，下面是一则公告： 为了比赛的公平性，如果再次出现多个题目通过速度超过原题场上所有人之类的行为，并被认定为作弊，将被 unofficial！ 孩子们，这并不好笑。 T1 裸的 DP 没啥好说的，一开始前缀和优化还把 n 维毫无必要地加进去，MLE 卡了一会，难绷。 T2 搞了半天，想出了 n+m−4n+m-4n+m−4 和 max(n,m)−(min(n,m)/2−1)max(n,m)-(min(n,m)/2-1)max(n,m)−(min(n,m)/2−1) 两种东西，然后缝在一起就过了，难绷构造题。 T3 拿了送的 555 分，本来想纯度暴力多搞 101010 分，没搞出来，最菜的一集。 PS：赛后发现简单 DP 还可以再拿 303030 分，太难绷了。 T4 有送的 101010 分，不拿白不拿。