A16686 | $Left is Always Right$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

给定一个长度为 $n$ 的二进制字符串和一个奇数 $k$。如果对于该字符串的每一个长度为 $k$ 的子串，其最左侧的字符出现的次数比其他字符多，则称该二进制字符串是好的。 例如，当 $k=3$ 时，字符串 000101 是好的，因为所有长度为 $3$ 的子串（000、001、010 和 101）中，子串最左侧的字符出现次数都多于另一种字符。相反，1011 不是好字符串，因为子串 011 不满足该性质。 现在给定一个长度为 $n$ 的模式串，包含字符 0、1 或 ?。请你计算将所有 ? 替换为 0 或 1，使得所得二进制字符串为好字符串的方案数。由于答案可能很大，请对 $998\,244\,353$ 取模后输出。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 10^3$），表示测试数据的组数。 每组测试数据的第一行包含两个整数 $n$ 和 $k$（$3 \le k \le n \le 10^5$，$k$ 为奇数）。第二行包含 $n$ 个字符 0、1 或 ?，组成的模式串。 保证所有测试数据中 $n$ 的总和不超过 $10^5$。

对于每组测试数据，输出一个整数，表示将所有 ? 替换为 0 或 1，使得所得字符串为好字符串的方案数，对 $998\,244\,353$ 取模后输出。

输入 #1

3
5 3
0??0?
7 7
1??1??1
9 5
?????????

输出 #1

3
15
46

C++ 编辑器

输入

输出