CF2276E.Good Substrings

普及+/提高

通过率:0%

时间限制:2.00s

内存限制:512MB

AC君温馨提醒

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

题目描述

You are given a string ss of length nn, consisting only of digits.

A substring of ss is a contiguous subsequence of its characters. A substring sl…rs_{l \dots r} is bad if it contains the string 20252025 as a subsequence and doesn't contain the string 20262026 as a subsequence. Otherwise, the substring is good. For example, the strings 20252025, 7270727572707275, 2062520625 are bad, but the strings 2025620256, 20262026, 777777, 12907235761290723576 are good.

For each index ii from 11 to nn, calculate the number of good substrings that contain it. In other words, for each index ii from 11 to nn, calculate the number of pairs of integers l,rl, r such that 1≤l≤i≤r≤n1 \le l \le i \le r \le n and the substring sl…rs_{l \dots r} is good.

给你一个长度为 nn 的字符串 ss,其中仅包含数字字符。

ss 的一个子串是指其字符的一个连续子序列。若子串 sl…rs_{l \dots r} 包含字符串 20252025 作为子序列,且不包含字符串 20262026 作为子序列,则称该子串为坏的;否则,该子串为好的。例如,字符串 20252025、7270727572707275、2062520625 是坏的,而字符串 2025620256、20262026、777777、12907235761290723576 是好的。

对每个从 11 到 nn 的下标 ii,计算包含位置 ii 的好子串的个数。换言之,对每个从 11 到 nn 的下标 ii,计算满足 1≤l≤i≤r≤n1 \le l \le i \le r \le n 且子串 sl…rs_{l \dots r} 为好的整数对 (l,r)(l, r) 的个数。

输入格式

The first line contains a single integer tt (1≤t≤1041 \le t \le 10^4) — the number of test cases.

The first line of each test case contains a single integer nn (1≤n≤3⋅1051 \le n \le 3 \cdot 10^5).

The second line contains a string ss of length nn, consisting of digits.

Additional constraint on the input: the sum of nn across all test cases does not exceed 3⋅1053 \cdot 10^5.

第一行包含一个整数 tt(1≤t≤1041 \le t \le 10^4)——测试用例的数量。

每个测试用例的第一行包含一个整数 nn(1≤n≤3⋅1051 \le n \le 3 \cdot 10^5)。

第二行包含一个长度为 nn 的字符串 ss,由数字组成。

输入的额外约束:所有测试用例的 nn 之和不超过 3⋅1053 \cdot 10^5。

输出格式

For each test case, print nn integers. The ii-th integer should be equal to the number of good substrings that contain index ii.

对于每个测试用例,输出 nn 个整数。其中第 ii 个整数应等于包含下标 ii 的“好”子串的数量。

输入输出样例

  • 输入#1

    2
    6
    202516
    5
    20265

    输出#1

    4 8 10 10 9 6 
    5 8 9 8 5

说明/提示

null

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

首页