$2^N$个二进制位可以排成环状，使得所有按顺时针方向取得的N位二进制子串各不相同。

$N=3$时，有两种可行的排列方式：

第一种排列方式中按顺时针顺序取得的三位子串分别是：000、001、010、101、011、111、110和100。

每种排列方式都能以全为$0$的子串作为前三位来编码，例如上图的两种排列方式的编码为 $$00010111_2=23, \quad 00011101_2=29.$$ 记$S(N)$是所有符合要求的排列方式的编码之和，例如$S(3)=23+29=52$。

求$S(5)$。

本题难度:

解答

本题数据量很小，直接用深度优先搜索。

每次出栈后若可以在当前字串后添加0或1，则添加后入栈。长度达到32位时再判断分别以倒数第四、三、二、一个字符起始的子串是否符合要求，将符合要求的字符串转为整数后汇总即可。

结果是$209110240768$。

注：满足要求的字符串称为De Brujin Sequence，满足本题要求的De Brujin Sequence共有2048个。

注2：以下为Python 3代码，因Python 3的字符串比较有很大优化，效率远高于Python 2。

r=0
q=["00000"]

while q:
    s=q.pop()
    if len(s)==32 and (s[-4:]+s[0] not in s) and (s[-3:]+s[:2] not in s) and (s[-2:]+s[:3] not in s) and (s[-1:]+s[:4] not in s):
        r+=int(s,2)
    else:
        if s[-4:]+"0" not in s:
            q.append(s+"0")
        if s[-4:]+"1" not in s:
            q.append(s+"1")
    
print(r)