It is a well known fact that people in Switzerland like to go out for walks, and a less known fact is that students at ETH actually attend classes (This may be a myth).
The city of Zurich can be modelled as a graph of $$$n$$$ locations and $$$n-1$$$ bidirectional roads, in which it is possible to travel between any pair of locations using the given roads. We also know that there are $$$q$$$ students that go to ETH, with the $$$i$$$-th student living at location $$$a_i$$$ and having a class today at location $$$b_i$$$.
Now today each student will go out for a random walk as follows. It will start at its home, then choose any adjacent location to its current location with equal probability that they hasn't visited today and walk there. If there exists no such location they will walk the same way back home. If a student ever walks to a location in which they have a class in, they will attend the class.
Our question for you is, what is the probability that the $$$i$$$-th student will attend their own class. It can be shown that this answer can always be expressed as a fraction $$$\frac{1}{p}$$$ where $$$p$$$ is an integer. Output $$$p$$$ modulo $$$998244353$$$.
The first line contains two integers $$$n, q$$$ ($$$2 \leq n \leq 10^5); (1 \leq q \leq 10^5)$$$, the number of locations in Zurich and the number of students attending ETH.
The next $$$n-1$$$ lines contain two integers each $$$u_i, v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$), corresponding to a bidirectional road between location $$$u_i$$$ and $$$v_i$$$.
The next $$$q$$$ lines contain two integers each $$$a_i, b_i$$$ ($$$1 \leq a_i, b_i \leq n)$$$, giving that the $$$i$$$-th student lives at location $$$a_i$$$ and has a class at location $$$b_i$$$, it is guaranteed that $$$a_i \neq b_i$$$.
Output should contains $$$q$$$ lines, for each line print $$$p$$$ modulo $$$998244353$$$ such that the probability of the $$$i$$$-th student attending their class is $$$\frac{1}{p}$$$.
5 41 21 34 51 41 53 53 13 2
3 2 1 2
8 51 22 34 51 46 76 81 84 27 84 56 74 1
4 1 2 2 2
Paul and Micha, tired after a lecture, decide to go to Limmat. But they take the brave decision and get on the Polybahn. In the middle of the ride, the Polybahn gets stuck by a tree, and out of boredom, Paul challenges Micha to count the number of connected subgraphs of this tree, where every subgraph has maximum matching of size 1. Micha gets confused by Paul's mind-bending challenge and calls you for help to count this number in modulo $$$10^9 + 7 $$$.
Luckily, Micha recalls the definition of a subgraph: A subgraph of a tree is some set of the tree vertices and some set of the tree edges. The set of edges must meet the following condition: Both ends of each edge from the set must belong to the chosen set of vertices.
The first line contains a single integer $$$n$$$ $$$(2 \leq n \leq 10^5)$$$.
In the next $$$n - 1$$$ lines you are given the edges of the tree. In each of these lines you are given $$$u$$$ and $$$v$$$ $$$(1 \leq u, v \leq n)$$$ describing an edge between nodes $$$u$$$ and $$$v$$$.
Print a single integer modulo $$$10^9+7$$$, number of connected subgraphs of the tree, where every subgraph has maximum matching of size exactly 1.
31 22 3
3
55 33 45 13 2
9
The tree in the first sample has 3 connected subgraphs with maximum matching of size 1 each.
Alice likes geometric objects, in particular rectangles. Today she drew a grid on a piece of paper, consisting of $$$n$$$ horizontal and $$$m$$$ vertical lines. Since rectangles are her favorite shapes, she wants to know the number of distinct rectangles on the grid that fulfill the following conditions:
- the rectangle is non-degenerate
- the sides must be either horizontal or vertical
- the sides must lie on a grid line
A line containing two integers $$$n$$$–number of horizontal lines and $$$m$$$–number of vertical lines $$$(1\leq n, m\leq 100)$$$.
Print one integer – the number of distinct rectangles which fulfill the conditions.
3 4
18
Grid consisting of 3 horizontal and 4 vertical lines.
ETH math majors Alice and Bob are playing a game with dice. There are $$$n$$$ dice, each of the same, custom design, on the table. The game lasts $$$k$$$ turns; on a player's turn, that player picks up any subset of the dice, and rerolls them.
Alice starts, and plays on odd-numbered turns (including the first turn). Bob plays on even-numbered turns. Alice wants to maximize the sum of values the dice show at the end of the game, and Bob wants to minimize the sum. Assuming both players play optimally, what is the expected sum of values of the dice at the end of the game?
The first line contains three integers $$$1 \leq n, m, k \leq 10^5$$$: the number of dice, the number of faces on the custom type of dice, and the number of rounds the game lasts.
The second line contains $$$m$$$ integers $$$f_1, \dots, f_m$$$ ($$$1 \leq f_i \leq 10^9$$$): the values on the faces of the custom type of dice used.
The third line contains $$$n$$$ integers $$$v_1, \dots, v_n$$$ ($$$v_i \in \{f_1, \dots, f_m\}$$$): the initial values of each of the $$$n$$$ dice.
Output one real number: the expected sum of values of the dice at the end of the game, assuming both players play optimally.
Your answer is considered correct if its absolute or relative difference to the correct answer is at most $$$10^{-9}$$$. More formally, let $$$a$$$ be your answer and $$$c$$$ the correct answer. Your output is considered correct if $$$|a - c| / \max(1, c) \leq 10^{-9}$$$.
2 6 21 2 3 4 5 61 4
6.2500000000
1 3 101 1 33
1.2866432962
After a dice is rolled, its value will be an uniformly random one among the $$$m$$$ values $$$f_1, \dots, f_m$$$.
After studying the Erdős–Ginzburg–Ziv theorem, Daniel wants to present its proof to the local Opaquely Constructivist Primes Committee. The final step of the theorem constitutes the following problem:
You're given a prime number $$$p$$$, a sequence of integers $$$x_1,\dots,x_{p-1}$$$ between $$$1$$$ and $$$p-1$$$, and a number $$$g$$$. You have to find a sub-sequence of numbers such that their sum is congruent to $$$g$$$ modulo $$$p$$$.
Daniel presented the committee a proof that such a subset exists, but since all committee members are constructivists, they reject Daniel's proof until he provides a concrete construction for the given $$$x_1,\dots,x_{p-1}$$$. "Okay, for which $$$g$$$?" – asked Daniel. "All of them, of course!" – replied the committee.
Since $$$p$$$ may be quite large, Daniel decided to settle on the following construction pattern: He makes a rooted tree of $$$p$$$ vertices numbered $$$0$$$ through $$$p-1$$$, rooted at $$$0$$$. Then, Daniel will use each of the numbers $$$x_1,\dots,x_{p-1}$$$ exactly once to mark each tree edge with a number in such a way that the sum of the numbers on the path from any vertex $$$g$$$ to the root is congruent to $$$g$$$ modulo $$$p$$$.
Since Daniel is not a constructivist, he again only managed to prove that such a tree always exists, but has no idea how to actually construct it. Of course, someone still has to do so to appease the strict committee, and this someone just so happens to be you. Help Daniel!
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 5 \cdot 10^5$$$). The description of the test cases follows.
The first line of each test case contains a single prime integer $$$p$$$ ($$$2 \leq p \leq 10^6$$$).
The next line contains the $$$p-1$$$ integers $$$x_i$$$ ($$$1 \leq x_i \leq p-1)$$$.
It is guaranteed that the sum of $$$p$$$ over all test cases does not exceed $$$10^6$$$.
For each test case, print $$$p-1$$$ lines.
In the $$$i$$$-th line, print three integers $$$a$$$, $$$b$$$ and $$$x$$$, meaning that there is an edge between vertices $$$a$$$ and $$$b$$$ marked with the number $$$x$$$. Each of $$$x_i$$$ should be used exactly once in the tree description.
374 2 2 6 4 551 1 1 132 2
0 4 4 4 6 2 6 1 2 6 5 6 5 2 4 5 3 5 0 1 1 1 2 1 2 3 1 3 4 1 0 2 2 2 1 2
A sequence $$$a$$$ is a subsequence of a sequence $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly, zero or all) elements.
There is an exam being held at ETH. Chairs in the exam room are arranged in a grid of size $$$n \times m$$$, with the student sitting at the $$$(i,j)$$$ $$$(1 \leq i \leq n; 1 \leq j \leq m)$$$ position having IQ $$$a_{i,j}$$$.
Professors at ETHz have become aware that students sometimes cheat at exam. Cheating at exams always happens the same way. Some set of students $$$S = \{b_1, b_2, \dots, b_s\}$$$ decide before hand to cheat, but a set of students $$$S$$$ is only valid if two of the following conditions hold.
- Let $$$b_i$$$ and $$$b_j$$$ have the smallest and largest IQ respectively in $$$S$$$, then $$$|a_{b_i} - a_{b_j}| \leq k$$$. Since otherwise student $$$b_j$$$ won't feel that it is beneficial to cheat.
- For all pairs of students $$$(b_i, b_j)$$$ in $$$S$$$ they must be able to communicate. Two students $$$b_i$$$ and $$$b_j$$$ can communicate if there exists a sequence of students $$$c_1, c_2, \dots c_p$$$ in $$$S$$$ for $$$p \geq 2$$$, such that $$$c_1 = b_i$$$, $$$c_p = b_j$$$ and $$$c_z$$$ is adjacent to $$$c_{z+1}$$$ for $$$(1 \leq z \lt p)$$$. We say two students are adjacent if they sit next to each other in the exam (up, down, left, right).
The professors at ETHz have already published the seating arrangement, and it is to late to change it. But they wonder, what is the largest possible number of students cheating in one group.
Each test contains multiple test cases.
The first line contain an integer $$$t$$$ $$$(1 \leq t \leq 100)$$$, the number of test cases. The description of the $$$t$$$ test cases follows.
The first line of each teset case contains three integers $$$n, m, k$$$ $$$(1 \leq n,m \leq 600; 1 \leq k \leq 10^9)$$$.
Then $$$n$$$ lines follow, each line contains $$$m$$$ integers $$$a_{i,1}, a_{i,2}, \dots a_{i,m}$$$ $$$(1 \leq a_{i,j} \leq 10^9)$$$, where $$$a_{i,j}$$$ is the IQ of the student sitting in the $$$i$$$-th row and $$$j$$$-th column.
It is guaranteed that over all test cases $$$\sum n \cdot m \leq 600\cdot 600$$$
For each test case, print the largest possible number of students cheating in one group.
33 3 11 3 11 3 11 3 14 4 21 4 4 11 3 4 23 3 3 42 2 2 22 2 31 47 10
3 13 2
This summer, the Competitive Programming Committee at ETH Zurich has taken a bold step towards modernizing their programming tutorial. With attendance rocketing due to the Big Tech Interview Process and space limited, they have turned to artificial intelligence for a solution. A Large Language Model, trained on the university's notoriously theory-heavy lecture scripts, has been tasked with providing instant support to students seeking answers to their questions.
After sucessfully training the model, the committee has decided to test it with a self-created set of multiple choice questions. However, instead of delivering clear explanations in plain language, the AI has developed an alarming quirk. It now responds with cryptic mathematical expressions, seemingly inventing its own operators and rules along the way. The committee is stumped, unable to decipher the AI's cryptic responses.
Can you unravel the solutions to the questions that the comittee has asked?
You are given the output of the LLM that always has the same format (Yes we used a low temperature for sampling!). This means that some parts of the input are always the same (fixed) and some change.
We will now explain how the input is structured. The first 6 lines are fixed. The second to last word in the first sentence in line 7 is variable: "A logic with <S> values". <S> can be any number from $$$1, ..., 5$$$ but as lower-case english word, i.e. one, ..., five.
After that the next element that changes are the names of the operators. They are always given at the end of line 7 as a comma+space separated list and the last operator is always introduced by "and ". The number of operators is $$$2\leq N_{O} \leq 20$$$.
After another fixed text, the function tables are given, one for each operator and in the order that the operators were mentioned. A function table has one column for each input argument and one column for the output. The output is always given by the last column. An operator $$$o_i$$$ can have $$$1\leq x_i \leq 5$$$ arguments and different operators can have different numbers of arguments. A table has as many rows as there are possible input combinations. Columns are separated by one space.
Following the tables there is exactly one fixed line. The last word in the line after that defines the name of the assignment operator $$$A$$$.
That is followed by $$$1 \leq N_w \leq 30$$$ assignments of words $$$w$$$ to values $$$v$$$. Each assignment is one line that reads as $$$w_i$$$ $$$A$$$ $$$v_i$$$. It means that word $$$w_i$$$ has the value $$$v_i$$$.
After one single fixed line we describe the relations of $$$1 \leq N_n \leq 30$$$ more words $$$w$$$ through the operators. (New)-Words are never assigned more than once! Each relation is one line with the format: $$$n_i$$$ $$$A$$$ $$$o_j$$$ $$$w^1$$$, ..., $$$w^{x_j}$$$. That means that the operator is followed by as many words as it expects arguments. After that, the LLM text always ends with the line "Is there anything else that I can help you with?".
Directly after the LLM text, we provide a single line with $$$1 \lt Q \lt 40$$$, the number of questions we need you to answer followed by $$$Q$$$ lines with queries $$$q_i$$$ that consist of a single string.
We further illustrate the format in the examples.
All operators, words, and the assignment operator are non-empty strings consisting of lower-case english letters and '!', '?', '#', '$', '%', '&', '*', '+', '=', '@'. The domain of the functions and values are the first <S> positive integers.
Output $$$Q$$$ lines. For each input query $$$q_i$$$, output 0 if the query did not appear as a word or no value can be inferred from the given relation. We already say that no value can be inferred if the value of a word $$$w_i$$$ depends on itself, directly or indirectly. Otherwise output the value of the word from $$$q_i$$$.
As a large language model that was trained on the script of all lectures, I know all of the answers and could provide you with them. As I was trained to answer in the style of the notes, instead of just answering your question like normal people would, I will leave the answer for you to it prove as an exercise! But standard notation is boring. So I will provide you with the following. A logic with two values! Additionally, I have the following operators @, $, and #. They are not defined how you would imagine them to be to. To not cause any confusion, here are their function tables in the order that they appeared. 1 1 2 2 1 2 2 1 1 1 2 1 Now the questions you asked me can be answered by checking how the variables evaluate. Here are the values of some variables that are assigned with %. a % 1 And here are some rules b % @ a c % $ b d % # d Is there anything else that I can help you with? 4 a b c d
1 1 2 0
As a large language model that was trained on the script of all lectures, I know all of the answers and could provide you with them. As I was trained to answer in the style of the notes, instead of just answering your question like normal people would, I will leave the answer for you to prove as an exercise! But standard notation is boring. So I will provide you with the following. A logic with two values! Additionally, I have the following operators ?, and !. They are not defined how you would imagine them to be to. To not cause any confusion, here are their function tables in the order that they appeared. 1 1 2 2 1 1 1 1 2 1 2 1 1 2 2 1 Now the questions you asked me can be answered by checking how the variables evaluate. Here are the values of some variables that are assigned with asg. a asg 1 And here are some rules b asg ! a a d asg ? c c asg ? b Is there anything else that I can help you with? 5 a b c d e
1 1 1 1 0
In example one we can see that $$$a$$$ is assigned to $$$1$$$. According to the table of $$$@$$$, $$$1$$$ maps to $$$1$$$. So $$$b$$$ also has value $$$1$$$. Now according to the table of $$$?$$$ we map $$$1$$$ to $$$2$$$ which means $$$c$$$ is $$$2$$$ and finally $$$d$$$ depends directly on the value of $$$d$$$, so the correct output is $$$0$$$.
In example two line $$$a$$$ is set to $$$1$$$. After that $$$b$$$ is set to $$$1$$$ because $$$! 1 = 1$$$. We can not evaluate $$$d$$$ yet because the value of $$$c$$$ is unknown. Next, $$$? 1 = 1$$$ and so $$$c$$$ is also $$$1$$$. Now, we evaluate $$$? c = 1$$$ and so $$$d$$$ is also $$$1$$$. $$$e$$$ did not appear as a word in any assignment so the value is $$$0$$$.
After an unusually high number of reports that the Mate Machine was empty, VIS finally investigated the reasons for this. It turns out that a majority of the purchases were made by a single individual named Sascha. Fortunately, recent advancements in facial recognition technology now make it possible to prevent Sascha from making any more purchases in the future. Instead, they plan to install a separate machine exclusively for him.
Currently, there are $$$n$$$ Mate drinks in the machine, each belonging to some type $$$a$$$. In total, there are $$$m$$$ different types of Mate. Additionally, each Mate drink will expire in $$$b$$$ hours and cannot be sold after that. As a serious Mate addict, Sascha buys and consumes one Mate every hour.
Sascha enjoys every type of Mate equally. However, with this machine, it is not possible to select a specific type of Mate to buy; instead, a carefully designed algorithm decides which of the Mate in the machine to dispense. Assuming the machine dispenses the Mate optimally, what is the biggest integer $$$k$$$ such that Sascha can consume $$$k$$$ Mate of every type?
Each test contains multiple test cases. The first line contains the number of test cases t ($$$1 \le t \le 10^4$$$).
The description of the test cases follows.
The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 3 \cdot 10^5$$$, $$$1 \le m \le 3 \cdot 10^5$$$) – the number of Mate and the types of Mate there are.
The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,...,a_n$$$ ($$$1 \le a_i \le m$$$) — the type of each Mate.
The third line of each test contains $$$n$$$ integers $$$b_1,b_2,...,b_n$$$ ($$$0 \le b_i \le 10^9$$$) — the hours until a Mate expires. Note that if $$$b_i = j$$$, then Mate $$$i$$$ can be up to the $$$j+1$$$'th Mate sold to Sascha. Specifically, if $$$b_i = 0$$$ then this can (only) be the first Mate sold to Sascha.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.
For each test case, output a single line containing an integer: the maximum integer $$$k$$$ such that Sascha can buy $$$k$$$ Mate of each type.
35 44 2 1 3 23 3 1 7 24 21 2 1 20 1 2 36 54 3 3 3 5 14 2 2 1 5 14
1 2 0
In the first test case the machine can first dispense Mate $$$5$$$ (type $$$2$$$), after one hour dispense Mate $$$3$$$ (type $$$1$$$), one hour later Mate $$$4$$$ (type $$$3$$$), and finally Mate $$$1$$$ (type $$$4$$$). As there are exactly $$$4$$$ types of Mate, every type was dispensed once and the answer is $$$1$$$.
In the second test case the machine can dispense in the order $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$. This is the only optimal dispense order and the answer is $$$2$$$.
In the third test case there is no Mate of type $$$2$$$, hence, the answer is $$$0$$$.
As we all know, intelligence is strictly determined by your DNA sequence. One student, Konstantin, at ETHz just realized this recently. He then started reading about what exactly was the reason for intelligence in DNA sequences. He came to the conclusion that there are $$$k$$$ important strings $$$a_1, a_2, \dots, a_k$$$ with strength scores $$$b_1, b_2, \dots, b_k$$$ that make up your IQ-score.
Let $$$L(s)$$$ be the number of times the string $$$s$$$ appears in your DNA sequence as a substring$$$^{*}$$$. Then you can formally define your IQ score as follows.
$$$$$$\sum_{1 \leq i \leq k} L(a_i) \cdot b_i$$$$$$
Excited with this new knowledge, he went straight to a medical center that specializes in DNA modifications. After the doctors did testing on him, they told him the results. Konstantins DNA sequence can be represented as a string of $$$n$$$ characters consisting of letters $$$\{A, C, G, T\}$$$. The doctors told him that there are $$$m$$$ possible indices $$$c_1, c_2, \dots, c_m$$$ in the DNA sequence that can be altered into any other character. Konstantin told the doctors to change his DNA sequence so that his IQ score would be maximum, but they can't possibly solve such a hard problem of maximizing his IQ score. They would need to know how Konstantin wants to change the sequence.
Can you tell Konstantin what the maximum possible IQ score he can have if he changes his DNA sequence optimally?
$$$*$$$ Let $$$a = a_1 a_2 a_3 \dots a_{|a|}$$$ be a string where the $$$i$$$-th character of $$$a$$$ is $$$a_i$$$. We call a string $$$a_l a_{l+1} \dots a_{r}$$$ $$$(1 \leq l \leq r \leq |a|)$$$ a substring of $$$a$$$.
Each test contains multiple test cases.
The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 1000)$$$, the number of test cases. The description of the $$$t$$$ test cases follows.
The first line of each test case contains three integers $$$n,m,k$$$ $$$(1 \leq m \leq n \leq 1000; 1 \leq k \leq 100)$$$.
The second line of each test case contains a string s of length $$$n$$$, the DNA sequence of Konstantin.
The next line contains $$$m$$$ integers $$$c_1, c_2, \dots, c_m$$$ $$$(1 \leq c_i \leq n)$$$, the indices of the DNA sequence that can be changed. It is guaranteed that $$$c_i \neq c_j$$$ for $$$i \neq j$$$.
The next $$$k$$$ lines contain a string $$$a_i$$$ $$$(1 \leq |a_i| \leq n)$$$ consisting only of letters from $$$\{A, C, G, T\}$$$ and the strength level $$$b_i$$$ $$$(1 \leq b_i \leq 10^5)$$$ of the $$$i$$$-th string. It is guaranteed that all strings $$$a_i$$$ are unique per test case.
It is guaranteed that over all test cases $$$\sum n \leq 1000$$$, and $$$\sum |a_i| \leq 1000$$$.
For each test case, print a single integer: the highest possible IQ score Konstantin can achieve if his DNA sequence is modified optimally.
13 3 2AAA1 2 3CC 5AA 3
10
You are currently taking the course AlgoHell and have procrastinated a bit too much. Today is already the deadline for the current problem. Luckily, you have an algorithm which is correct, but it has a terrible runtime complexity. Therefore, you break into ETH's top secret super computer in the dome at the top of HG. Unfortunately, the complexity of your algorithm is so bad that even on the super computer, it runs too slowly. It will not be able to give you the result in time for your deadline.
To speed up the computation, you need to cool down the super computer. It has $$$n$$$ different server racks, where $$$n$$$ is even since the server architects can only buy racks in bundles of 2. Each rack has a unique heat level $$$a_i$$$ since your parallelization does not split up the workload evenly. The racks are all aligned in a row; rack $$$i$$$ is next to rack $$$i+1$$$. You want adjacent racks with a low heat level to cool their warmer neighbors. This works best if the difference between the heat levels is big. Therefore, you want to maximize the sum of absolute differences of heat levels in adjacent server racks:
$$$$$$\max\sum_{i=2}^n |a_{i-1} - a_i|$$$$$$
Since you have been here before, you know that all adjacent racks are connected with a wire. You can use this wire to transfer the workloads and swap the heat levels of one server rack with an adjacent one. However, you also want to minimize the number of swaps, since each swap takes about 1 minute and you have to submit the answer before the deadline.
Now you want to answer 2 questions to determine whether the computation will finish in time:
- How much cooling can you achieve — what is the maximum sum of absolute differences in heat levels?
- How much time does it take to reach this cooling efficiency — what is the minimum number of adjacent swaps to reach this sum?
The first line of input contains an integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^5$$$) — the number of test cases. Then $$$t$$$ lines follow, each describing one test case.
The first line of each test case contains an integer $$$n$$$ ($$$2 \leq n \leq 4 \cdot 10^5$$$) — the number of server racks in the super computer. Since the server architects are not weird, $$$n$$$ is guaranteed to be even.
The second line of each test case contains n distinct integers $$$a_1,...,a_n$$$ ($$$1 \leq a_i \leq n$$$), where $$$a_i$$$ is the heat level of the $$$i$$$–th rack.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$4 \cdot 10^5$$$.
For each test case, output two integers: the maximum sum of absolute differences in heat levels and the minimum number of adjacent swaps required to achieve this maximum.
321 266 5 1 4 3 284 2 3 1 7 6 8 5
1 0 17 6 31 6
In the first test case, no workloads need to be swapped to reach the maximum difference of $$$1 = |1 - 2|$$$.
In the second test case, you can swap heat level $$$3$$$ to the very left. After 4 swaps, you have the heating configuration $$$3, 6, 5, 1, 4, 2$$$. Then you can swap $$$4$$$ with $$$2$$$ and $$$5$$$ with $$$1$$$, leaving $$$3, 6, 1, 5, 2, 4$$$. This permutation has a maximum sum of differences of $$$3 + 5 + 4 + 3 + 2 = 17$$$ after only 6 swaps. It can be proven that this is the maximum sum and the minimum number of adjacent swaps.
The world's problems have worsened, with hunger prevailing, even in Polymensa. With only one scoop of Rösti per day, Polymensa queue becomes battleground for survival. Oli, lost in his research, skipped the Probability Lecture as usual and needs your help to determine his expected loss for the day.
There are $$$n$$$ students, including Oli, who form a queue for the single scoop of Rösti at Polymensa. The fate of the student at the front(first place of the queue) is determined by a magical ladle. There's a probability $$$\frac{a}{b}$$$ that the ladle scoops out Rösti. If not, the student pays a coin as a penalty and moves to the end(n-th place) of the queue while everyone else shifts one place forward. The process continues, with the student at the front having a probability of $$$\frac{a}{b}$$$ to receive Rösti. If unsuccessful, the student moves to the end of the queue, and so on.
When someone gets the single scoop of Rösti this whole process stops.
Calculate the expected amount of coins spent by Oli, who initially occupies the $$$k$$$-th place in the queue, modulo $$$10^9+7$$$.
Input contains two lines.
In the first line, you are given $$$n$$$, representing the number of students and $$$k$$$, representing the place of Oli in the queue $$$(1 \leq k \leq n \leq 10^{9})$$$
In the second line you are given $$$a$$$ and $$$b$$$, such that the probability of the magical ladle scooping out the Rösti is $$$\frac{a}{b}$$$ $$$(1 \leq a \leq b \leq 10^{9})$$$
Print one integer the expected amount of coins spent by Oli, taken modulo $$$10^9+7$$$.
The required expected value can be represented as an irreducible fraction $$$\frac{p}{q}$$$. You have to print the value $$$p \cdot q^{-1} \mod 1000000007$$$. Note that any valid input in this problem is co-prime to $$$10^9+7$$$.
3 11 2
571428576
5 21 3
725118489
1000000000 10000000001000000000 1000000000
0
In the first test, the answer is $$$\frac{4}{7}$$$. There are $$$3$$$ students waiting, and Oli is first in the queue. The person at the front has probability of $$$\frac{1}{2}$$$ getting Rösti.
Note that $$$4 \cdot 7 ^{-1} = 571428576 \mod (10^9 + 7)$$$.
In the second test, the answer is $$$108/211$$$. There are $$$5$$$ students waiting, and Oli is second in the queue. The person at the front has probability of $$$\frac{1}{3}$$$ getting Rösti.
In the third test, the person at the front of the queue will get the dish on the first attempt. So, poor Oli doesn't even get a chance to experience the magical ladle and spends $$$0$$$ coins.
At station A, there are $$$n$$$ railcars, numbered with distinct values from $$$1$$$ to $$$n$$$, in an arbitrary order. However, the order in which they are in track A is important, as they will leave point A exactly in the order in which they are listed. For example, if $$$n$$$ = 3 and we have the order [2, 3, 1], railcar number 3 can only leave after railcar 1 has departed from point A. Similarly, railcar 2 can only leave after railcars 1 and 3 have departed from the station A.
The $$$n$$$ railcars need to be moved to station C, such that the first railcar to arrive at this location is 1, followed by 2, 3, and so forth up to the last railcar.
To accomplish this, individual railcars can be moved from one station to another in the order indicated by the arrows:
| Operation 1 | Operation 2 | Operation 3 |
| A to B | B to C | A to C |
Nevertheless, since there is only one track at point B (just like at points A and C), any railcar arriving at B after a railcar $$$p$$$ already arrived (and it's still at point B), it must leave point B before $$$p$$$ to make it possible to move railcar $$$p$$$.
Determine the $$$\bf{shortest}$$$ sequence of operations to move all railcars from station A to station C in the desired order.
The program reads the number $$$n$$$ $$$(1 \leq n \leq 10^5)$$$, and then n distinct natural numbers between $$$1$$$ and $$$n$$$, representing the order of the railcars on track A.
The program will display on the screen the number $$$Q$$$ of operations performed, followed by the $$$Q$$$ operations.
Each operation will be displayed on a separate line of the screen and will consist of two characters in the form $$$T$$$ $$$Z$$$, signifying that a railcar is being moved from station $$$T$$$ to station $$$Z$$$. If it is not possible to move the railcars from station $$$A$$$ to station $$$C$$$, the number of operations displayed will be $$$-1$$$.
88 5 6 4 2 3 1 7
11 A B A C A B A C B C A C A B A C B C B C A C
51 2 3 5 4
-1