Decode

题面翻译

给出一个长度为由 $0$ 和 $1$ 组成的字符串 $s$。

定义：若区间 $[l,r]$ 中 $0$ 的个数等于 $1$ 的个数，则 $f(l,r)=1$，否则 $f(l,r)=0$。

求 $\displaystyle\sum_{l=1}^n \displaystyle\sum_{r=l}^n\displaystyle\sum_{x=l}^r \displaystyle\sum_{y=x}^r f(x,y)$。

答案对 $10^9+7$ 取模。

令 $|s|$ 为字符串 $s$ 的长度，保证 $1\le |s|\le 2\times 10^5$。

Translated by PineappleSummer.

题目描述

In a desperate attempt to obtain your waifu favorite character, you have hacked into the source code of the game. After days of struggling, you finally find the binary string that encodes the gacha system of the game. In order to decode it, you must first solve the following problem.

You are given a binary string $ s $ of length $ n $ . For each pair of integers $ (l, r) $ $ (1 \leq l \leq r \leq n) $ , count the number of pairs $ (x, y) $ $ (l \leq x \leq y \leq r) $ such that the amount of $ \mathtt{0} $ equals the amount of $ \mathtt{1} $ in the substring $ s_xs_{x+1}…s_y $ .

Output the sum of counts over all possible $ (l, r) $ modulo $ 10^9+7 $ .

输入格式

The first line contains $ t $ ( $ 1 \leq t \leq 1000 $ ) — the number of test cases.

Each test case contains a binary string $ s $ ( $ 1 \leq |s| \leq 2 \cdot 10^5 $ ). It is guaranteed $ s $ only contains characters $ \mathtt{0} $ and $ \mathtt{1} $ .

It is guaranteed the sum of $ |s| $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, output an integer, the answer modulo $ 10^9+7 $ .

样例 #1

样例输入 #1

4
0000
01010101
1100111001
11000000111

样例输出 #1

0
130
147
70

题目的本意是找到一个区间[x,y]，这个区间1的个数等于0的个数，然后l<=x,r>=y，问有多少个l和r满足情况，，明显是x*(n-y+1)，但是区间怎么找，运用前缀和的关系

令1让ans++，0让ans–，如果当前的ans已经出现过了，上一次出现的位置+1到当前的位置的区间就是0的个数等于1的个数，以每一个区间左端点存有多少个l可选择，那么确定右端点后，前面有多少个左端点就有多少个选择，可以用前缀和加起来

const int N = 2e5 + 10;
int a[N];
int b[N];

int mod = 1e9 + 7;
void solve()
{
    string s; cin >> s;
    int n = s.size();
    s = " " + s;
    map<int, int> p;
    p[0] = 1;
    int ans = 0;
    int sum = 0;
    for (int i = 1; i <= n; i++)
    {
        if (s[i] == '1') ans++;
        else ans--;
        sum = (sum + ((n - i + 1) * p[ans]) % mod) % mod;
        p[ans] = (p[ans] + i+1) % mod;
    }
    cout << sum << '\n';
}