1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Nauuo and Cards
Contest: Codeforces Round 564 (Div. 1)
Difficulty rating: 1800
Tags: greedy, implementation

Nauuo is a girl who loves playing cards.

One day she was playing cards but found that the cards were mixed with some empty ones.

There are $$$n$$$ cards numbered from $$$1$$$ to $$$n$$$, and they were mixed with another $$$n$$$ empty cards. She piled up the $$$2n$$$ cards and drew $$$n$$$ of them. The $$$n$$$ cards in Nauuo's hands are given. The remaining $$$n$$$ cards in the pile are also given in the order from top to bottom.

In one operation she can choose a card in her hands and play it — put it at the bottom of the pile, then draw the top card from the pile.

Nauuo wants to make the $$$n$$$ numbered cards piled up in increasing order (the $$$i$$$-th card in the pile from top to bottom is the card $$$i$$$) as quickly as possible. Can you tell her the minimum number of operations?

Input format:
The first line contains a single integer $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$) — the number of numbered cards.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0\le a_i\le n$$$) — the initial cards in Nauuo's hands. $$$0$$$ represents an empty card.

The third line contains $$$n$$$ integers $$$b_1,b_2,\ldots,b_n$$$ ($$$0\le b_i\le n$$$) — the initial cards in the pile, given in order from top to bottom. $$$0$$$ represents an empty card.

It is guaranteed that each number from $$$1$$$ to $$$n$$$ appears exactly once, either in $$$a_{1..n}$$$ or $$$b_{1..n}$$$.

Output format:
The output contains a single integer — the minimum number of operations to make the $$$n$$$ numbered cards piled up in increasing order.

Constraints:
Time limit: 1.5 s
Memory limit: 256.0 MB

Note:
Example 1

We can play the card $$$2$$$ and draw the card $$$3$$$ in the first operation. After that, we have $$$[0,3,0]$$$ in hands and the cards in the pile are $$$[0,1,2]$$$ from top to bottom.

Then, we play the card $$$3$$$ in the second operation. The cards in the pile are $$$[1,2,3]$$$, in which the cards are piled up in increasing order.

Example 2

Play an empty card and draw the card $$$1$$$, then play $$$1$$$, $$$2$$$, $$$3$$$ in order.

Example input:
3
0 2 0
3 0 1

Example output:
2

Example input:
3
0 2 0
1 0 3

Example output:
4

Editorial:
First, try to finish it without playing any empty cards.
If that's not possible, the best choice is to play several empty cards in a row, then play from $$$1$$$ to $$$n$$$. For a card $$$i$$$, suppose that it is in the $$$p_i$$$-th position in the pile ($$$p_i=0$$$ if it is in the hand), you have to play at least $$$p_i - i + 1$$$ empty cards. So the answer will be $$$\max\{p_i-i+1+n\}$$$.
Nauuo and Circle
Contest: Codeforces Round 564 (Div. 1)
Difficulty rating: 1900
Tags: combinatorics, dfs and similar, dp, trees

Nauuo is a girl who loves drawing circles.

One day she has drawn a circle and wanted to draw a tree on it.

The tree is a connected undirected graph consisting of $$$n$$$ nodes and $$$n-1$$$ edges. The nodes are numbered from $$$1$$$ to $$$n$$$.

Nauuo wants to draw a tree on the circle, the nodes of the tree should be in $$$n$$$ distinct points on the circle, and the edges should be straight without crossing each other.

"Without crossing each other" means that every two edges have no common point or the only common point is an endpoint of both edges.

Nauuo wants to draw the tree using a permutation of $$$n$$$ elements. A permutation of $$$n$$$ elements is a sequence of integers $$$p_1,p_2,\ldots,p_n$$$ in which every integer from $$$1$$$ to $$$n$$$ appears exactly once.

After a permutation is chosen Nauuo draws the $$$i$$$-th node in the $$$p_i$$$-th point on the circle, then draws the edges connecting the nodes.

The tree is given, Nauuo wants to know how many permutations are there so that the tree drawn satisfies the rule (the edges are straight without crossing each other). She only wants to know the answer modulo $$$998244353$$$, can you help her?

It is obvious that whether a permutation is valid or not does not depend on which $$$n$$$ points on the circle are chosen.

