Juca dreams of retiring and spending the rest of his life peacefully. He calculated that he needs to have at least $$$R$$$ thousand reais. Juca has a variable income job, and at the end of each year, he receives a payment that varies from $$$1$$$ to $$$R$$$ thousand reais, with uniform probability.
If, after receiving his salary, his total income is $$$R$$$ thousand reais or more, he retires happily. Otherwise, he decides to adjust his income according to inflation:
- Let $$$S$$$ be the balance of his account.
- Let $$$a, b$$$ be two integers that satisfy $$$0 \leq a \lt b$$$, representing the level of inflation.
- The new balance will be (floor(S * (1 - a / b))), where floor is the floor function, which returns the integer part of a positive real number. For example, if $$$S = 3, a=1,b=2$$$, the new balance would be floor($$$1.5$$$) = $$$1$$$.
Juca is curious to know the expected value of the number of years it will take for him to retire. It can be shown that the answer is a fraction $$$\frac{p}{q}$$$ with $$$gcd(p,q) = 1$$$. Print $$$p \cdot q^{-1} \mod (10^9 + 7)$$$.
The input consists of three integers $$$R$$$, $$$a$$$, and $$$b$$$ in that order. It is guaranteed that $$$1 \leq R \leq 500$$$ and $$$0 \leq a \lt b \leq 1000 $$$.
It can be shown that the answer is a fraction $$$\frac{p}{q}$$$ with $$$gcd(p,q) = 1$$$. Print $$$p \cdot q^{-1} \mod (10^9 + 7)$$$.
1 0 1
1
2 1 2
2
500 1 2
699460048
500 0 1
830988645
"Reais" is Brazil's currency (BRL).
Syl learned today about Modular Arithmetic. She wants to test her knowledge with various questions on addition, subtraction, multiplication, and exponentiation. To have an answer key, she asked you to create a program that solves these operations. As a good computer scientist, the chosen modulus is $$$10^9 + 7$$$.
Be careful, as the input numbers can be large.
The input comes in the format "x ? y", where $$$1 \leq x,y \leq 10^{100000}$$$ and ? is the symbol of the operation performed, which can be +, -, *, or ^, for addition, subtraction, multiplication, and exponentiation, respectively.
Print only one integer $$$0 \leq x \lt 10^9 + 7$$$, the result of the operation of $$$x$$$ and $$$y$$$ modulo $$$10^9 + 7$$$.
1 + 1
2
1000000006 ^ 1000000006
1
1000000006 ^ 1000000007
1000000006
1000000007 ^ 1
0
10 - 11
1000000006
123456789123456789 * 987654321987654321987654321
150430847
912784 ^ 145
788766592
The only difference between this problem and the hard version is the value of $$$n$$$.
Given a permutation $$$P$$$ of $$$n$$$ elements, let $$$G$$$ be a directed graph with $$$n$$$ vertices, where there is a directed edge from $$$i$$$ to $$$P_i$$$ for every $$$1 \leq i \leq n$$$.
Determine the number of permutations $$$P$$$ such that the graph $$$G$$$ induced by the permutation contains at least one cycle of size greater than or equal to $$$T$$$, where $$$T$$$ is a given integer ($$$1 \leq T \leq n$$$).
Since this number can be large, print the answer modulo $$$10^9 + 7$$$.
The input consists of two integers $$$n$$$ and $$$T$$$ in that order.
It is guaranteed that $$$1 \leq T \leq n \leq 10^3$$$.
Print the number of permutations with at least one cycle of size $$$T$$$ or more. Since this number can be large, print the answer modulo $$$10^9 + 7$$$.
5 2
119
5 4
54
10 4
3457224
The only difference between this problem and the easy version is the value of $$$n$$$.
Given a permutation $$$P$$$ of $$$n$$$ elements, let $$$G$$$ be a directed graph with $$$n$$$ vertices, where there is a directed edge from $$$i$$$ to $$$P_i$$$ for every $$$1 \leq i \leq n$$$.
Determine the number of permutations $$$P$$$ such that the graph $$$G$$$ induced by the permutation contains at least one cycle of size greater than or equal to $$$T$$$, where $$$T$$$ is a given integer ($$$1 \leq T \leq n$$$).
Since this number can be large, print the answer modulo $$$10^9 + 7$$$.
The input consists of two integers $$$n$$$ and $$$T$$$ in that order.
It is guaranteed that $$$1 \leq T \leq n \leq 10^6$$$.
Print the number of permutations with at least one cycle of size $$$T$$$ or more. Since this number can be large, print the answer modulo $$$10^9 + 7$$$.
5 2
119
5 4
54
10 4
3457224
Willy Wonka, famous for his large chocolate factory, decided to give a gift to the $$$n$$$ lucky people who won a visit to his factory. He has $$$k$$$ chocolates available, all different from each other. Willy wants to distribute the chocolates among the $$$n$$$ participants, ensuring that everyone receives at least one chocolate.
After a while, he realized that this task was too easy and decided to compute how many ways this can be done. Let the $$$k$$$ distinct chocolates be numbered from $$$1$$$ to $$$k$$$, and the participants from $$$1$$$ to $$$n$$$. Two distributions are different if there exists a participant $$$i$$$ who receives a chocolate $$$j$$$ in one distribution but not in another for some $$$1 \leq i \leq n$$$ and $$$1 \leq j \leq k$$$. Since the number of ways can be very large, compute the answer modulo $$$10^9 + 7$$$.
The input consists of two integers $$$k$$$ and $$$n$$$, respectively. It is guaranteed that $$$1 \leq n \leq k \leq 10^5$$$.
Print an integer $$$0 \leq q \lt 10^9 + 7$$$, the number of ways to distribute the sweets with the given restrictions, modulo $$$10^9 + 7$$$.
1 1
1
2 1
1
2 2
2
3 1
1
3 2
6
Please read the statement of the easier version first. It has been copied to the notes.
Willy realizes that he has made a big mess, and the number $$$n$$$ of participants who will make the visit is unknown. The only thing he knows is that $$$1 \leq n \leq k$$$. Help Willy Wonka by computing the number of ways to distribute the $$$k$$$ sweets for every possible value of $$$n$$$. Print the answer modulo $$$10^9 + 7$$$.
The input consists of a single integer $$$k$$$, representing the number of chocolates. It is guaranteed that $$$1 \leq k \leq 10^5$$$.
Print $$$k$$$ integers separated by spaces. The integer $$$1 \leq i \leq k$$$ represents how many ways to distribute $$$k$$$ sweets to $$$i$$$ participants such that everyone receives at least one sweet, modulo $$$10^9 + 7$$$.
1
1
2
1 2
5
1 30 150 240 120
Statement of the easier version:
Willy Wonka, famous for his large chocolate factory, decided to give a gift to the $$$n$$$ lucky people awarded a visit to his factory. He has $$$k$$$ chocolates available, all different from each other. Willy wants to distribute the chocolates among the $$$n$$$ participants, ensuring that everyone receives at least one chocolate.
After a while, he realized that this task was too easy and decided to compute how many ways this can be done. Let the $$$k$$$ distinct chocolates be numbered from $$$1$$$ to $$$k$$$, and the participants from $$$1$$$ to $$$n$$$. Two ways are different if there exists some participant $$$i$$$ who receives a chocolate $$$j$$$ in one of the distributions but not in another for some $$$1 \leq i \leq n$$$ and $$$1 \leq j \leq k$$$. Since the number of ways can be very large, compute the answer modulo $$$10^9 + 7$$$.
Kaladin and his friends are very tired after a long and hard day of work. Now they sit down to have soup at a round table. However, since everyone is very tired, no one wants to talk. Even simple questions like "What is your name?" would be stressful.
As no one wants to risk a conversation, no one sits next to anyone. Kaladin's friend, Syl, became interested in counting how many ways people can sit at the round table so that no one is next to anyone.
The seats at the table are numbered from $$$1$$$ to $$$n$$$, and the people from $$$1$$$ to $$$k$$$. A way of seating the people at the round table can be represented by a list of size $$$k$$$, $$$l$$$, where $$$l_i$$$ represents the chair that the $$$i$$$-th person sat in. That is, for this counting, it matters which person is sitting in which chair.
Return the answer modulo $$$10^9 + 7$$$.
The input consists of two integers: $$$n$$$ and $$$k$$$, indicating the number of seats at the table and the number of people who will eat, respectively.
It is guaranteed that $$$1 \leq k \leq n \leq 10^5$$$.
Print a single integer $$$0 \leq x \lt 10^9 + 7$$$, the number of ways that people can sit at the round table so that no one is next to anyone, modulo $$$10^9 + 7$$$.
1 1
1
2 1
2
2 2
0
5 2
10
As the table is round, the position $$$i$$$ is next to position $$$i+1$$$, for $$$1\leq i \lt n$$$, and also position $$$1$$$ is next to position $$$n$$$.
Sheldon Cooper and his family will participate in a Secret Santa game, which will take place at the town church. Pastor Jeff wrote down the name of each of the $$$n$$$ people who will participate and then randomly distributed a piece of paper to each person. After that, each person must buy a gift for the person whose name is on the paper they received.
Sheldon calculated and told the pastor that there is a high chance that someone will draw their own name. In that case, they would have to buy a gift for themselves, and the game would be boring!
Jeff does not trust Sheldon and asked you to create a program that calculates the probability that at least one person draws their own name. It is guaranteed that the answer can be expressed as a fraction $$$\frac{a}{b}$$$. You should print $$$a \cdot b^{-1}\ mod \ M$$$, where $$$M = 10^9 + 7$$$. It can be shown that under these constraints $$$b \neq 0\ mod \ M$$$.
The input contains a single integer $$$1 \leq n \leq 10^5$$$.
Print the probability that at least one person draws their own name, in the format $$$a \cdot b^{-1}\ mod\ M$$$.
1
1
5
433333337
This is an interactive problem. If you are not familiar with this type of problem, it is recommended to read the following guide: https://codeforces.me/blog/entry/45307
Kaladin is participating in a game by the famous YouTuber Mr. Besta. The game works as follows:
- There are 3 doors numbered from 1 to 3.
- Behind one of the doors, there is a new car, and behind the other two, there is a dirty sock. The door with the car is chosen randomly.
The host of the game challenges Kaladin to guess which door hides the car. The game follows these steps:
- Kaladin initially chooses one of the 3 doors.
- The host opens one of the remaining doors, revealing a dirty sock.
- Kaladin has the option to stick with his initial choice or switch to the other closed door.
- Finally, the door chosen by Kaladin is opened, and he finds out if he won the car.
Kaladin will participate in the game $$$N=10000$$$ times in a row. He will only win the car if he guesses correctly at least $$$6500$$$ out of the $$$N$$$ games. Your task is to implement a strategy to help Kaladin win the car.
This is an interactive question. Remember to always "flush" the output with "std::endl" or cout.flush()
The input is interactive and follows this format:
- In the first line, you will receive an integer $$$N = 10^4$$$, indicating the number of times Kaladin will play.
- For each game:
- You must print an integer between 1 and 3, representing the initially chosen door.
- You will receive an integer between 1 and 3, indicating the door opened by the host with a dirty sock.
- You must print another integer between 1 and 3, representing the door chosen by Kaladin as his final decision.
- You will receive an integer $$$0$$$ or $$$1$$$, where $$$1$$$ means Kaladin won the car, and $$$0$$$ means he chose a dirty sock.
Note that there is only 1 test case, so there is no test input!
You should not produce direct standard output, except for the interaction with the system described in the input section. Your strategy will be evaluated at the end. Kaladin will win the car if he guesses correctly at least $$$6500$$$ times in $$$N = 10000$$$ games.
For example, suppose there is only $$$1$$$ test case and the game occurred as follows:
- Kaladin chooses door $$$1$$$
- It is revealed that door $$$2$$$ has a sock
- Kaladin chooses door $$$1$$$ as his final decision
- It is revealed that he guessed correctly (1 is written in the Input)
Input/Judge
1
2
1
Kaladin:
1
1
- The host will always open a door with a dirty sock, among those that Kaladin did not choose (that is, a door that was not chosen by Kaladin and that does not contain the car).
- Use an efficient strategy to maximize Kaladin's chances of winning the car.
It is guaranteed that there is only $$$1$$$ test case, and that the input is random.
Little John loves challenges and decided to test his luck at the Big Tiger roulette. Initially, he plays on a roulette with $$$l[1]$$$ markings, all equally probable, but only one marking results in a win. After every $$$q[i]$$$ consecutive losses, the system reduces the size of the roulette, moving to a new one with $$$l[i+1]$$$ markings, where $$$l[i+1] \lt l[i]$$$. This process continues until reaching the last roulette, which has $$$l[n]$$$ markings.
Little John is very persistent and will keep playing until he gets his first win. After that, he decides to stop and go home.
You, concerned about Little John's obsession, decided to calculate the expected value $$$E$$$ of the number of times the roulette will be spun until the first win.
The result should be represented as an irreducible fraction $$$\frac{p}{q}$$$, where $$$\gcd(p, q) = 1$$$. To avoid issues with floating-point numbers, print the answer as $$$p \cdot q^{-1} \mod (10^9 + 7)$$$, where $$$q^{-1}$$$ is the modular inverse of $$$q$$$ modulo $$$10^9 + 7$$$. It can be shown that $$$q \neq 0 \mod (10^9 + 7)$$$ within the problem's constraints.
The input consists of an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$), representing the number of roulettes, followed by $$$n$$$ pairs $$$l[i] \, q[i]$$$, where $$$l[i]$$$ represents the number of markings on the $$$i$$$-th roulette and $$$q[i]$$$ ($$$1 \leq q[i] \leq 10^9$$$) represents the number of consecutive losses required to switch to the next roulette. For the last roulette, $$$q_n = -1$$$.
It is guaranteed that $$$1 \leq l[n] \lt l[n-1] \lt \dots \lt l[1] \lt 10^9 + 7$$$.
Print a single integer, the expected value $$$E$$$ of the number of spins until the first win, represented as $$$p \cdot q^{-1} \mod (10^9 + 7)$$$.
1 2 -1
2
2 3 1 2 -1
333333338
Aline noticed that there are several ways to write a number $$$n$$$ as the sum of other positive integers. For example, the number $$$3$$$ can be written in $$$4$$$ ways:
$$$3 = 1 + 1 + 1 = 1 + 2 = 2 + 1 = 3$$$
Help Aline compute how many ways a number $$$n$$$ can be written. Compute the answer modulo $$$10^9 + 7$$$.
The input consists of a single integer $$$1 \leq n \leq 10^6$$$.
Print the number of ways to write $$$n$$$ as the sum of other positive integers, modulo $$$10^9 + 7$$$.
1
1
3
4