H. *【哈密顿回路】开关的哈密顿路径[BZOJ3033]太鼓达人

传统题

1000ms

64MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题意】

$M$ 个传感器围成一圈。每个传感器都有开和关两种工作状态，分别用 $1$ （开）和 $0$ （关）表示。

从不同的位置出发沿顺时针方向连续检查 $K$ 个传感器可以得到 $M$ 个长度为 $K$ 的 $01$ 串。已知这 $M$ 个 $01$ 串应该是互不相同的。

已知 $K$ 的值，求 $M$ 可能的最大值，并给出字典序最小的传感器排布方案。

一个整数 $K(2 \le K \le 11)$ 。

一个整数 $M$ 和一个二进制串。

8 00010111

得到的 8 个 01 串分别是 000,001,010,101,011,111,110 和 100。注意前后是相邻的。

长度为 3 的二进制串总共只有 8 种，所以 M=8 一定是可能的最大值。