Input format:
The first line contains a single integer $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) — the number of nodes in the tree.

Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1\le u,v\le n$$$), denoting there is an edge between $$$u$$$ and $$$v$$$.

It is guaranteed that the given edges form a tree.

Output format:
The output contains a single integer — the number of permutations suitable to draw the given tree on a circle satisfying the rule, modulo $$$998244353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Example 1

All valid permutations and their spanning trees are as follows.

Here is an example of invalid permutation: the edges $$$(1,3)$$$ and $$$(2,4)$$$ are crossed.

Example 2

Every permutation leads to a valid tree, so the answer is $$$4! = 24$$$.

Example input:
4
1 2
1 3
2 4

Example output:
16

Example input:
4
1 2
1 3
1 4

Example output:
24

Editorial:
First, if we choose a node as the root, then each subtree must be in a continuous arc on the circle. Then, we can use DP to solve this problem.
Let $$$f_u$$$ be the number of plans to draw the subtree of $$$u$$$, then $$$f_u=(|son(u)|+[u\ne root])!\prod\limits_{v\in son(u)}f_v$$$ — choose a position for each subtree and then $$$u$$$ itself, then draw the subtrees. However, instead of choosing the position of the root, we suppose the root is on a certain point on the circle, then rotate the circle, thus get the answer: $$$nf_{root}$$$.
In fact, we don't have to write a DP, the answer is $$$n$$$ times the product of the factorial of each node's degree ($$$n\prod\limits_{i = 1}^ndegree[i]$$$).
Nauuo and Pictures (easy version)
Contest: Codeforces Round 564 (Div. 1)
Difficulty rating: 2300
Tags: dp, probabilities

The only difference between easy and hard versions is constraints.

Nauuo is a girl who loves random picture websites.

One day she made a random picture website by herself which includes $$$n$$$ pictures.

When Nauuo visits the website, she sees exactly one picture. The website does not display each picture with equal probability. The $$$i$$$-th picture has a non-negative weight $$$w_i$$$, and the probability of the $$$i$$$-th picture being displayed is $$$\frac{w_i}{\sum_{j=1}^nw_j}$$$. That is to say, the probability of a picture to be displayed is proportional to its weight.

However, Nauuo discovered that some pictures she does not like were displayed too often.

To solve this problem, she came up with a great idea: when she saw a picture she likes, she would add $$$1$$$ to its weight; otherwise, she would subtract $$$1$$$ from its weight.

Nauuo will visit the website $$$m$$$ times. She wants to know the expected weight of each picture after all the $$$m$$$ visits modulo $$$998244353$$$. Can you help her?

The expected weight of the $$$i$$$-th picture can be denoted by $$$\frac {q_i} {p_i}$$$ where $$$\gcd(p_i,q_i)=1$$$, you need to print an integer $$$r_i$$$ satisfying $$$0\le r_i<998244353$$$ and $$$r_i\cdot p_i\equiv q_i\pmod{998244353}$$$. It can be proved that such $$$r_i$$$ exists and is unique.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n\le 50$$$, $$$1\le m\le 50$$$) — the number of pictures and the number of visits to the website.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$a_i$$$ is either $$$0$$$ or $$$1$$$) — if $$$a_i=0$$$ , Nauuo does not like the $$$i$$$-th picture; otherwise Nauuo likes the $$$i$$$-th picture. It is guaranteed that there is at least one picture which Nauuo likes.

The third line contains $$$n$$$ integers $$$w_1,w_2,\ldots,w_n$$$ ($$$1\le w_i\le50$$$) — the initial weights of the pictures.

Output format:
The output contains $$$n$$$ integers $$$r_1,r_2,\ldots,r_n$$$ — the expected weights modulo $$$998244353$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
In the first example, if the only visit shows the first picture with a probability of $$$\frac 2 3$$$, the final weights are $$$(1,1)$$$; if the only visit shows the second picture with a probability of $$$\frac1 3$$$, the final weights are $$$(2,2)$$$.

So, both expected weights are $$$\frac2 3\cdot 1+\frac 1 3\cdot 2=\frac4 3$$$ .

Because $$$332748119\cdot 3\equiv 4\pmod{998244353}$$$, you need to print $$$332748119$$$ instead of $$$\frac4 3$$$ or $$$1.3333333333$$$.

