题解

思路

母串长度为 $3\times10^{10}$，并以 110 为周期。

做法

一个起点只由其下标模 $3$ 的余数决定，因此枚举余数 $r=0,1,2$，检查每个 $T_i$ 是否等于周期串在位置 $(r+i)\bmod3$ 的字符；不匹配的余数没有贡献。

若余数 $r$ 匹配，合法起点还需满足 $r+3k\le3\times10^{10}-N$，直接由等差数列项数公式计算其贡献。

复杂度

三个余数的贡献之和即为答案，时间复杂度为 $O(N)$，额外空间为 $O(1)$。