分数: 466 分
问题陈述
2^N 学生从左到右站成一排,每个学生都戴着红色帽子或白色帽子。学生帽子的颜色用字符串表示 S 长度 2^N。对于 i左起第一个学生,如果 i- 第一个字符 S is 0,他们戴着红色帽子,如果是 1,他们戴着白帽子。
高桥,为准备体育节,可以执行以下操作 最多一次:
- 选择一个整数 l (1 \leq l \leq 2^N - K + 1),并重新排列 K 连续学生 l-第 (l+K-1)从左边算起。重新排列的结果是,该区间内所有戴红帽子的学生都连续放在该区间的左侧,所有戴白帽子的学生都连续放在该区间的右侧。区间外学生的位置不变。
操作完成后(如果不进行操作则按原样),根据以下规则将学生递归分组:
- 最初,所有来自 1-st 到 2^N从左起第一个组成一组。
- 一组 2 或更多人被分成两组:一组由前半部分学生(从左数)组成,一组由后半部分学生组成。
- 重复这种分割,直到每个组恰好包含 1 人。
考虑这个过程中出现的所有群体(包括最初的整体群体、每个中间阶段的群体以及最终的单人群体——总共 2^{N+1} - 1 组)。如果组内戴红帽子的学生数量和戴白帽子的学生数量相等,则该组称为“平衡组”。请注意,单人小组无法满足此条件,因此它永远不是一个平衡的小组。
求当Takahashi最优选择是否执行操作和区间位置时,平衡组的最大可能数量。
约束
- 1 \leq N
- 2^N \leq 10^6
- 1 \leq K \leq 2^N
- S 是一个长度为的字符串 2^N 组成
0和1 - N, K 是整数
输入
N K S
第一行包含整数 N,代表学生人数参数,整数 K,表示操作中要重新排列的区间长度,以空格分隔。第二行包含字符串 S 长度 2^N 代表每个学生的帽子颜色。
输出
将平衡组的最大数量输出为单个整数。
示例输入 1
2 2 0110
示例输出 1
3
示例输入 2
3 3 01011001
示例输出 2
7
示例输入 3
5 7 00110101111000010100111011001010
示例输出 3
19
示例输入 4
8 64 0100110010110001111001011010100011110000101010100101001111001100000111010010110111001000101101111010101000001111111100000101010101100110011010010101101011000011100100111011010001001011011110000011001111001100001111000011110011001010010101100011101010010111
示例输出 4
146
示例输入 5
1 1 01
示例输出 5
1