In the second example, there is only one picture which Nauuo likes, so every time Nauuo visits the website, $$$w_1$$$ will be increased by $$$1$$$.

So, the expected weight is $$$1+2=3$$$.

Nauuo is very naughty so she didn't give you any hint of the third example.

Example input:
2 1
0 1
2 1

Example output:
332748119
332748119

Example input:
1 2
1
1

Example output:
3

Editorial:
Nauuo and Bug
Contest: Codeforces Round 564 (Div. 1)
Difficulty rating: 3300
Tags: data structures

Nauuo is a girl who loves coding.

One day she was solving a problem which requires to calculate a sum of some numbers modulo $$$p$$$.

She wrote the following code and got the verdict "Wrong answer".

She soon discovered the bug — the ModAdd function only worked for numbers in the range $$$[0,p)$$$, but the numbers in the problem may be out of the range. She was curious about the wrong function, so she wanted to know the result of it.

However, the original code worked too slow, so she asked you to help her.

You are given an array $$$a_1,a_2,\ldots,a_n$$$ and a number $$$p$$$. Nauuo will make $$$m$$$ queries, in each query, you are given $$$l$$$ and $$$r$$$, and you have to calculate the results of Sum(a,l,r,p). You can see the definition of the Sum function in the pseudocode above.

Note that the integers won't overflow in the code above.

Input format:
The first line contains three integers $$$n$$$, $$$m$$$, $$$p$$$ ($$$1 \le n \le 10^6$$$, $$$1 \le m \le 2 \cdot 10^5$$$, $$$1 \le p \le 10^9$$$) — the length of the given array, the number of queries and the modulus. Note that the modulus is used only in the ModAdd function.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^9\le a_i\le10^9$$$) — the given array.

In the following $$$m$$$ lines, each line contains two integers $$$l$$$, $$$r$$$ ($$$1\le l\le r\le n$$$) — you have to calculate the result of Sum(a,l,r,p).

Output format:
The output contains $$$m$$$ integers to answer the queries in the given order.

Constraints:
Time limit: 4.0 s
Memory limit: 1024.0 MB

Example input:
4 5 6
7 2 -3 17
2 3
1 3
1 2
2 4
4 4

Example output:
-1
0
3
10
11

Editorial:
At first, let's solve this problem in $$$\mathcal{O}(n\sqrt{n \log n})$$$.
Let's split our array into blocks by $$$B$$$ integers, and let's find a function, $$$f(x) = $$$ which value you will get at the end of the current block if you will start with $$$x$$$. With simple induction, you can prove that this function is a piece-wise linear, and it has $$$\mathcal{O}(B)$$$ segments, so you can build it iteratively in $$$\mathcal{O}(B^2)$$$ time for each block, so the preprocessing took $$$\mathcal{O}(nB)$$$.
And to answer the query, you can keep the current value of $$$x$$$ and then find with binary search by that piece-wise linear function the $$$f(x)$$$ for the current block.
With a good choice of $$$B$$$, this solution will work in $$$\mathcal{O}(n\sqrt{n \log n})$$$.
Ok, but then how to solve it in $$$\mathcal{O}(n \log + q \log^2)$$$?
Lemma: each segment of this piece-wise linear function has length at least $$$p$$$.
You can prove it with simple induction.
And then, with this lemma, it is possible by two functions $$$f(x)$$$ of size $$$n$$$ and $$$g(x)$$$ of size $$$m$$$ find the new function $$$h(x) = g(f(x))$$$, in the $$$\mathcal{O}(n + m)$$$, you can do it with two pointers, similar to the previous iterative method, but adding a several points to the function each time, best way to understand it is to check the indendent solution :)
Even Substrings
Contest: Codeforces Round 548 (Div. 2)
Difficulty rating: 800
Tags: implementation, strings

You are given a string $$$s=s_1s_2\dots s_n$$$ of length $$$n$$$, which only contains digits $$$1$$$, $$$2$$$, ..., $$$9$$$.

A substring $$$s[l \dots r]$$$ of $$$s$$$ is a string $$$s_l s_{l + 1} s_{l + 2} \ldots s_r$$$. A substring $$$s[l \dots r]$$$ of $$$s$$$ is called even if the number represented by it is even.

