CF1038F Wrap Around

给定一个二进制字符串 $s$。 请你计算长度为 $n$ 的不同循环二进制字符串的数量，这些字符串中包含 $s$ 作为子串。 如果存在某个循环移位后的字符串 $t$，使得 $s$ 是该字符串的一个子串，则称循环字符串 $t$ 包含 $s$ 作为子串。 例如，循环字符串 "000111" 包含子串 "001"、"01110" 和 "10"，但不包含 "0110" 和 "10110"。 如果两个循环字符串本身不同，则认为它们是不同的循环字符串，即使它们仅通过循环移位不同，也视为不同的循环字符串。

第一行包含一个整数 $n$（$1 \le n \le 40$），表示目标字符串 $t$ 的长度。 第二行包含字符串 $s$（$1 \le |s| \le n$），表示必须作为子串出现的字符串。字符串 $s$ 仅包含字符 '0' 和 '1'。

输出一个整数，表示包含 $s$ 作为子串的不同循环二进制字符串 $t$ 的数量。

在第一个样例中，有三个包含 "0" 的循环字符串——"00"、"01" 和 "10"。 在第二个样例中，只有两个这样的字符串——"1010" 和 "0101"。 由 ChatGPT 4.1 翻译