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

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    // Write your code here
    while(line = await readline()){
        const n = parseInt(line);
        let s = await readline();
        s = ' ' + s + s;
        const MOD = 1e9 + 7;
        let ans = 0;
        let sum = 0; // 表示当前i结尾的长度是n的字符串的权值
        let sum0 = 0; // 表示当前窗口里0的权重和，从字符串的位置开始，第1个权重是1
        let sum1 = 0; // 表示当前i结尾的长度为2～n的字符串权值和
        let num0 = 0;
        let num1 = 0;

        for (let i = 1; i <= n; i++) {
            if(s[i] === '0') {
                num0 += 1;
                sum0 += i;
            } else {
                num1 += 1;
                sum1 += sum0;
                sum += num0;
            }
        }

        for (let i = n + 1; i <= n * 2; i++) {
            sum1 -= sum;
            sum0 -= num0;

            if (s[i] === '0') {
                sum -= num1;
                sum0 += n;
            } else {
                sum1 += sum0;
                sum += num0;
            }

            ans += sum1;
            ans %= MOD;
        }

        console.log(ans);
    }
}()