B Spirit Circle Observation 接着_wfx大佬提出的第一个做法讲讲我个人赛时的做法。这个做法被构造数据卡掉，主要问题是如果每次不停地走9和0可能会被卡到 O(n)O(n)O(n)。我在赛时没有考虑去证明这个暴力是否存在一个比 O(n2)O(n^2)O(n2) 低的上界，而是在想这样一件事：如果某一次我暴力走走了很多步，那就意味着存在一段很长的形如9999999999...的子段.规定一个阈值B，在SAM上只能走B步，这样可以把所有后缀9的个数小于等于B的字符串对的贡献都统计到。对于后缀9的个数多于B的，与官方题解中的关键点定义相近，只是规定后缀9的个数大于B才能成为关...