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

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a), _##i = (b); i <= _##i; ++i)
#define per(i, a, b) for (int i = (a), _##i = (b); i >= _##i; --i)
#define vi vector <int>
#define vii vector <pii >
#define vl vector <ll>
#define vb vector <bool >
#define eb emplace_back
#define pb push_back
#define pii pair <int, int>
#define vt vector <vi >
#define vtv vector <vii >
#define all(a, i) a.begin() + i, a.end()
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
// 001001	
ll ans = 0, sum = 0;
ll num0, sum0, num1, sum1;
void solve() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	s = " " + s + s;
	// sum 维护以即将被去除的滑动窗口签的那一个字符为开头的0/1个数
	// sum1 维护最大区间所有区间的0/1个数
	// sum0 维护 当前窗口组合含0的子序列的方法数
	rep(i, 1, n) {
		if (s[i] == '0') num0++, sum0 += i;
		else num1++, sum1 += sum0, sum += num0;
 	}
 	rep(i, n + 1, 2 * n) {
 		// 这里也是减去 i - n 作为边界的贡献 
 		sum1 -= sum;
 		// 把 i - n 作为边界的贡献减去 
 		sum0 -= num0;
 		//如果去掉一个 0 那么 sum 会变化, num0 会变化 
 		if (s[i - n] == '0') num0--, sum -= num1; 
 		else num1--; 
 		if (s[i] == '0') num0++, sum0 += n;
		else num1++, sum1 += sum0, sum += num0;
		ans += sum1;
		ans %= mod; 
	 }
	cout << ans << '\n';
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int t;
	t = 1;
//    cin >> t;
	while (t--) {
	   solve();
	}
	return 0;
}