STRFFT 的意思是不是 街首

NewMarchqwq · 2025-11-28 19:39:55 · 题解

快速卷积匹配就不说了，之前训卷积的时候做过很多个这样的题目，套路就是 sigma 条件转艾弗森括号后进行和、差卷积匹配，或者对哈希值进行匹配。可以参考 P4173 和 qoj11617 等。

但是你让我 noip 前随到这种题被诈骗一小时也是太恶心了。

那么我就讲一下周期相关的事情。现在题解区里大家对“哪些长度是周期”的认知还是“先去掉一定不可能的，再推理矛盾的”，这里给出一个通用的结论。

• 【结论】一个字符串 s 有周期 d 当且仅当下面条件不成立：存在 1\le i<j\le n,s_i\ne s_j，有 d\mid (j-i)。当然像本题的问号之类的通配符之类的不算不等（下面记作“\sim”）。

需要注意当周期被规定为满周期的时候显然还要加个条件就是 d\mid |s|。接下来证明上面给出的结论。

充分性： 即若条件不成立一定有周期。考虑对于所有 0\le r<d，根据不存在 kd=j-i=(k_2d+r)-(k_1d+r)，一定有 s_r\sim s_{r+d}\sim \dots\sim s_{r+md}（其中 x\sim y 表示他们要么相等要么有通配符在里面，如上文所述）。因此满足周期性质。

必要性： 若条件成立，设 d\mid (j-i)=T，且 T 是最小的满足这个条件的数。那么归纳。若 d=T 显然 d 不是周期；否则一定有 s_{i}\ne s_{i+d} 或 s_{i+d}\ne s_j，故 T 非最小，矛盾。

因此得证。我们只需要卷积出所有 j-i 之后标记它们所有因数即可。使用枚举倍数被动获得 tag 的方法，可以做到和 NTT 一样的复杂度，因此本题复杂度 \Theta(n\log n)。

反思： 一个很有意思的点在于其他题解一直声称本题“问号不是通配”，这只是对周期的性质不了解。当串完好的时候，若 s_i\ne s_{i+2d}，那么一定有 s_i\ne s_{i+d} 或 s_{i+d}\ne s_{i+2d}，因此只将所有的 (j-i) ban 掉也是能够通过；但是像这个题，就需要深入挖掘周期的性质，ban 掉所有 d\mid (j-i)。这样子就不用被通配符迷惑了。

NOIP 2025 RP++