#P18766. Expected Symmetry
Expected Symmetry
Expected Symmetry
题目描述
给定一个长度为 的二进制字符串 。
考虑如下随机过程:
- 从 到 中等概率地选择一个整数 。
- 考察前缀 。如果存在一个对称位置 (),使 则过程立刻结束。
- 否则,对于每个 ,分别独立地以 的概率翻转 的值。之后重新执行上述步骤,选择下一个 。
不同步骤中选择的 相互独立。所有位是否翻转的事件,在不同位置以及不同步骤之间也都相互独立。
请计算该过程结束时经历的步数期望,包括过程结束的那一步。可以证明答案可以表示为最简分数 ,请输出
注意:停止条件是存在至少一对镜像位置上的值相同,并不要求整个前缀是回文。
输入格式
第一行包含一个整数 。
第二行包含长度为 的二进制字符串 。
数据范围
- ;
- 字符串只包含字符0和1,长度恰好为 。
输出格式
输出一个整数,表示期望步数对998244353取模后的值。
样例
输入:
10
01010000111101010000
输出:
222017723