Find the number of even substrings of $$$s$$$. Note, that even if some substrings are equal as strings, but have different $$$l$$$ and $$$r$$$, they are counted as different substrings.

Input format:
The first line contains an integer $$$n$$$ ($$$1 \le n \le 65000$$$) — the length of the string $$$s$$$.

The second line contains a string $$$s$$$ of length $$$n$$$. The string $$$s$$$ consists only of digits $$$1$$$, $$$2$$$, ..., $$$9$$$.

Output format:
Print the number of even substrings of $$$s$$$.

Constraints:
Time limit: 0.5 s
Memory limit: 256.0 MB

Note:
In the first example, the $$$[l, r]$$$ pairs corresponding to even substrings are:

- $$$s[1 \dots 2]$$$
- $$$s[2 \dots 2]$$$
- $$$s[1 \dots 4]$$$
- $$$s[2 \dots 4]$$$
- $$$s[3 \dots 4]$$$
- $$$s[4 \dots 4]$$$

In the second example, all $$$10$$$ substrings of $$$s$$$ are even substrings. Note, that while substrings $$$s[1 \dots 1]$$$ and $$$s[2 \dots 2]$$$ both define the substring "2", they are still counted as different substrings.

Example input:
4
1234

Example output:
6

Example input:
4
2244

Example output:
10

Editorial:
Any substring ending in $$$2, 4, 6, 8$$$ forms an even substring. Thus, iterate over all positions $$$i$$$ of the string $$$s$$$, and if the digit represented by character at $$$i_{th}$$$ index is even, then add $$$i+1$$$ to the answer, since all the substrings starting at $$$0, 1, ..., i$$$ and ending at $$$i$$$ are even substrings.
Overall Complexity: $$$O(n)$$$.
Chocolates
Contest: Codeforces Round 548 (Div. 2)
Difficulty rating: 1000
Tags: greedy, implementation

You went to the store, selling $$$n$$$ types of chocolates. There are $$$a_i$$$ chocolates of type $$$i$$$ in stock.

You have unlimited amount of cash (so you are not restricted by any prices) and want to buy as many chocolates as possible. However if you buy $$$x_i$$$ chocolates of type $$$i$$$ (clearly, $$$0 \le x_i \le a_i$$$), then for all $$$1 \le j < i$$$ at least one of the following must hold:

- $$$x_j = 0$$$ (you bought zero chocolates of type $$$j$$$)
- $$$x_j < x_i$$$ (you bought less chocolates of type $$$j$$$ than of type $$$i$$$)

For example, the array $$$x = [0, 0, 1, 2, 10]$$$ satisfies the requirement above (assuming that all $$$a_i \ge x_i$$$), while arrays $$$x = [0, 1, 0]$$$, $$$x = [5, 5]$$$ and $$$x = [3, 2]$$$ don't.

Calculate the maximum number of chocolates you can buy.

Input format:
The first line contains an integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$), denoting the number of types of chocolate.

The next line contains $$$n$$$ integers $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$), denoting the number of chocolates of each type.

Output format:
Print the maximum number of chocolates you can buy.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, it is optimal to buy: $$$0 + 0 + 1 + 3 + 6$$$ chocolates.

In the second example, it is optimal to buy: $$$1 + 2 + 3 + 4 + 10$$$ chocolates.

In the third example, it is optimal to buy: $$$0 + 0 + 0 + 1$$$ chocolates.

Example input:
5
1 2 1 3 6

Example output:
10

Example input:
5
3 2 5 4 10

Example output:
20

Editorial:
It is optimal to proceed greedily from the back of the array. If we have taken $$$x$$$ candies of the $$$i+1$$$ type, then we can only take $$$\min(x - 1, A_i)$$$ candies for type $$$i$$$. If this value is less than zero, we take $$$0$$$ from here.
Overall Complexity: $$$O(n)$$$
Edgy Trees
Contest: Codeforces Round 548 (Div. 2)
Difficulty rating: 1500
Tags: dfs and similar, dsu, graphs, math, trees

You are given a tree (a connected undirected graph without cycles) of $$$n$$$ vertices. Each of the $$$n - 1$$$ edges of the tree is colored in either black or red.

