There are some gifts in a box. Each gift is a $$$1 \times 1 \times 1$$$ cube. The width, length, and height of the box are $$$n$$$, $$$m$$$, and $$$h$$$ respectively, as shown in Figure 1. The gifts are neatly placed in the box and we can use an $$$n \times m$$$ matrix $$$A$$$ to represent them. If we look at the box from the top there are $$$A_{i,j}$$$ gifts at $$$i$$$-th row, $$$j$$$-th column.
Fig. 1. the original box Now we carefully turn the box and make its opening facing to us, as shown in Figure 2. Then we want to use another $$$h \times m$$$ matrix $$$B$$$ to represent the gifts. If we look at the box from the top there are $$$B_{i,j}$$$ gifts at $$$i$$$-th row, $$$j$$$-th column.
Fig. 2. the turned box The first line contains three integers $$$n, m, h\ (1 \leq n, m, h \leq 100)$$$.
For the next $$$n$$$ lines, each contains $$$m$$$ integers. The $$$j$$$-th integer in the $$$i$$$-th line is $$$A_{i,j}$$$.
Output $$$h$$$ lines, each contains $$$m$$$ integers. The $$$j$$$-th integer in the $$$i$$$-th line is $$$B_{i,j}$$$.
3 4 5 1 2 3 4 2 0 1 5 1 3 2 2
3 2 3 3 1 2 2 3 0 1 1 2 0 0 0 2 0 0 0 1
You should take gravity into consideration.
Master Yi likes palindrome very much. He defines lucky strings as strings that contain exactly one palindrome substring whose length is greater than or equal to $$$2$$$.
Now, please help him find out how many lucky strings are there among all strings of length $$$n$$$ which only contains characters in $$$\{\texttt{b}, \texttt{i}, \texttt{t}\}$$$. Since this number may be too large, output it modulo $$$10^9 + 7$$$.
Each test contains multiple test cases.
The first line contains an integer $$$t\ (1\le t\le 10^4$$$) — the number of test cases.
The only line of each test case contains a single integer $$$n\ (1\le n\le 10^9)$$$.
For each test case, print one integer — the number of lucky strings with length $$$n$$$ modulo $$$10^9 + 7$$$.
2 2 3
3 18
Aqua and Hiyori love combination.
Today, Aqua has a sequence $$$a$$$ with length of $$$n$$$, and she wants to combine the sequence. She can get all $$$x$$$ which satisfies that there exists $$$\lbrace c_1,c_2,\cdots,c_n\rbrace,c_i \in \mathbb{N}$$$, and $$$x=\sum_{i=1}^n c_ia_i$$$. Hiyori decides to test Aqua, so she will set $$$q$$$ queries.
In each query, Hiyori will give Aqua two integers $$$A,B$$$. According to the answer of the last query called $$$\mathrm{lastans}$$$, the present query has two parameters $$$l=\min(A\oplus \mathrm{lastans},B\oplus \mathrm{lastans})$$$, $$$r=\max(A\oplus \mathrm{lastans},B\oplus \mathrm{lastans})$$$. Initially, $$$\mathrm{lastans}=0$$$.
Here $$$\oplus$$$ denotes bitwise XOR (exclusive-or).
Aqua should answer that how many numbers in $$$[l,r]$$$ has she got. But she is stupid, could you help her?
The first line contains two integers $$$n,q\ (1\leq n,q\leq 10^6)$$$, indicating the length of the sequence $$$a$$$ and the number of queries.
The second line contains $$$n$$$ integers $$$a_1,a_2,\cdots,a_n\ (2\leq a_i\leq 10^9)$$$.
The next $$$q$$$ lines, each line contains two integers $$$A,B\ (0\leq A,B\leq 10^{18})$$$, indicating a query. It is guaranteed that $$$n\times \min_{i=1}^n a_i\leq 10^6$$$.
Print $$$q$$$ lines. The $$$i$$$-th line the contains answer for the $$$i$$$-th query.
2 3 7 4 1 6 1 5 1 2
1 2 1
5 3 6 7 8 9 3 0 5 0 6 0 5
2 1 1
Although ZYW has graduated from BIT, he still comes to BIT often to have dinner with his friends. After a period of observation, ZYW found that the traffic light cycle of all intersections near BIT is $$$T$$$, which means that for any traffic light, the color of it is same at time $$$t_0$$$ and time $$$t_0+T$$$ for any $$$t_0$$$.
After detailed investigation, ZYW records the schedule of traffic light changes, i.e., the time when passing is allowed and the time when passing is not allowed. Note that the traffic light in this city allows people to enter the intersection at any time, but all people must leave the intersection within the allowed time period.
In this city there are $$$n$$$ intersections and $$$m$$$ bidirectional roads. The $$$i$$$-th road connects the $$$u_i$$$-th intersection with the $$$v_i$$$-th intersection and takes $$$w_i$$$ time to pass. BIT is at the $$$n$$$-th intersection and ZYW's home is at the $$$1$$$-st intersection. Now ZYW wants to know the minimum time it takes to get from his house to BIT at any time from $$$0$$$ to $$$T-1$$$.
The first line contains three integers $$$n,m,T\ (1\le n,T\le 500, 1\le m\le 2000) $$$, indicating there are $$$n$$$ intersections and $$$m$$$ roads in this city and the cycle of each traffic light is $$$T$$$.
In the next $$$n$$$ lines, each line contains a $$$\text{01}$$$ string of length $$$T$$$. The $$$i$$$-th intersection is allowed to pass at time $$$j$$$ if the $$$j$$$-th character in the $$$i$$$-th line is $$$\text{1}$$$, and not allowed to pass otherwise.
In the next $$$m$$$ lines, each line contains three integers $$$u,v,w\ (1\le u,v\le n,1\le w\le 10^9) $$$, indicating a road connecting $$$u$$$ and $$$v$$$ intersections, and it takes $$$w$$$ time to pass.
Output $$$T$$$ integers representing the minimum time ZYW needs to reach BIT if ZYW starts from each time in $$$[0, T)$$$.
It is guaranteed that ZYW can reach BIT.
4 4 5 11111 00001 01000 00000 1 2 1 2 4 1 1 3 1 3 4 1
2 4 3 2 3
Aqua and Hiyori love equal numbers.
Aqua loves two integers $$$x$$$ and $$$y$$$, and she wants to perform some operations to make $$$x$$$ and $$$y$$$ equal. In one step, Aqua can do one of the following operations:
1. $$$x\leftarrow x+1$$$.
2. $$$y\leftarrow y+2$$$.
Now, Hiyori sets a problem to Aqua: What is the minimum number of steps required to make $$$x$$$ and $$$y$$$ equal?
But Aqua is stupid, could you help her?
The first and only line contains two integers $$$x\ (0\leq x\leq 10^9)$$$ and $$$y\ (0\leq y\leq 10^9)$$$.
Output a single integer — the minimum number of operations required to make $$$x$$$ and $$$y$$$ equal.
5 10
5
9 3
3
ZYW has too many books to organize! But he has already set up a flag in front of his roommates that he will finish sorting out his books tonight. Each book of ZYW has an attribute $$$a_i$$$ to describe the usage frequency of the book. The smaller the $$$a_i$$$, the higher usage frequency. ZYW hopes to make books with high usage frequency in front of books with low usage frequency. But now the books on the shelf are out of order.
Sadly, ZYW has a very serious obsessive-compulsive disorder. He can only take a book from the front of the shelf or put a book in the back of the shelf, while inserting or taking out a book from any other position is prohibited. ZYW also made space to organize books. Books can be stacked here, that is, he can put a book at the top or take a book from the top.
Now the deadline is coming. ZYW hopes you can help him plan how to organize his books.
Specifically, there are $$$n$$$ books on ZYW's bookshelf, and each book has the attribute $$$a_i$$$ to describe its frequency of use. ZYW can perform one of the following two operations at a time:
- Take a book from the front of the shelf and put it on the top of the book stack.
- Take a book from the top of the book stack and put it on the back of the shelf.
The first line contains an integer $$$n\ (1\le n\le 10^5)$$$, the number of books.
The next line contains $$$n$$$ integers, the $$$i$$$-th integer $$$a_i\ (0\le a_i\le 10^9)$$$ describes the usage frequency of the $$$i$$$-th book. The input order is from front to back.
The first line contains a single integer $$$k$$$, representing the number of operations. Note that $$$k$$$ should not exceed $$$40\times n$$$.
In the second line, print a string of length $$$k$$$ consisting of $$$1$$$ and $$$2$$$, representing your operation type in order.
5 3 2 4 5 1
8 11221212
To improve the commuting efficiency of employees, Master Yi's company has planned a new shuttle operation plan. The office location and the home of its employees are like a tree with $$$n$$$ nodes where the vertex $$$1$$$ is the company as well as the root of the tree, and each of the other nodes is the home of an employee.
The company plans to use several shuttles, which will depart from the company in all directions without turning back, and a shuttle bus has only $$$k$$$ seats for employees. The employee immediately gets off the bus and goes home when the bus reaches the node of his/her home. To save money, please help them calculate the minimum number of shuttles needed to take all company employees home after work.
The first line contains a single integer $$$t\ (1\le t\le 10^4)$$$, the number of test cases. For each test case:
The first contains $$$2$$$ integers $$$n\ (2\le n\le 2 \cdot 10^5)$$$ and $$$k\ (1\le k\le 50)$$$, which shows the number of nodes and the number of seats on each bus.
The next $$$n−1$$$ lines show the edges of the tree — one edge per line. Each line contains two integers $$$u,v\ (1\le u,v\le n;u\neq v)$$$ representing an edge.
It is guaranteed that the given edges form a tree.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, print a single integer, which shows the minimum number of shuttles needed.
16 21 21 34 25 23 6
3
16 21 21 34 25 23 6
3
Fig. 1. the tree in the example We can send $$$5$$$ employees off with $$$3$$$ shuttles, here is an optimal arrangement.
- The first bus goes from the root node to node $$$4$$$, and the employees who live in nodes $$$2$$$ and $$$4$$$ sit on this bus.
- The second bus goes from the root node to node $$$5$$$, and the employee who lives in node $$$5$$$ sits on this bus.
- The third bus goes from the root node to node $$$6$$$, and the employees who live in node $$$3$$$ and node $$$6$$$ sit on this bus.
The government is very concerned about the happiness index of residents. In the practical work of ideological and political courses, Master Yi collected the happiness index of $$$n$$$ residents in his hometown as an integer array $$$a_1, a_2, \cdots, a_n$$$.
In this task, Master Yi wants to know how many intervals are there satisfying that the average happiness index in this interval is approximately $$$k$$$. In other words, please help him calculate how many intervals $$$[l,r]$$$ satisfy $$$\lfloor{\frac{a_l+a_{l+1}+\cdots+a_r}{r-l+1}}\rfloor=k$$$.
The first line contains a single integer $$$t\ (1\le t\le 10^4)$$$, the number of test cases. For each test case:
The first line contains $$$2$$$ integers $$$n\ (1\le n\le 2\cdot 10^5)$$$ and $$$k\ (0\le k\le 10^9)$$$, the number of the interviewed residents and the required happiness index.
The second line contains $$$n$$$ integers $$$a_1, a_2, \cdots, a_n\ (0\le a_i\le 10^9)$$$, which are the happiness indexes of each interviewed resident.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5\cdot 10^5$$$.
For each test case, print the answer in a single line, which is the number of subsegments satisfying the condition.
13 22 1 3
3
In the first example, the subsegments satisfying the condition are $$$[2]$$$, $$$[1,3]$$$ and $$$[2,1,3]$$$, each has an average happiness index of $$$2$$$.
Aqua and Hiyori love strings.
Today, Aqua gets a pretty string $$$s$$$ of length $$$n$$$. To improve Aqua's intelligence, Hiyori sets a problem for Aqua.
A set $$$S$$$ is said to be a pretty set when its elements are substrings of $$$s$$$ and for every pair of different substrings $$$(A, B)$$$ in $$$S$$$, $$$A$$$ is not the suffix of $$$B$$$ and $$$B$$$ is not the suffix of $$$A$$$.
Now, for each $$$k=1,2,\cdots,n$$$, Aqua should answer the number of pretty set $$$S$$$ which satisfies $$$|S|=k$$$. But she is stupid, could you help her?
A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.
A string $$$a$$$ is a suffix of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from the beginning.
The only line contains a string $$$s\ (1\leq |s| \leq 10^5)$$$, consists of only lowercase letters.
Print $$$n$$$ lines. The $$$i$$$-th line should contain the answer for $$$k=i$$$ modulo $$$998244353$$$.
abb
5 6 2
aabdeffdg
42 741 7151 41208 145149 305478 351810 170100 0
In the first example:
- When $$$k=1$$$, $$$S=\lbrace \mathrm{a}\rbrace,\lbrace \mathrm{b}\rbrace,\lbrace \mathrm{ab}\rbrace,\lbrace \mathrm{bb}\rbrace,\lbrace \mathrm{abb}\rbrace$$$.
- When $$$k=2$$$, $$$S=\lbrace \mathrm{a},\mathrm{b}\rbrace,\lbrace \mathrm{a},\mathrm{ab}\rbrace,\lbrace \mathrm{a},\mathrm{abb}\rbrace,\lbrace \mathrm{a},\mathrm{bb}\rbrace,\lbrace \mathrm{ab},\mathrm{bb}\rbrace,\lbrace \mathrm{ab},\mathrm{abb}\rbrace$$$.
- When $$$k=3$$$, $$$S=\lbrace \mathrm{a},\mathrm{ab},\mathrm{abb}\rbrace,\lbrace \mathrm{a},\mathrm{ab},\mathrm{bb}\rbrace$$$.
Aqua and Hiyori love playing games.
There are $$$n$$$ piles of stones, the $$$i$$$-th pile has $$$a_i$$$ stones.
They take turns to make a move. Aqua makes the first move.
In one move, the player must choose a non-empty pile $$$i$$$ and select an integer $$$x$$$ from the chosen set satisfying $$$2\leq 2x\leq a_i+1$$$. Then the player should remove $$$x$$$ stones from the pile $$$i$$$.
The player who can not make a move loses the game.
You want to know whether Aqua will win the game, if both of them play optimally.
The first line contains an integer $$$n\ (1\leq n\leq 10^6)$$$, indicating the number of the piles.
The second line contains $$$n$$$ integers $$$a_1,a_2,...,a_n\ (0\leq a_i\leq 10^9)$$$, indicating the number of stones in each pile.
Print "Alice" (without quotes) if the Aqua will win, otherwise print "Bob" (without quotes).
8 2704 3196 108 820 520 1976 3524 3520
Bob
3 3 5 9
Alice
Make sure to print "Alice" and "Bob" instead of "Aqua" and "Hiyori".
ZYW has high academic abilities so many tutors want to work with ZYW. However, ZYW did not want to choose casually, so he gave the tutors a task. The tutor who achieves the best results will be favored by ZYW.
The problem is as follows. Given a $$$n \times n$$$ matrix $$$A$$$, you can choose a number in the matrix and change it to any real number, but you can only do this at most once. You need to minimize $$$|\det(A)|$$$, where $$$\det(A)$$$ represents the determinant of the matrix $$$A$$$.
ZYW can of course compute the result immediately, but your tutor is not very good at this. Can you help your tutor? Note that you do not need to output exactly how the change was made.
The first line contains an integer $$$n\ (1\le n\le 100)$$$.
For the following $$$n$$$ lines, each line contains $$$n$$$ integers, where the $$$j$$$-th number of the $$$i$$$-th line indicates $$$A_{i,j}\ (-10^9\le A_{i,j}\le 10^9)$$$.
Print a single number — the minimum value of $$$|\det(A)|$$$.
If the standard answer is $$$a$$$, and your answer is $$$b$$$, your answer will be considered correct if $$$|\frac{a-b}{\max(a,1)}| \lt 10^{-6}$$$.
3 1 1 4 5 1 4 0 0 0
0
The Travelling Salesman Problem (TSP) asks that given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city.
Unfortunately, the TSP is an NP-hard problem. So instead of expecting you to solve it, we propose a Fake Traveling Salesman Problem (FTSP). In FTSP, the map is defined on a $$$n \times m$$$ grids. The salesman starts at $$$(1,1)$$$. He can only move to four adjacent cities each step and can't move out of the grids. He wants to visit each grid exactly once and end up at $$$(x,y)$$$.
Help the salesman find a valid route satisfying such conditions.
The only line contains four integers $$$n,m,x,y\ (2 \leq n,m \leq 500, 1 \leq x \leq n, 1 \leq y \leq m)$$$. It is guaranteed that $$$(x,y) \neq (1,1)$$$.
Output "Yes"(without quotes) or "No"(without quotes) in the first line, represents whether you can find a route.
If the route exists, output $$$n \times m$$$ lines. The $$$i$$$-th line contains two integers $$$a,b$$$, which means the salesman should be in grid $$$a,b$$$ in the $$$i$$$-th step. You should guarantee that:
- $$$a=1,b=1$$$ holds for the first line.
- $$$a=x,b=y$$$ holds for the last line.
- $$$1 \le a \le n, 1 \le b \le m$$$.
- The distance between two adjacent steps is $$$1$$$.
2 2 2 2
No
3 3 2 2
Yes 1 1 2 1 3 1 3 2 3 3 2 3 1 3 1 2 2 2
3 4 3 2
Yes 1 1 1 2 1 3 1 4 2 4 3 4 3 3 2 3 2 2 2 1 3 1 3 2
You are given a tree with nodes labeled from $$$1 \sim n$$$, and the root of the tree is vertex $$$1$$$. There are multiple queries, each of which gives one node $$$x$$$, and you need to find $$$$$$ \displaystyle\sum_{u\in T(x)}\displaystyle\sum_{\begin{subarray}{l}v\in T(x)\\ v \lt u\end{subarray}}[\gcd(u,v)=1] $$$$$$ where $$$T(x)$$$ denotes the subtree with root $$$x$$$.
$$$\gcd(u,v)$$$ denotes the greatest common divisor of $$$u$$$ and $$$v$$$.
The value $$$[\ast]$$$ is $$$1$$$ if $$$\ast$$$ is true, otherwise it is $$$0$$$.
The first line contains two integers $$$n,q\ (1\leq n,q\leq 10^5)$$$.
The next line contains $$$n-1$$$ integers, the $$$i$$$-th of which shows the parent node of node $$$i+1$$$.
Each of the next $$$q$$$ lines contains an integer $$$x$$$, which shows the node $$$x$$$ to be queried.
For each query, output your answer as a single integer.
2 2 1 1 2
1 0