U535402 【搬运】FR0G EBB

出处是山东省集。

有一个长度为 $n$ 的 01 串 $a=a_{1} a_{2} \ldots a_{n}$。 初始时 $x=0$，按照 $i=1,2, \ldots, n$ 的顺序对 $x$ 进行操作，对于每次操作： - 如果 $a_{i}=0$，则 $x \leftarrow x-\operatorname{lowbit}(x)$。 - 如果 $a_{i}=1$，则 $x \leftarrow x+\operatorname{lowbit}\left(2^{k}-1-x\right)$。 规定 $\operatorname{lowbit}(0)=0$。定义 $f(a)$ 是所有操作后 $x$ 的值。 给定整数 $r$ 和 $k$，对于每一个 $i=1,2, \ldots, n$，求： - 有多少种补全 01 串的方案使得 $a_i=0$ 且 $f(a)\leq r$。 答案对 $998244353$ 取模。

第一行，三个正整数 $n,k,r$。 第二行，一个长为 $n$ 的 01? 字符串 $s$。

一行 $n$ 个数，表示 $i=1,2, \ldots, n$ 时答案对 $998244353$ 取模的值。

对于所有数据，$1\leq n\leq 10^5$，$1\leq k\leq 20$，$0\leq r< 2^k$。 共 $25$ 个测试点，每个测试点 $4$ 分。 | 测试点 | $n$ | $k$ | $r$ | |:-:|:-:|:-:|:-:| |$1\sim3$ | $\leq20$ | $\leq 4$ | $