题解

思路

长度不超过 $n$ 的模式串在无限循环串 $ttt\cdots$ 中出现，当且仅当它在 $t+t$ 中出现。直接枚举 $t$ 会产生指数复杂度；满分算法需要在构造第一份 $t$ 时，同时描述第二份 $t$ 在自动机上的行为。

做法

子任务 1：逐位置检查

枚举 $2^n$ 个候选串 $t$，再枚举 $s$ 的起点，并逐字符按下标模 $n$ 比较。复杂度为 $O(2^n n|s|)$。

子任务 2：KMP 扫描

仍枚举 $t$，但对 $t+t$ 做一次 KMP 匹配，把每个候选串的检查降到 $O(n+|s|)$。总复杂度为 $O(2^n(n+|s|))$。

子任务 3：双自动机状态 DP

为模式串 $s$ 建 KMP 自动机，状态 $0,1,\ldots,m$ 表示已经匹配的前缀长度，$m=|s|$ 是吸收态。

枚举第一份 $t$ 从状态 $0$ 读完后到达的状态 $r$。固定 $r$ 后，令

表示已经确定 $t$ 的前 $i$ 位；第一台自动机从状态 $0$ 出发到达 $x$，第二台自动机从状态 $r$ 出发到达 $y$ 的方案数。初值为

枚举下一位字符 $c\in\{0,1\}$，两台自动机同时沿 $c$ 转移。读完 $n$ 位后，只有第一台恰好到达所枚举的 $r$，且第二台到达吸收态 $m$ 的方案才合法，因此把

加入答案。

第一台处理第一份 $t$，第二台从第一份结束状态继续处理同一个 $t$，合起来恰好描述 $t+t$；枚举 $r$ 后每个字符串只会进入唯一一组状态，不会重复计数。

复杂度

设 $m=|s|$。满分算法时间复杂度为 $O(nm^3)$，空间复杂度为 $O(m^2)$。答案不超过 $2^{40}$，使用 64 位整数即可。