You are also given an integer $$$k$$$. Consider sequences of $$$k$$$ vertices. Let's call a sequence $$$[a_1, a_2, \ldots, a_k]$$$ good if it satisfies the following criterion:

- We will walk a path (possibly visiting same edge/vertex multiple times) on the tree, starting from $$$a_1$$$ and ending at $$$a_k$$$.
- Start at $$$a_1$$$, then go to $$$a_2$$$ using the shortest path between $$$a_1$$$ and $$$a_2$$$, then go to $$$a_3$$$ in a similar way, and so on, until you travel the shortest path between $$$a_{k-1}$$$ and $$$a_k$$$.
- If you walked over at least one black edge during this process, then the sequence is good.

Consider the tree on the picture. If $$$k=3$$$ then the following sequences are good: $$$[1, 4, 7]$$$, $$$[5, 5, 3]$$$ and $$$[2, 3, 7]$$$. The following sequences are not good: $$$[1, 4, 6]$$$, $$$[5, 5, 5]$$$, $$$[3, 7, 3]$$$.

There are $$$n^k$$$ sequences of vertices, count how many of them are good. Since this number can be quite large, print it modulo $$$10^9+7$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^5$$$, $$$2 \le k \le 100$$$), the size of the tree and the length of the vertex sequence.

Each of the next $$$n - 1$$$ lines contains three integers $$$u_i$$$, $$$v_i$$$ and $$$x_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$x_i \in \{0, 1\}$$$), where $$$u_i$$$ and $$$v_i$$$ denote the endpoints of the corresponding edge and $$$x_i$$$ is the color of this edge ($$$0$$$ denotes red edge and $$$1$$$ denotes black edge).

Output format:
Print the number of good sequences modulo $$$10^9 + 7$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, all sequences ($$$4^4$$$) of length $$$4$$$ except the following are good:

- $$$[1, 1, 1, 1]$$$
- $$$[2, 2, 2, 2]$$$
- $$$[3, 3, 3, 3]$$$
- $$$[4, 4, 4, 4]$$$

In the second example, all edges are red, hence there aren't any good sequences.

Example input:
4 4
1 2 1
2 3 1
3 4 1

Example output:
252

Example input:
4 6
1 2 0
1 3 0
1 4 0

Example output:
0

Editorial:
Let's find the number of bad sequences — Sequences of length $$$k$$$ that do not pass through any black edges. Then answer is all possible sequences minus the number of bad sequences.
Thus, we can remove black edges from the tree.
Now the tree would be split into connected components.
For every connected component, if we start with $$$A_1$$$ being a node from this component, then we cannot step outside this component, since doing so would mean that we visit a black edge. But we can visit all the nodes in the current connected component in any order. So if the size of the current component is $$$p$$$, then we have $$$p^k$$$ bad sequences corresponding to this connected component.
Thus, the overall answer is $$$n^k - \sum p^k$$$ where $$$p$$$ is the size of different connected components, considering only red edges.
Display The Number
Contest: Educational Codeforces Round 81 (Rated for Div. 2)
Difficulty rating: 900
Tags: greedy

You have a large electronic screen which can display up to $$$998244353$$$ decimal digits. The digits are displayed in the same way as on different electronic alarm clocks: each place for a digit consists of $$$7$$$ segments which can be turned on and off to compose different digits. The following picture describes how you can display all $$$10$$$ decimal digits:

As you can see, different digits may require different number of segments to be turned on. For example, if you want to display $$$1$$$, you have to turn on $$$2$$$ segments of the screen, and if you want to display $$$8$$$, all $$$7$$$ segments of some place to display a digit should be turned on.

You want to display a really large integer on the screen. Unfortunately, the screen is bugged: no more than $$$n$$$ segments can be turned on simultaneously. So now you wonder what is the greatest integer that can be displayed by turning on no more than $$$n$$$ segments.

Your program should be able to process $$$t$$$ different test cases.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases in the input.

Then the test cases follow, each of them is represented by a separate line containing one integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the maximum number of segments that can be turned on in the corresponding testcase.

It is guaranteed that the sum of $$$n$$$ over all test cases in the input does not exceed $$$10^5$$$.

