P14591 [LNCPC 2025] Kanon

> 梦。 > > 我做着一个悠远而长久的梦。 > > 从很久以前就一直在做着这个梦； > > 在梦中我凝望四季的街道， > > 期望与永远不会到来的人再度见面， > > 找寻连自己也早已忘却的遗失的东西。 > > 多少时间、多少岁月从我身边流逝而过， > > 在无尽的黑夜中，一直、一直都在孤单地等待着—— > > 等待着最后那必将到来的黎明。 > > ——《Kanon》

下文中，我们约定： - 字符串的下标从 $1$ 开始。 - 对于一个字符串 $s$，$s[l:r]$ 表示将 $s_l,s_{l+1},\cdots,s_r$ 依次连接形成的字符串。 - $a\oplus b$ 表示 $a$ 和 $b$ 在二进制下按位异或得到的值。 - $\bigoplus\limits_{i=1}^na_i=a_1\oplus a_2\oplus\cdots\oplus a_n$。 --- 亚由的梦里有一个长度为 $n$ 的、仅由数字 $0$ 和 $1$ 构成的字符串 $s$。她现在需要将其划分成 $k$ 个非空子段 $s[1:p_1],s[p_1+1:p_2],\cdots,s[p_{k-1}+1:n]$，其中 $1\le p_1

每个测试点包含多组测试数据。第一行给定一个整数 $T(1\leq T\leq 10^4)$，表示测试数据组数。 对于每组测试数据，给定一行一个仅由 $0$ 和 $1$ 构成的字符串 $s$。 保证在每个测试点中所有测试数据的字符串的长度的总和不超过 $3\times 10^6$。

对于每组数据，为了避免大量的输出，采用如下输出方式（本题正解不依赖该输出方式）： 设对于 $k=1,2,\cdots,n$，对应的最大值对 $998244353$ 取模后，为 $p_1,p_2,\cdots,p_n$；权值为最大值的划分方案数对 $998244353$ 取模后，为 $q_1,q_2,\cdots,q_n$。则一行输出四个整数 $A,B,C,D$，用半角空格隔开。其中 $A,B,C,D$ 的值分别为： $$ \begin{aligned} A&=\bigoplus_{i=1}^np_i\\ B&=\bigoplus_{i=1}^nq_i\\ C&=\bigoplus_{i=1}^n(p_i\times i)\\ D&=\bigoplus_{i=1}^n(q_i\times i)\\ \end{aligned} $$ 注意，需要取模的只有最终得到的最大值和权值为最大值的划分方案数。**您无需在计算 $\boldsymbol{A,B,C,D}$ 的过程中取模**。

### 样例解释 对于样例的第一组测试数据，下面分别算出 $k=1,2,3$ 时对应的答案： - $k=1$：最大值即为它本身 $(110)_2=6$，方案数为 $1$。 - $k=2$：当划分方案为 $(11,0)$ 或 $(1,10)$ 时，都可以得到最大值，为 $(11)_2\oplus(0)_2=(1)_2\oplus(10)_2=3$，方案数为 $2$。 - $k=3$：划分方案只有 $(1,1,0)$，最大值为 $(1)_2\oplus(1)_2\oplus(0)_2=0$，方案数为 $1$。 这样可以得到 $p=\{6,3,0\},q=\{1,2,1\}$，可以分别求得 $A,B,C,D$： $$ \begin{aligned} A&=6\oplus3\oplus0=5\\ B&=1\oplus2\oplus1=2\\ C&=(6\times1)\oplus(3\times2)\oplus(0\times3)=0\\ D&=(1\times1)\oplus(2\times2)\oplus(1\times3)=6 \end{aligned} $$ 故输出的数分别为 $5,2,0,6$。