UOJ Logo Universal Online Judge

UOJ

附件下载 统计

小重和小庆正在下“兵棋”。

$n$ 个士兵棋子排成一行,每个士兵要么是小重的要么是小庆的。接下来有若干天,每天如果第 $i$ 个士兵和第 $i+1$ 只士兵不属于同一玩家,那么第 $i$ 只士兵会击杀第 $i+1$ 只士兵。所有击杀操作会同时进行,士兵被击杀后会被移除。例如,如果某一天第 3 个士兵击杀第 4 个士兵,第 4 个士兵击杀第 5 个士兵,那么结果就是第 4 个和第 5 个士兵都会被移除。

现在小重和小庆已经在一些位置上摆好自己的士兵了,但他们还没确认其余位置摆什么士兵。你需要对于所有方案,求出 $k$ 天后剩下的士兵数的总和,答案对 $998244353$ 取模。

简要题意

对于一个 $01$ 字符串,定义其权值如下:执行 $k$ 轮操作,每次找到所有 $s_{i}\neq s_{i-1} (i\ge 2)$ 的位置 $i$,并把 $s_i$ 删掉。它的权值就是最后剩余的字符数。

现在字符串中有一些问号,这些位置既可以填 $0$ 也可以填 $1$。你需要对于所有填数方案求权值总和。答案对 $998244353$ 取模。

输入格式

第一行输入两个正整数 $n,k$。

第二行包含一个字符串 $s$。$s_i=\texttt{0}$ 表示第 $i$ 个位置上摆了小重的士兵,$s_i=\texttt{1}$ 表示第 $i$ 个位置摆了小庆的士兵,$s_i=\texttt{?}$ 表示第 $i$ 个位置还没摆士兵。

输出格式

共一行,用一个正整数表示答案。

样例一

input

5 1
01?10

output

4

样例二

input

6 2
?????0

output

89

样例三$\sim$九

见附件下载。

限制与约定

对于所有数据,保证 $1\le n\le 10^5,1\le k\le 200$。

子任务编号 $n\leq$ $k\leq$ 特殊性质 分值
1 $18$ $18$ $8$
2 $10^5$ $200$ 问号个数 $\le 8$ $12$
3 $100$ $100$ $24$
4 $500$ $200$ $8$
5 $10^5$ $1$ $8$
6 $2$ $16$
7 $5$ $16$
8 $200$ $8$

时间限制:$\texttt{2s}$

空间限制:$\texttt{1GB}$