Output format:
For each test case, print the greatest integer that can be displayed by turning on no more than $$$n$$$ segments of the screen. Note that the answer may not fit in the standard $$$32$$$-bit or $$$64$$$-bit integral data type.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
2
3
4

Example output:
7
11

Editorial:
First of all, we don't need to use any digits other than $$$1$$$ and $$$7$$$. If we use any other digit, it consists of $$$4$$$ or more segments, so it can be replaced by two $$$1$$$'s and the number will become greater. For the same reason we don't need to use more than one $$$7$$$: if we have two, we can replace them with three $$$1$$$'s.
Obviously, it is always optimal to place $$$7$$$ before $$$1$$$. So our number is either a sequence of $$$1$$$'s, or a $$$7$$$ and a sequence of $$$1$$$'s. We should use $$$7$$$ only if $$$n$$$ is odd, because if $$$n$$$ is even, it will decrease the number of digits in the result.
Infinite Prefixes
Contest: Educational Codeforces Round 81 (Rated for Div. 2)
Difficulty rating: 1700
Tags: math, strings

You are given string $$$s$$$ of length $$$n$$$ consisting of 0-s and 1-s. You build an infinite string $$$t$$$ as a concatenation of an infinite number of strings $$$s$$$, or $$$t = ssss \dots$$$ For example, if $$$s =$$$ 10010, then $$$t =$$$ 100101001010010...

Calculate the number of prefixes of $$$t$$$ with balance equal to $$$x$$$. The balance of some string $$$q$$$ is equal to $$$cnt_{0, q} - cnt_{1, q}$$$, where $$$cnt_{0, q}$$$ is the number of occurrences of 0 in $$$q$$$, and $$$cnt_{1, q}$$$ is the number of occurrences of 1 in $$$q$$$. The number of such prefixes can be infinite; if it is so, you must say that.

A prefix is a string consisting of several first letters of a given string, without any reorders. An empty prefix is also a valid prefix. For example, the string "abcd" has 5 prefixes: empty string, "a", "ab", "abc" and "abcd".

Input format:
The first line contains the single integer $$$T$$$ ($$$1 \le T \le 100$$$) — the number of test cases.

Next $$$2T$$$ lines contain descriptions of test cases — two lines per test case. The first line contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le n \le 10^5$$$, $$$-10^9 \le x \le 10^9$$$) — the length of string $$$s$$$ and the desired balance, respectively.

The second line contains the binary string $$$s$$$ ($$$|s| = n$$$, $$$s_i \in \{\text{0}, \text{1}\}$$$).

It's guaranteed that the total sum of $$$n$$$ doesn't exceed $$$10^5$$$.

Output format:
Print $$$T$$$ integers — one per test case. For each test case print the number of prefixes or $$$-1$$$ if there is an infinite number of such prefixes.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, there are 3 good prefixes of $$$t$$$: with length $$$28$$$, $$$30$$$ and $$$32$$$.

Example input:
4
6 10
010010
5 3
10101
1 0
0
2 0
01

Example output:
3
0
1
-1

Editorial:
Let's denote a prefix of length $$$i$$$ as $$$pref(i)$$$. We can note that each $$$pref(i) = k \cdot pref(n) + pref(i \mod n)$$$ where $$$k = \left\lfloor \frac{i}{n} \right\rfloor$$$ and $$$+$$$ is a concatenation. Then balance $$$bal(i)$$$ of prefix of length $$$i$$$ is equal to $$$k \cdot bal(n) + bal(i \mod n)$$$.
Now there two cases: $$$bal(n)$$$ is equal to $$$0$$$ or not. If $$$bal(n) = 0$$$ then if exist such $$$j$$$ ($$$0 \le j < n$$$) that $$$bal(j) = x$$$ then for each $$$k \ge 0$$$ $$$bal(j + kn) = x$$$ and answer is $$$-1$$$.
Otherwise, for each such $$$j$$$ there will no more than one possible $$$k$$$: since there are zero or one solution to the equation $$$bal(j) + k \cdot bal(n) = x$$$. The solution exists if and only if $$$x - bal(j) \equiv 0 \mod bal(n)$$$ and $$$k = \frac{x - bal(j)}{bal(n)} \ge 0$$$. So, just precalc $$$bal(n)$$$ and for each $$$0 \le j < n$$$ check the equation.