题解 | 小红的01子序列计数（hard）

while True:
    try:
        n = int(input())
        s = input()
        s = ' ' + s + s     # 加一个空格，从索引1开始处理
        MOD = 10 ** 9 + 7
        ans = 0     # 最终答案
        sum = 0     # 以即将被去除的滑动窗口前的那一个字符为开头的0/1个数
        sum0 = 0    # 当前窗口中包含0的子序列数量
        sum1 = 0    # 最大区间所有区间的0/1个数
        num0 = 0    # 当前窗口中0的数量
        num1 = 0    # 当前窗口中1的数量

        for i in range(1, n+1):     # 第一次遍历，初始化窗口的值
            if s[i] == '0':
                num0 += 1
                sum0 += i
            else:
                num1 += 1
                sum1 += sum0
                sum += num0

        for i in range(n+1, 2 * n + 1):     # 滑动窗口
            # 减去i-n作为边界的贡献
            sum1 -= sum
            sum0 -= num0

            if s[i - n] == '0':     # 如果溢出窗口的字符是0
                num0 -= 1
                sum -= num1
            else:
                num1 -= 1

            if s[i] == '0':     # 加入新字符的贡献
                num0 += 1
                sum0 += n
            else:
                num1 += 1
                sum1 += sum0
                sum += num0
                
            ans += sum1     # 累加答案
            ans %= MOD
        
        print(ans)

    except:
        break