Jelefy is playing the Tower of Hanoi with a special rule.
The Tower of Hanoi has three pillars, $$$A$$$, $$$B$$$, and $$$C$$$, on which disks can be stacked. Disks can be moved between different pillars, but must adhere to the following rules:
At the beginning, Jelefy randomly stacks $$$n$$$ disks of different sizes on pillar $$$A$$$ and leaves pillars $$$B$$$ and $$$C$$$ empty. Under the above conditions, Jelefy wants to know how many moves are needed to move all the disks from pillar $$$A$$$ to pillar $$$B$$$.
The first line contains an integer $$$T$$$ ($$$1\leq T\leq 10^4$$$), indicating the number of test cases.
For each test case: The first line contains an integer $$$n$$$ ($$$1\leq n\leq 10^5$$$), representing the number of disks on pillar $$$A$$$ in the initial state.
The second line contains $$$n$$$ integers $$$p_1,p_2,\ldots,p_n$$$ ($$$1\leq p_i\leq n$$$), where $$$p_i$$$ represents the diameter of the $$$i$$$-th disk on pillar $$$A$$$ from bottom to top. It is guaranteed that $$$p_1,p_2,\ldots,p_n$$$ form a permutation of length $$$n$$$, i.e., each integer from $$$1$$$ to $$$n$$$ appears exactly once in the sequence.
For all test cases, it is guaranteed that $$$\sum n\leq 2\times 10^5$$$.
For each test case, output an integer on a single line, representing the minimum number of moves required.
351 5 3 2 451 2 3 4 565 3 6 1 4 2
11519
In the first example, one possible solution with the minimum number of moves is as follows ($$$X\rightarrow Y$$$ indicates moving the top disk from pillar $$$X$$$ to the top of pillar $$$Y$$$):
Li Hua has a deck of cards, each card has three attributes: color, number, and value. The color of each card can be represented by an integer in the range $$$[1,n]$$$, and similarly, each card will have an integer number in the range $$$[1,n]$$$ written on it. Based on the different numbers and colors, these cards are divided into $$$n^2$$$ types.
For convenience, the type number of a card with color $$$x$$$ and number $$$y$$$ is denoted as $$$(x-1)\times n+y$$$. In the deck, there are a total of $$$a_i$$$ cards of the $$$i$$$-th type, and each card has a value of $$$b_i$$$.
At the beginning, Li Hua's hand is empty, the initial score is $$$0$$$, and Li Hua will play $$$k$$$ rounds of the game. At the beginning of each round, Li Hua will randomly draw a card from the remaining cards in the deck, with an equal probability of drawing each card. Then, if the hand contains cards with the same number or color as the drawn card, Li Hua will return all cards that meet the above conditions along with the originally drawn card to the deck; otherwise, the drawn card will be put in the hand.
After each round, Li Hua's score will be increased by the value of all the cards in the hand. Please help Li Hua calculate the expected total score after $$$k$$$ rounds, taken modulo $$$998244353$$$.
The first line contains two positive integers $$$n,k$$$ ($$$2\le n\le 4, 1\le k\le 10^9$$$), representing the number of color and number types and the number of game rounds.
The second line contains $$$n^2$$$ integers $$$a_i$$$ ($$$0\le a_i \lt 998244353$$$), representing the quantity of each type of card in the deck.
The third line contains $$$n^2$$$ integers $$$b_i$$$ ($$$0\le b_i \lt 998244353$$$), representing the score of each type of card.
It is guaranteed that there will be no situation where all cards can be held in the hand at the same time, and $$$\sum a_i \lt 998244353$$$.
Output a single integer, representing the expected total score after $$$k$$$ rounds.
2 21 1 1 12 1 1 1
582309208
2 41 2 3 44 3 2 1
570601408
For the first example, the correspondence between the final score and the probability is as follows:
| Score | $$$1$$$ | $$$2$$$ | $$$3$$$ | $$$4$$$ | $$$5$$$ |
| Probability | $$$\frac 12$$$ | $$$\frac 16$$$ | $$$\frac 16$$$ | $$$\frac 1{12}$$$ | $$$\frac 1{12}$$$ |
For the second example, the expected score is $$$\frac{5041}{810}$$$.
Given a sequence of length $$$n$$$, $$$a_1,a_2,\ldots,a_n$$$, initially $$$a_i=i$$$. Perform $$$n-1$$$ operations on the sequence, where the $$$i$$$-th operation involves choosing an integer $$$j$$$ uniformly at random from the range $$$[1,n-i]$$$, and setting $$$a_j$$$ to $$$a_j+2a_{n-i+1}$$$.
Find the value of $$$a_1$$$ modulo $$$998244353$$$ after all operations are completed.
The first line contains a positive integer $$$T$$$ ($$$1\leq T\leq 10^4$$$), indicating the number of test cases.
Following are $$$T$$$ lines, each containing a positive integer $$$n$$$ ($$$1\leq n\leq 10^9$$$), representing the length of the sequence.
$$$T$$$ lines, each containing an integer representing the value of $$$a_1$$$ modulo $$$998244353$$$.
3425
30 5 55
3435
30 14 55
3813
204 1 14
You are a craftsman in the Kuanzhai Alley. One day, a customer ordered a black and white bead string from you. The black and white bead string is shaped like a chain, with black and white beads arranged on it. The customer also presented you with $$$k$$$ conditions, each of which is as follows:
Here, a substring refers to a continuous segment of beads in the black and white bead string.
Please construct a black and white bead string for the customer that satisfies all the above conditions and has the minimum length. To ensure that the bead string you construct meets the above conditions, you also need to provide the position of a substring that satisfies each condition.
The first line contains an integer $$$k$$$ ($$$1\leq k\leq 10^5$$$), indicating the number of conditions.
The next $$$k$$$ lines, where the $$$i$$$-th line contains two integers $$$x_i,y_i$$$ ($$$1\leq x_i\leq 10^6,0\leq y_i\leq x_i$$$), representing the content of the $$$i$$$-th condition.
The first line contains an integer $$$l$$$, representing the minimum length of the black and white bead string that satisfies the conditions.
The second line contains a string consisting of 0 and 1, with a length of $$$l$$$, representing the black and white bead string you constructed. Here, 0 represents a white bead, and 1 represents a black bead.
The next $$$k$$$ lines, where the $$$i$$$-th line contains an integer $$$p_i$$$, representing the starting position of a substring that satisfies the $$$i$$$-th condition in the bead string. Here, the position of the bead string is numbered starting from $$$0$$$.
33 13 22 0
4 1100 1 0 2
42 13 34 03 2
7 1110000 2 0 3 1
bjh has a string $$$s$$$ of length $$$n$$$ consisting only of the characters 0 and 1.
bjh can choose a maximal substring of length greater than $$$1$$$ that consists of only one type of character, and change the entire substring to the opposite character (for example, in the string $$$11001$$$, after one operation it can be changed to $$$0001$$$ or $$$1111$$$).
bjh will continue to operate until the string can no longer be modified. Please help him find the difference between the maximum and minimum number of operations in all operation scenarios.
This problem contains multiple test cases. The first line contains an integer $$$T$$$ ($$$1\leq T\leq 10^4$$$), indicating the number of test cases.
For each test case, the first line contains an integer $$$n$$$ ($$$1\leq n\leq 10^5$$$), indicating the length of the string.
The second line contains a string $$$s$$$, representing the initial string.
It is guaranteed that the sum of all $$$n$$$ in the input does not exceed $$$10^6$$$.
For each test case, output an integer representing the difference between the maximum and minimum number of operations.
2511001511000
1 0
Assume you are a student named Li Hua at UESTC. In a certain episode of "One Stop to the End" in the year 4202, you participated as a contestant in the program's recording. Unlike the rules from over 2000 years ago, the program does not involve contestants competing in pairs and answering questions in a round-robin format. Instead, each contestant answers questions individually, with the following specific rules:
Before the contestant's answering phase begins, the system will randomly select $$$n$$$ questions from the question bank, each with a score of $$$a_i$$$ based on its difficulty level. The host will announce all the questions and their scores at the beginning, and then the contestant's answering phase will commence.
To make the program more interesting, contestants cannot freely choose the order in which they answer the questions. Specifically, except for the first question, each question has one and only one prerequisite question. A contestant can only answer a question after correctly answering its prerequisite question. The program ensures that the prerequisite question number for question $$$i$$$ is always less than $$$i$$$.
Furthermore, if a contestant submits an incorrect answer to a question, the floor beneath him/her will immediately open, causing the contestant to fall and end their answering. The sum of the scores of all the questions answered correctly before this point will be the contestant's final score. If a contestant answers all the questions correctly, the sum of the scores of all the questions will be the contestant's final score.
Now that you have read all the questions, based on your knowledge, you have determined the probability $$$p_i$$$ of answering each question correctly. You need to devise the optimal answering strategy to maximize your expected score in the shortest time possible. Please output this score.
The first line contains a positive integer $$$n$$$ ($$$2\le n\le 10^5$$$), representing the number of questions.
The next line contains $$$n$$$ positive integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\leq a_i\leq 10^6$$$), where $$$a_i$$$ represents the score of question $$$i$$$.
The following line contains $$$n$$$ real numbers $$$p_1,p_2,\ldots,p_n$$$ ($$$0 \lt p_i \lt 1$$$), where $$$p_i$$$ represents the probability of answering question $$$i$$$ correctly.
The next line contains $$$n-1$$$ positive integers $$$t_1,t_2,\ldots,t_{n-1}$$$ ($$$1\leq t_i\leq i$$$), where $$$t_i$$$ represents the number of the prerequisite question for question $$$i+1$$$.
Output a single real number, representing the expected score under the optimal answering strategy.
If your output is $$$a$$$ and the correct answer is $$$b$$$, your answer will be considered correct if and only if $$$\frac{|a-b|}{\max(1,b)}\le 10^{-9}$$$.
55 4 3 2 10.9 0.89 0.88 0.87 0.861 1 2 2
11.572522416
In the sample case, it is obvious that answering the questions in the order of $$$1,2,3,4,5$$$ will yield the optimal result, as the higher-scoring questions also have a higher probability of being answered correctly.
Given a trie tree with $$$n$$$ nodes, with node $$$1$$$ as the root, and each node has a character on the edge to its parent, and the characters on the edges to the same parent are all different. The path from the root to each node represents a word, which is formed by concatenating the characters on the path. At each node $$$i$$$, there is a weight $$$c_i$$$, indicating the number of times the word represented by that node needs to be written.
You have a cache, and you can choose any number of words to put in the cache. When writing a word, it costs $$$a$$$ for each character. When a complete word is written, you can choose to end the current word and start spelling the next word. The cache will always suggest the word with the smallest lexicographical order that has the current written characters as a prefix, and at this point, you can spend $$$b$$$ to directly write out this word, and end the spelling of the current word, and start spelling the next word. Note that a string itself is also considered as its own prefix.
Find the minimum cost required to complete the spelling of all words on the trie tree.
The first line contains three integers $$$n,a,b$$$ ($$$1\leq n\leq 2\times 10^5,0\leq a,b\leq 10^4$$$), representing the size of the trie tree, the cost of writing a character, and the cost of using the cache to write a word.
Next $$$n$$$ lines, where the $$$i$$$-th line first contains two integers $$$c_i,k_i$$$ ($$$0\leq c_i\leq 10^4,0\leq k_i \lt n$$$), representing the weight of the $$$i$$$-th node and the number of child nodes of the $$$i$$$-th node. Next, input $$$k_i$$$ integers $$$son_{i,1},son_{i,2},\ldots,son_{i,k_i}$$$, representing the numbers of the child nodes of the $$$i$$$-th node, given in increasing order of lexicographical order between the characters on the edge from the $$$i$$$-th node to the child nodes.
It is ensured that $$$c_1=0$$$.
Output a single integer, representing the minimum cost required to complete the spelling of all words on the trie tree.
4 2 3 0 2 3 2 3 0 2 1 4 4 0
22
The explanation to the sample test case is as follows.
Assume that the edges to the child nodes of each node are encoded by $$$a,b,\ldots$$$ in lexicographic order from small to large. The optimal solution is to put $$$aa$$$ in the cache, so $$$aa$$$ can be typed out using prompts at a cost of $$$3\times 4$$$, and both $$$a$$$ and $$$b$$$ are typed out directly. The total cost is $$$3\times 4+2\times 1\times 2+2\times 1\times 3=22$$$.
There is a juicer that can make a cup of juice of any volume per minute.
There are $$$n$$$ people lined up. The $$$i$$$-th person will walk to the juicer at the $$$t_i$$$-th minute and take the largest cup of juice that has been made so far. The $$$i$$$-th person will be satisfied if they get a cup of juice with a volume greater than or equal to $$$a_i$$$. If there is no juice at that time, the $$$i$$$-th person will also be unsatisfied.
Determine if it is possible to satisfy all the people. If so, output the minimum total volume of juice needed to satisfy everyone.
The first line contains an integer $$$n$$$ ($$$1\leq n\leq 2 \times 10^5$$$), representing the number of people in the queue.
The next line contains $$$n$$$ integers $$$t_1,t_2,\ldots,t_n$$$ ($$$1\leq t_1\leq t_2\leq\ldots\leq t_n\leq 10^9$$$), where $$$t_i$$$ represents the time when the $$$i$$$-th person arrives at the juicer. If two people arrive at the same time, the order is determined from left to right as given in the input.
The following line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\leq a_i\leq 10^9$$$), where $$$a_i$$$ represents the volume requirement of the $$$i$$$-th person for the juice.
If it is not possible to satisfy all the people, output $$$-1$$$.
Otherwise, output a single integer representing the minimum total volume needed.
51 3 4 6 63 8 2 7 4
24
51 3 4 5 53 8 2 7 4
26
Explanation for Example 1:
| Time | Production | Taken |
| $$$1$$$ | $$$3$$$ | $$$3$$$ |
| $$$2$$$ | — | — |
| $$$3$$$ | $$$8$$$ | $$$8$$$ |
| $$$4$$$ | $$$2$$$ | $$$2$$$ |
| $$$5$$$ | $$$4$$$ | — |
| $$$6$$$ | $$$7$$$ | $$$7,4$$$ |
Explanation for Example 2:
| Time | Production | Taken |
| $$$1$$$ | $$$3$$$ | $$$3$$$ |
| $$$2$$$ | $$$4$$$ | — |
| $$$3$$$ | $$$8$$$ | $$$8$$$ |
| $$$4$$$ | $$$4$$$ | $$$4$$$ |
| $$$5$$$ | $$$7$$$ | $$$7,4$$$ |
| $$$6$$$ | — | — |
There is a sequence of length $$$n$$$, and the weight of the $$$i$$$-th number is $$$a_i$$$. Two players, A and B, are playing a game, taking turns to operate on the sequence. Each player has two options to choose from:
If the final total weight obtained by A is greater, then A wins; otherwise, B wins.
A goes first to make a move. Determine if A has a winning strategy. It is guaranteed that the sum of $$$a_i$$$ is odd.
This problem contains multiple test cases.
The first line contains an integer $$$T$$$ ($$$1\leq T\leq 10^5$$$), indicating the number of test cases.
For each test case, the input format is as follows.
The first line contains an integer $$$n$$$ ($$$1\leq n\leq 5 \times 10^5$$$), indicating the initial length of the sequence.
The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\leq a_i\leq 10^9$$$), representing the initial sequence.
It is guaranteed that $$$\sum n\leq 10^6$$$ and $$$\sum a_i$$$ is odd.
For each test case, if A has a winning strategy, output YES; otherwise, output NO.
333 6 421 232 5 6
NO YES NO
Explanation for Example 1:
In all cases, B can obtain a higher weight with the optimal strategy, so A cannot win.
Explanation for Example 2:
If A chooses the weight $$$2$$$, then B can obtain a weight of $$$1$$$.
Therefore, A has a winning strategy.
Alice and Bob are two creatures in a $$$k$$$-dimensional space. In their living space, there are $$$2n$$$ feature points, where the coordinates of the $$$i$$$-th feature point are $$$(x_{i,1},x_{i,2},\ldots,x_{i,k})$$$.
In this space, the distance between two points is defined as their Manhattan distance (i.e., the distance $$$\text{dist}_{i,j}=\sum_{p=1}^{k}|x_{i,p}-x_{j,p}|$$$ between point $$$i$$$ and point $$$j$$$).
Alice and Bob need to collect these feature points. They take turns to select a point from these $$$2n$$$ points, and once a point is selected by any one of them, it cannot be chosen again. Alice goes first. Alice puts her selected points into set $$$S_1$$$, while Bob puts his selected points into set $$$S_2$$$.
$$$\text{val}(S)$$$, The value of a set $$$S$$$, is the sum of distances between all unordered pairs of points in the set, i.e. $$$\text{val}(S)=\sum_{\text{point }i,j\text{ in }S,i \lt j}\text{dist}_{i,j}$$$. Alice wants to maximize $$$\text{val}(S_1)-\text{val}(S_2)$$$, while Bob wants to minimize $$$\text{val}(S_1)-\text{val}(S_2)$$$.
If Alice and Bob both adopt the optimal strategy, please calculate the value of $$$\text{val}(S_1)-\text{val}(S_2)$$$ in the end.
The first line contains two integers $$$n,k$$$ ($$$1\leq n,k\leq 10^5,n\times k\leq 10^5$$$), representing half the number of feature points and the number of dimensions in the space, respectively.
The next $$$2n$$$ lines each contain $$$k$$$ integers $$$x_{i,1},x_{i,2},\ldots,x_{i,k}$$$ ($$$-10^8\leq x_{i,j}\leq 10^8$$$), representing the coordinates of the $$$i$$$-th feature point.
Output an integer, representing the value of $$$\text{val}(S_1)-\text{val}(S_2)$$$ when both Alice and Bob adopt the optimal strategy.
2 21 00 11 10 0
0
Given a sequence of length $$$n$$$, $$$a_1,a_2,\ldots,a_n$$$.
You need to select an integer $$$k$$$ ($$$1\leq k\leq n$$$), and then perform any number of operations on the sequence. Each operation can select $$$k$$$ different positions in the sequence, and multiply the numbers at these positions by the same non-zero integer, until all the numbers in the sequence are equal.
Output the maximum value of $$$k$$$ that satisfies the condition.
This problem contains multiple test cases. The first line contains an integer $$$T$$$ ($$$1\leq T\leq 10^4$$$), indicating the number of test cases.
For each test case, the first line contains an integer $$$n$$$ ($$$1\leq n\leq 10^5$$$), indicating the length of the sequence.
The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\leq a_i\leq 10^9$$$), representing the given sequence.
It is guaranteed that the sum of all $$$n$$$ in the input does not exceed $$$10^6$$$.
For each test case, output an integer representing the maximum value of $$$k$$$ that satisfies the condition.
132 6 2
2