Codeforces Round 962 (Div. 3) E. Decode 题解

y0k1n0

2025 年 01 月 11 日

85 次浏览

暂无评论

1975字数

思维

# 题目描述

在拼命尝试获取你的"老婆"最喜欢的角色时，你已经侵入了游戏的源代码。经过数天的努力，你终于找到了编码游戏抽卡系统的二进制字符串。为了解码它，你必须首先解决以下问题。

给定长度为$n$的二进制字符串$s$。对于每对整数$(l, r)$ $(1 \leq l \leq r \leq n)$，计算子串$s_xs_{x+1}...s_y$中$\mathtt{0}$的数量等于$\mathtt{1}$的数量的所有$(x, y)$ $(l \leq x \leq y \leq r)$的对数。

输出所有可能的$(l, r)$的计数总和对$10^9+7$取模的结果。

# 输入

**输入**

第一行包含一个整数$t$($1 \leq t \leq 1000$)— 测试用例的数量。

每个测试用例包含一个二进制字符串$s$($1 \leq |s| \leq 2 \cdot 10^5$)。保证$s$只包含字符$\mathtt{0}$和$\mathtt{1}$。

保证所有测试用例中$|s|$的总和不超过$2 \cdot 10^5$。

# 输出

**输出**

对于每个测试用例，输出一个整数，答案模 $10^9+7$。

# 解题思路

阅读题目， 不难发现题目中需要求得的是对于$\forall x, y,  1\leq x \leq y \leq n$且满足字串$s_xs_{x+1}...s_y$中$\mathtt{0}$的数量等于$\mathtt{1}$的数量, 存在多少的$1\leq l \leq x \leq y \leq r \leq n$, 使得$[x, y]$是[l, r]的子区间

考察每一个子区间$[x, y]$， 包含他的区间$[l, r]$总数为$x \times (n - y + 1)$

现在考虑如何求出$[x, y]$区间的左右端点： 不妨考虑前缀和， 设字符`'0'`对应$-1$, 字符`'1'`对应$1$， 则在前缀和数组`pre`中， 如果`pre[i] == pre[j]`， 则证明$[i - 1, j]$即是所求的区间

现在考虑如何统计所有前缀和为`t`子区间的贡献， 假设现在有`pre[i] = pre[j] = pre[k] = t`， 则对答案有贡献的区间为$[i + 1, j]$, $[j + 1, k]$, $[i + 1, k]$， 先考虑朴素做法：

- 区间$[x, y]$的贡献度为$(x + 1) * (n - y + 1)$， 其中将$(x+1)$称作**左部**， $(n - y +1)$称为**右部**
- 区间$[i + 1, j]$的贡献度为$(i + 1) * (n - j + 1)$
- 区间$[j + 1, k]$的贡献度为$（j + 1）* （n - k + 1）$
- 区间$[i + 1, k]$的贡献度为$（i + 1）* （n - k + 1）$
- 所有的$pre[h] = t$的总贡献为$(i + 1) * (n - j + 1) + [(i + 1) + (j + 1)] * (n - k + 1)$
- 不难发现， 对于每个右部$k$，其对应的左部为$l \in [0, k - 1]$中所有$pre[l]$为$t$的

因此可以对上述过程进行下述优化：

- 使用字典记录$[0, i - 1]$内前缀和为$t$的所有左部的累加
- 遇到$j > i \And pre[j]=t$时， 计算$j$和所有前缀和为$t$的$i$的贡献之和
- 如此， 可以将时间复杂度降到$O(N)$

# AC代码

```cpp
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <map>
#define endl '\n'
using namespace std;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
int t, n;
string s;
int a[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> t;
    while(t --)
    {
        map<int, int> dic;
        cin >> s;
        n = s.size();
        s = " " + s;
        for(int i = 1; i <= n; i ++)
        {
            if(s[i] == '1') a[i] = a[i - 1] + 1;
            else a[i] = a[i - 1] - 1;
        }
        int ans = 0;
        dic[0] = 1;
        for(int i = 1; i <= n; i ++)
        {
            ans = (ans + 1ll * dic[a[i]] * (n - i + 1) % mod) % mod;
            dic[a[i]] = ((long long)dic[a[i]] + i + 1) % mod;
        }
        cout << ans << endl;
    }
	return 0;
}
```

最后修改：2025 年 01 月 11 日