codeforces#P1930D2. Sum over all Substrings (Hard Version)
Sum over all Substrings (Hard Version)
Description
This is the hard version of the problem. The only difference between the two versions is the constraint on and . You can make hacks only if both versions of the problem are solved.
For a binary pattern and a binary string , both of length , is called -good if for every (), there exist indices and such that:
- , and
- is a mode of the string .
For a pattern , let be the minimum possible number of s in a -good binary string (of the same length as the pattern).
You are given a binary string of size . Find In other words, you need to sum the values of over all substrings of .
A binary pattern is a string that only consists of characters and .
Character is a mode of string of length if the number of occurrences of in is at least . For example, is a mode of , is not a mode of , and both and are modes of .
Each test contains multiple test cases. The first line contains the number of test cases () — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer () — the length of the binary string .
The second line of each test case contains a binary string of length consisting of only characters and .
It is guaranteed that the sum of over all test cases does not exceed .
For each test case, output the sum of values of over all substrings of .
Input
Each test contains multiple test cases. The first line contains the number of test cases () — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer () — the length of the binary string .
The second line of each test case contains a binary string of length consisting of only characters and .
It is guaranteed that the sum of over all test cases does not exceed .
Output
For each test case, output the sum of values of over all substrings of .
Note
In the first test case, the only -good string is . Thus, .
In the second test case, because is -good, and is not -good. Thus, the answer is .
In the third test case, equals to for all . Thus, the answer is .