P17133 [ICPC 2025 Shanghai R] Yet another 01 problem

试题来自 [清华大学学生算法协会](https://gitlink.org.cn/thusaa/ICPC2025shanghai)。

Yana、Mino、White 和 Huzz 是最好的朋友。 最近，Mino 一直感到迷茫。他沉溺于自己过去在 OI 中的失败，在繁忙的学业中艰难地规划未来。三位朋友建议他评估自己各项任务的重要性，并为其排列优先级。 假设共有 $n$ 个不同的任务，编号为 $1$ 到 $n$。每次，Huzz 选择两个相邻的任务，White 比较它们，然后 Yana 将它们合并为一个任务。Mino 惊奇地发现，这个过程竟意外地形成了一棵线段树，且并不一定在中间位置分裂。更准确地说，它形成了一棵有 $2n - 1$ 个节点的树，其中每个子树都对应一个连续区间。注意，所有 $n$ 个任务都是叶子，而其余 $n - 1$ 个节点每个都有两个孩子。这些由比较产生的节点定义了连向其孩子的边的权值：较小的孩子对应 $0$，较大的孩子对应 $1$。 Mino 非常喜欢计算。他将每个任务的权重定义为从该任务到根的路径上所有边的权值的异或和。他思考道：如果给定了这些权重，构造这样的树以及确定孩子间比较结果的方法有多少种？ 又一次，Mino 并不擅长 OI，因此他向你求助。为了简化问题，你只需要求出答案对 $998,244,353$ 取模的结果。

第一行包含一个正整数 $n$ ($1 \le n \le 250000$)，表示任务的数量。 第二行包含一个长度为 $n$ 的二进制字符串 $S$，其中 $S_i$ 表示从任务 $i$ 到根的路径上所有边权值的按位异或结果。

输出一个整数，即答案对 $998,244,353$ 取模的结果。

有 $6$ 种构造树以及确定孩子间比较结果的方法： :::align{center}  ::: 翻译由 DeepSeek V4 Pro 完成