题解

思路

一局进行途中只有四种比分：$0:0,1:0,0:1,1:1$。一个字符对这四个状态给出确定转移，并可能产生一次 Alice 胜局（权值 $+1$）或 Bob 胜局（权值 $-1$）。一个完整周期串因此给出四点函数图以及四条带权边。从初态 $0:0$ 出发最终进入的环，其边权和符号决定长期胜负；进入环前的有限前缀不影响极限。

做法

子任务 1

枚举全部问号替换，构造四点带权函数图，找到从初态可达的环并判断环权和符号。复杂度为 $O(2^q|s|)$。

子任务 2

从四个起始比分同时读取模式串。状态完整记录四个终点和四个累计权值，相同完整变换合并计数；最后在函数图上找环。该方法直接但权值维数较高。

子任务 3

函数图只有四点。枚举可达环的节点集合 $C$（共十五个非空集合）。在 DP 中仍记录四个终点，但权值只记录 $C$ 中起点对应边权之和。处理完整串后，仅保留函数图可达环恰为 $C$ 的状态，此时所记录的一维权值正是环权和。

映射只有 $4^4=256$ 种，权值范围为 $O(|s|)$。使用滚动数组和活跃状态表即可。

复杂度

三档算法时间复杂度依次为 $O(2^q|s|)$、完整变换状态数乘 $|s|$、$O(2^4\cdot4^4\cdot |s|^2)$；满分算法空间复杂度为 $O(4^4|s|)$。

正确性说明

有限前缀对无限局数中的胜率贡献趋于零，所以只需考察函数图可达环。子任务 3 枚举了该环节点集合的全部可能；对于正确集合，DP 累加的正是环上每条周期边的 Alice 胜局数减 Bob 胜局数。其正、零、负分别等价于 Alice 胜率大于、等于、小于二分之一，因此三个答案分类正确且无重无漏。