← 返回题目列表

AtCoder · awc0081_e

E. 锦标赛分区中的平衡小组

中文机器翻译题面 查看原题

分数: 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. 最初,所有来自 1-st 到 2^N从左起第一个组成一组。
  2. 一组 2 或更多人被分成两组:一组由前半部分学生(从左数)组成,一组由后半部分学生组成。
  3. 重复这种分割,直到每个组恰好包含 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