CF1996E.Decode

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

为了获得你心仪的“老婆”角色，你不惜黑进了游戏的源代码。经过数天的努力，你终于找到了用于编码游戏抽卡系统的二进制字符串。为了解码它，你首先需要解决如下问题。

给定一个长度为 $n$ 的二进制字符串 $s$ 。对于每一对整数 $(l, r)$ （ $1 \leq l \leq r \leq n$ ），统计有多少对 $(x, y)$ （ $l \leq x \leq y \leq r$ ），使得子串 $s_xs_{x+1}\ldots s_y$ 中 $0$ 的数量等于 $1$ 的数量。

请输出所有可能的 $(l, r)$ 对应的计数之和，答案对 $10^9+7$ 取模。

输入格式

第一行包含一个整数 $t$ （ $1 \leq t \leq 1000$ ），表示测试用例的数量。

每个测试用例包含一个二进制字符串 $s$ （ $1 \leq |s| \leq 2 \times 10^5$ ）。保证 $s$ 只包含字符 $0$ 和 $1$ 。

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

输出格式

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

输入输出样例

输入#1

4
0000
01010101
1100111001
11000000111

输出#1

说明/提示

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页