Naniwazu-kun is going to take on the traditional kendama challenge in a New Year's Eve music program. If at least $$$K$$$ people succeed consecutively, the record will be broken. To maximize the probability of success as much as possible, he decided to challenge it with a team of $$$N$$$ carefully selected players.
The $$$N$$$ players will attempt the kendama in order from the $$$1$$$-st to the $$$N$$$-th. The probability that the $$$i$$$-th player $$$(1 \leq i \leq N)$$$ succeeds is $$$\frac{A_i}{B_i}$$$, and each player's success or failure is independent.
Find the probability that there exists at least one segment where $$$K$$$ or more consecutive players succeed, modulo $$$998244353$$$.
In the first line, integers $$$N, K$$$ are given separated by a space. ($$$1 \leq K \leq N \leq 2 \times 10^5$$$)
In the following $$$N$$$ lines, the $$$i$$$-th line contains integers $$$A_i, B_i$$$ separated by a space. ($$$1 \leq A_i \leq B_i \leq 998244352$$$)
Output the probability modulo $$$998244353$$$ in a single line.
2 21 11 2
499122177
5 41 11 11 11 11 10000
1
5 33 141 592 653 589 79
62790646
For the first example:
Let S denote the event that player $$$i$$$ succeeds, and F denote the event that player $$$i$$$ fails.
The possible patterns and their probabilities are as follows:
- SS : $$$1 \times \frac{1}{2} = \frac{1}{2}$$$
- SF : $$$1 \times \frac{1}{2} = \frac{1}{2}$$$
Only SS contains a segment where at least $$$2$$$ players succeed consecutively, and its probability is $$$\frac{1}{2}$$$.
Since $$$499122177 \times 2 \equiv 1 \pmod{998244353}$$$, output $$$499122177$$$.
For the second example:
Even if Naniwazu-kun, who performs last, is not very skilled, it is fine as long as the helpers are reliable.
It can be proven that the required probability is always a rational number. Under the constraints of this problem, when the probability is expressed as a reduced fraction $$$\frac{y}{x}$$$, it is guaranteed that $$$x$$$ is not divisible by $$$998244353$$$.
In this case, there exists a unique integer $$$z$$$ with $$$0 \leq z \leq 998244352$$$ such that $$$xz \equiv y \pmod{998244353}$$$. Output this $$$z$$$.
You are given $$$N$$$ strings $$$S_1, \dots, S_N$$$, each consisting of lowercase English letters and having length $$$M$$$.
Initially, let $$$X = S_1$$$, and perform the following operation $$$N-1$$$ times.
In the $$$i$$$-th operation, let $$$Y$$$ be the string formed by concatenating $$$X$$$ and $$$S_{i+1}$$$ in this order. Then, choose any contiguous substring of $$$Y$$$ of length $$$M$$$, and replace $$$X$$$ with that substring.
Output the lexicographically smallest string that can possibly be the final value of $$$X$$$.
The first line contains integers $$$N, M$$$ in this order. ($$$2 \leq N \leq 2000, 1 \leq M \leq 2000$$$)
Each of the following $$$N$$$ lines contains a string $$$S_i$$$ of length $$$M$$$, consisting of lowercase English letters.
Print the answer.
2 3catcut
atc
2 1ab
a
3 8jastawaytatesotosoryuusi
asoryuus
In the first example, initially $$$X=$$$ cat.
In the first operation, $$$Y=$$$ catcut. If we choose the contiguous substring from the $$$2$$$-nd to the $$$4$$$-th character, then $$$X=$$$ atc, which is the lexicographically smallest possible.
You are given a sequence of positive integers $$$(A_1,\ldots,A_N)$$$ of length $$$N$$$. Consider partitioning this sequence $$$A$$$ into $$$M$$$ contiguous non-empty subsequences $$$B_1,B_2,\ldots,B_M$$$.
For a subsequence $$$B=(A_L,\ldots,A_R)$$$, define its score by $$$$$$S(B) = \dfrac{A_L \mathbin{\mathrm{and}} A_{L+1} \mathbin{\mathrm{and}} \cdots \mathbin{\mathrm{and}} A_R}{A_L \mathbin{\mathrm{or}} A_{L+1} \mathbin{\mathrm{or}} \cdots \mathbin{\mathrm{or}} A_R}$$$$$$ where $$$x \mathbin{\mathrm{and}} y$$$ and $$$x \mathbin{\mathrm{or}} y$$$ denote the bitwise AND and bitwise OR of $$$x$$$ and $$$y$$$, respectively.
Once a partition is fixed, we obtain $$$M$$$ values $$$S(B_1),\ldots,S(B_M)$$$ as the scores of the subsequences. Sort these values in descending order, and define the score of the partition as the $$$K$$$-th value in that order. Considering all possible partitions, find the maximum and minimum possible values of the partition score.
The first line contains integers $$$N, M, K$$$ in this order. ($$$1 \leq K \leq M \leq N \leq 10^5$$$)
The second line contains $$$N$$$ integers $$$A_1,\ldots,A_N$$$ in this order. ($$$ 1 \leq A_i \lt 2^{30} \ (1 \leq i \leq N)$$$)
Print $$$2$$$ lines.
Let the maximum and minimum values be $$$\frac{p}{q}$$$, $$$\frac{r}{s}$$$, respectively, where $$$p,r \geq 0$$$, $$$\ q,s \geq 1$$$, $$$\gcd(p,q) = \gcd(r,s) = 1$$$. Print $$$p,q$$$ on the first line, and $$$r,s$$$ on the second line, separated by spaces, in this order.
5 3 36 5 7 3 2
2 3 1 7
5 1 13 1 4 1 5
0 1 0 1
9 5 3998 244 353 469 762 49 754 974 721
1 1 208 1023
For the first example, if we choose $$$B_1 = (6)$$$, $$$B_2 = (5, 7)$$$, $$$B_3 = (3, 2)$$$, then $$$S(B_1) = 1$$$, $$$S(B_2) = \frac{5}{7}$$$, $$$S(B_3) = \frac{2}{3}$$$. When these are sorted in descending order, the $$$3$$$-rd value is $$$\frac{2}{3}$$$.
Also, if we choose $$$B_1 = (6), \ B_2 = (5,7,3), \ B_3 = (2)$$$, then $$$S(B_1) = 1, \ S(B_2) = \frac{1}{7}, S(B_3) = 1$$$. When these are sorted in descending order, the $$$3$$$-rd value is $$$\frac{1}{7}$$$.
The bitwise AND $$$x \mathbin{\mathrm{and}} y$$$ and bitwise OR $$$x \mathbin{\mathrm{or}} y$$$ of non-negative integers $$$x,y$$$ are defined as follows.
- In the binary representation of $$$x \mathbin{\mathrm{and}} y$$$, the digit at the $$$2^k \ (k \geq 0)$$$ place is $$$1$$$ if and only if the digits at the $$$2^k$$$ place in the binary representations of both $$$x$$$ and $$$y$$$ are $$$1$$$; otherwise, it is $$$0$$$.
- In the binary representation of $$$x \mathbin{\mathrm{or}} y$$$, the digit at the $$$2^k \ (k \geq 0)$$$ place is $$$1$$$ if and only if at least one of the digits at the $$$2^k$$$ place in the binary representations of $$$x$$$ and $$$y$$$ is $$$1$$$; otherwise, it is $$$0$$$.
You are given a simple $$$N$$$-gon on the $$$xy$$$-plane all of whose edges are parallel to either the $$$x$$$-axis or the $$$y$$$-axis (that is, a polygon with no self-intersections and no holes).
There are $$$M$$$ speech locations on the boundary of this polygon.
When movement is allowed only along the boundary of this polygon, find the minimum total travel distance required to visit all speech locations exactly once.
The starting point and ending point of the movement may be chosen arbitrarily on the boundary of the polygon.
The first line contains the number of vertices $$$N$$$ of the polygon and the number of speech locations $$$M$$$. ($$$4 \leq N \leq 10^5, 1 \leq M \leq 10^5$$$)
The $$$(i+1)$$$-th line contains the coordinates $$$(x_i, y_i)$$$ of the $$$i$$$-th vertex of the simple $$$N$$$-gon. ($$$1 \leq i \leq N, |x_i| , |y_i| \leq 10^5$$$) The edges of the polygon connect the $$$i$$$-th vertex and the $$$(i+1)$$$-th vertex. In other words, exactly one of $$$x_{i}=x_{i+1}$$$ or $$$y_{i}=y_{i+1}$$$ holds. (The $$$(N+1)$$$-th vertex denotes the $$$1$$$-st vertex.) No vertex lies on an edge. (That is, there is no vertex with an angle of $$$180$$$ degrees.)
The $$$(j + 1 + N)$$$-th line contains the coordinates $$$(p_j, q_j)$$$ of the $$$j$$$-th speech location. ($$$1 \leq j \leq M, |p_j|, |q_j| \leq 10^5$$$) These points are all distinct and lie on the boundary of the given polygon. (This includes vertices.)
All input values are integers.
Print the answer.
4 30 03 03 20 20 03 03 2
5
6 40 03 03 12 12 20 23 00 22 11 2
5
10 10-12 -11-12 93 93 1-3 1-3 -18 -18 -10-5 -10-5 -113 13 77 -1-3 0-4 -10-12 8-10 -11-3 9-12 -108 -7
74
In the first example, there are points on three vertices of a rectangle, and visiting them in the order $$$(0, 0) \rightarrow (3, 0) \rightarrow (3, 2)$$$ gives the shortest total travel distance, which is $$$3+2=5$$$.
Figure for Sample Input $$$1$$$
Figure for Sample Input $$$2$$$
Figure for Sample Input $$$3$$$
There is one box labeled with each integer from $$$1$$$ to $$$N$$$. Also, for each integer from $$$1$$$ to $$$N$$$, there are $$$M$$$ balls labeled with that integer.
These $$$NM$$$ balls are shuffled and then distributed into the $$$N$$$ boxes, with exactly $$$M$$$ balls placed into each box.
There are $$$\frac{(NM)!}{(M!)^N}$$$ possible ways to place the balls (if all balls are considered distinguishable), and all of these arrangements occur with equal probability.
You will perform operations on these boxes and balls. One operation consists of the following steps.
- Choose one box and go in front of that box.
- If there is no ball in that box, terminate the operation.
- Choose any one ball from that box and discard it outside the box.
- Finally, go in front of the box whose label matches the label of the ball most recently discarded, and return to step 2.
Define your score as the number of operations required until all $$$NM$$$ balls have been discarded. You want to minimize this score.
Find the expected value of the score when you act optimally, modulo $$$998244353$$$.
The first line contains $$$N$$$ and $$$M$$$ in this order, separated by spaces. ($$$1\leq N\leq 10^5$$$, $$$1\leq M\leq 100$$$)
Print the answer.
2 2
166374060
3 1
831870296
100000 100
402978825
For the first example, the possible ball arrangements and the corresponding optimal ways of operating are as follows.
- Put two balls labeled $$$1$$$ into box $$$1$$$, and two balls labeled $$$2$$$ into box $$$2$$$. ( Probability $$$1/6$$$ )
- In the first operation, go in front of box $$$1$$$. From there, take out a ball labeled $$$1$$$ and go in front of box $$$1$$$. Then take out another ball labeled $$$1$$$ and go in front of box $$$1$$$ again. At this point, box $$$1$$$ is empty, so terminate the operation.
- In the second operation, go in front of box $$$2$$$. From there, take out a ball labeled $$$2$$$ and go in front of box $$$2$$$. Then take out another ball labeled $$$2$$$ and go in front of box $$$2$$$ again. At this point, box $$$2$$$ is empty, so terminate the operation.
- In this case, the minimum achievable score is $$$2$$$.
- Put one ball labeled $$$1$$$ and one ball labeled $$$2$$$ into each of box $$$1$$$ and box $$$2$$$. ( Probability $$$2/3$$$ )
- In the first operation, go in front of box $$$1$$$. From there, take out a ball labeled $$$1$$$ and go in front of box $$$1$$$. Then take out a ball labeled $$$2$$$ and go in front of box $$$2$$$. Then take out a ball labeled $$$2$$$ and go in front of box $$$2$$$. Then take out a ball labeled $$$1$$$ and go in front of box $$$1$$$. At this point, box $$$1$$$ is empty, so terminate the operation.
- In this case, the minimum achievable score is $$$1$$$.
- Put two balls labeled $$$2$$$ into box $$$1$$$, and two balls labeled $$$1$$$ into box $$$2$$$. ( Probability $$$1/6$$$ )
- In the first operation, go in front of box $$$1$$$. From there, take out a ball labeled $$$2$$$ and go in front of box $$$2$$$. Then take out a ball labeled $$$1$$$ and go in front of box $$$1$$$. Then take out a ball labeled $$$2$$$ and go in front of box $$$2$$$. Then take out a ball labeled $$$1$$$ and go in front of box $$$1$$$. At this point, box $$$1$$$ is empty, so terminate the operation.
- In this case, the minimum achievable score is $$$1$$$.
In summary, the minimum score is $$$2$$$ with probability $$$1/6$$$, and the minimum score is $$$1$$$ with probability $$$5/6$$$, so the expected score overall is $$$7/6$$$. Therefore, output $$$166374060$$$, which represents this value modulo $$$998244353$$$.
It can be proven that the expected value to be found is always a rational number. Also, under the constraints of this problem, if the expected value is written as a reduced fraction $$$\frac{y}{x}$$$, it is guaranteed that $$$x$$$ is not divisible by $$$998244353$$$.
In this case, there exists a unique integer $$$z$$$ between $$$0$$$ and $$$998244352$$$, inclusive, satisfying $$$xz \equiv y \pmod{998244353}$$$. Output this $$$z$$$.
There are $$$10^{16}$$$ cities, labeled $$$1,2,\dots,10^{16}$$$.
For distinct cities $$$i,j$$$, there is a bidirectional road between city $$$i$$$ and city $$$j$$$ if and only if $$$\operatorname{lcm}(i,j)=A\cdot\gcd(i,j)+B$$$.
Answer $$$Q$$$ queries.
In the $$$i$$$-th query, an integer $$$x_i$$$ is given. Output the bitwise XOR of the labels of all cities that are reachable from city $$$x_i$$$ by traversing zero or more roads.
The first line contains integers $$$A,B$$$ in this order, separated by spaces. ($$$1\leq A,B \leq 10^8$$$)
The second line contains an integer $$$Q$$$. ($$$1\leq Q\leq 10^5$$$)
Each of the following $$$Q$$$ lines contains an integer $$$x_i$$$ for the $$$i$$$-th query. ($$$1\leq x_i\leq 10^{16}$$$)
Print $$$Q$$$ lines.
On the $$$i$$$-th line $$$(1\leq i\leq Q)$$$, output the answer to the $$$i$$$-th query.
3 2842026728
28 26 54 108
81781525 39459251053907475616090625029806730076217696038011341614502367555040341613851468112151358558435129081513506101126478601534519491287293575
53908389 6160906250298067 3007621769603801 9491260218029 2151369618045 4034161385146811 2151369618045 332851610359999 112647860153451 9491260218029
For the first example, the existence of a road between cities $$$i,j$$$ is equivalent to $$$\operatorname{lcm}(i,j)=3\cdot\gcd(i,j)+28$$$.
- For the first query, the cities reachable from city $$$20$$$ are $$$8,20$$$.
- For the second query, the only city reachable from city $$$26$$$ is $$$26$$$.
- For the third query, the cities reachable from city $$$7$$$ are $$$7,49$$$.
- For the fourth query, the cities reachable from city $$$28$$$ are $$$28,112$$$.
The bitwise XOR $$$x \oplus y$$$ of non-negative integers $$$x,y$$$ is defined as follows.
- In the binary representation of $$$x \oplus y$$$, the digit at the $$$2^k \ (k \geq 0)$$$ place is $$$1$$$ if and only if exactly one of the digits at the $$$2^k$$$ place in the binary representations of $$$x$$$ and $$$y$$$ is $$$1$$$; otherwise, it is $$$0$$$.
For example, $$$3 \oplus 5 = 6$$$ (in binary, $$$011 \oplus 101 = 110$$$).
Kyoto University has a magnificent symbolic tree as its symbol tree.
Impressed by this symbolic tree, K-kun made a copy of it as a rooted tree with $$$N$$$ vertices.
The vertices of the tree are labeled $$$1,2,\dots,N$$$, the root of the tree is vertex $$$1$$$, and the $$$i$$$-th edge connects vertices $$$u_i$$$ and $$$v_i$$$.
Thinking that merely copying the tree would be uninteresting, K-kun writes a non-negative integer on each vertex of the tree so that the following conditions are satisfied.
Conditions
- The integer written on the root is $$$K$$$.
- For each vertex other than the root, the integer written on that vertex is at most the integer written on its parent.
Find the remainder when the number of possible ways to write integers on the vertices of the tree is divided by $$$998244353$$$.
Two ways of writing integers on the vertices are considered different if and only if there exists some vertex such that the integer written on that vertex is different.
The first line contains integers $$$N,K$$$ separated by spaces. ( $$$2 \leq N \leq 3000, 1 \leq K \leq 10^9$$$ )
Each of the following $$$N-1$$$ lines contains integers $$$u_i,v_i$$$ separated by spaces, representing an edge of the tree.
Output the answer modulo $$$998244353$$$.
5 11 21 33 43 5
10
16 1615 1415 117 1014 24 614 165 31 512 115 72 913 105 149 68 1
623173536
For the first example, the following $$$10$$$ assignments of integers to vertices $$$1,2,3,4,5$$$ satisfy the conditions.
- $$$1,0,0,0,0$$$
- $$$1,0,1,0,0$$$
- $$$1,0,1,0,1$$$
- $$$1,0,1,1,0$$$
- $$$1,0,1,1,1$$$
- $$$1,1,0,0,0$$$
- $$$1,1,1,0,0$$$
- $$$1,1,1,0,1$$$
- $$$1,1,1,1,0$$$
- $$$1,1,1,1,1$$$
This is an interactive problem.
KUPC-kun wrote a program that solves the following problem.
| You are given a tree $$$T=(V,E)$$$ with $$$N$$$ vertices. |
| For a sequence $$$\{a_1,\ldots,a_{k}\}$$$ of vertices of $$$T$$$ of length $$$k$$$, define its score as follows. |
| - Let $$$d(u,v)$$$ be the number of edges on the path between vertices $$$u$$$ and $$$v$$$ in $$$T$$$. Then the score is |
| $$$\prod_{i=1}^{k} d(a_i,a_{(i \bmod k)+1})$$$ |
| A subset $$$S$$$ of $$$V$$$ is given. For each $$$1 \leq k \leq N$$$, find the following value $$$q_k$$$. |
| - The sum of the scores over all vertex sequences $$$\{a_1,\ldots,a_{k}\}$$$ of length $$$k$$$ whose elements belong to $$$S$$$, |
| taken modulo $$$2^{61}-1$$$ |
KUPC-kun secretly keeps the information of the tree $$$T$$$ in advance, and continues using $$$T$$$ as the tree given to the program.
You are trying to recover the information of the leaves using the above program. Letting the number of vertices of the tree be $$$N$$$, you may ask the following question at most $$$N$$$ times.
- Choose a subset $$$S$$$ of $$$V$$$ and ask for the output of the program.
Assuming that KUPC-kun's program is correct, identify all leaves contained in the tree $$$T$$$ from the information obtained through the questions.
The judge is not adaptive, and the tree $$$T$$$ is fixed before the interaction begins.
First, $$$N$$$ is given from standard input. ($$$2 \leq N \leq 50$$$)
For each question, output to standard output in the following format.
| ? $$$s_1s_2\cdots s_N$$$ |
Here, $$$s_1s_2\cdots s_N$$$ is a string of length $$$N$$$ representing the subset $$$S$$$, where $$$s_i=1$$$ if $$$i \in S$$$, and $$$s_i=0$$$ if $$$i \notin S$$$.
In response, the following is given from standard input.
| $$$q_1$$$ $$$q_2$$$ $$$\cdots$$$ $$$q_N$$$ |
Once you have identified all leaves, output your answer in the following format.
| ! $$$t_1t_2\cdots t_N$$$ |
Here, $$$t_1t_2\cdots t_N$$$ is a string of length $$$N$$$, where $$$t_i=1$$$ if $$$i$$$ is a leaf, and $$$t_i=0$$$ if it is not a leaf.
After this output, terminate your program immediately.
Whenever you output something, append a newline at the end and flush standard output.
5 0 8 0 32 0 0 44 108 968 3960 0 0 0 0 0 0 76 348 3336 22200
? 00101 ? 11001 ? 10000 ? 11111 ! 11001
For the first example, the edge set of the tree secretly held by the judge is $$$(1,3),(2,3),(3,4),(4,5)$$$.
In the first question, $$$S=\{3,5\}$$$.
Note that $$$d(3,3)=0,d(3,5)=d(5,3)=2,d(5,5)=0$$$.
For example, there are the following $$$4$$$ vertex sequences $$$a$$$ of length $$$2$$$ whose elements belong to $$$S$$$.
- If $$$a=(3,3)$$$, then the score of this sequence is $$$d(3,3) \times d(3,3) = 0 \times 0 = 0$$$
- If $$$a=(3,5)$$$, then the score of this sequence is $$$d(3,5) \times d(5,3) = 2 \times 2 = 4$$$
- If $$$a=(5,3)$$$, then the score of this sequence is $$$d(5,3) \times d(3,5) = 2 \times 2 = 4$$$
- If $$$a=(5,5)$$$, then the score of this sequence is $$$d(5,5) \times d(5,5) = 0 \times 0 = 0$$$
The judge responds with $$$8$$$ for $$$q_2$$$, which is the remainder when $$$0+4+4+0$$$ is divided by $$$2^{61}-1$$$.
By computing similarly for the other sequence lengths, we obtain the judge's response 0 8 0 32 0.
The leaves of this tree are vertices $$$1,2,5$$$, and outputting ! 11001 correctly completes the identification of the leaves.
A good matrix of size $$$N$$$ is an $$$N \times N$$$ matrix of positive integers such that the total XOR of each row, each column, and both diagonals is $$$0$$$.
More precisely, an $$$N \times N$$$ matrix $$$A$$$ is called a good matrix of size $$$N$$$ if it satisfies all of the following conditions. Here, $$$x \oplus y$$$ denotes the bitwise XOR of $$$x$$$ and $$$y$$$, and $$$\displaystyle \bigoplus_{i=1}^{N} a_i = a_1 \oplus \ldots \oplus a_N$$$.
- $$$A_{i, j}\ (1 \le i, j \le N)$$$ is a positive integer
- For each $$$i = 1, 2, \ldots, N$$$, $$$\displaystyle \bigoplus_{j=1}^{N} A_{i,j}= 0$$$
- For each $$$j = 1, 2, \ldots, N$$$, $$$\displaystyle \bigoplus_{i=1}^{N} A_{i,j}= 0$$$
- $$$\displaystyle \bigoplus_{i=1}^{N} A_{i,i}= 0$$$
- $$$\displaystyle \bigoplus_{i=1}^{N} A_{i,N-i+1}= 0$$$
A positive integer $$$N$$$ is given.
Among all good matrices of size $$$N$$$, output one whose total sum of all elements, $$$\displaystyle \sum_{1 \le i, j \le N} A_{i, j}$$$, is minimum.
If no good matrix of size $$$N$$$ exists, report that.
The input consists of a single integer $$$N$$$. ($$$1 \le N \le 2 \times 10^3$$$)
If no good matrix of size $$$N$$$ exists, print $$$-1$$$ on a single line.
If it exists, print the minimum possible total sum of all elements on the first line.
Then print the matrix $$$A$$$ in the following $$$N$$$ lines, with elements separated by spaces. That is, the $$$(i+1)$$$-th line should contain the elements of the $$$i$$$-th row of matrix $$$A$$$, separated by spaces.
If there are multiple solutions, any of them may be printed.
2
4 1 1 1 1
1
-1
For the first example, the total XOR of each row, each column, and both diagonals is $$$0$$$, so it satisfies the conditions for a good matrix. Also, among all good matrices of size $$$2$$$, the total sum of all elements cannot be made smaller than $$$4$$$, so the minimum value is $$$4$$$.
For the second example, there is no good matrix of size $$$1$$$, so print $$$-1$$$.
The bitwise XOR $$$x \oplus y$$$ of non-negative integers $$$x,y$$$ is defined as follows.
- In the binary representation of $$$x \oplus y$$$, the digit at the $$$2^k \ (k \geq 0)$$$ place is $$$1$$$ if and only if exactly one of the digits at the $$$2^k$$$ place in the binary representations of $$$x$$$ and $$$y$$$ is $$$1$$$; otherwise, it is $$$0$$$.
For example, $$$3 \oplus 5 = 6$$$ (in binary, $$$011 \oplus 101 = 110$$$).
You are given a positive integer $$$N$$$ and a prime number $$$P$$$.
For a permutation $$$(a_1,a_2,\cdots,a_N)$$$ of $$$1,2,\cdots,N$$$, define its score $$$f(a)$$$ as follows.
$$$$$$f(a) = \max\{ia_i\ |\ i=1,2,\cdots,N\}$$$$$$
Find the remainder when the sum of the scores over all permutations is divided by $$$P$$$.
The first line contains $$$N,P$$$ in this order, separated by spaces. ($$$1\leq N\leq 10^4, 10^8\leq P \lt 10^9,P$$$ is prime)
Print the remainder when the sum of the scores over all permutations is divided by $$$P$$$.
10 100000007
77379290
1000 998244353
168695631
For the first example, for instance, $$$f(3,9,4,10,8,2,7,5,6,1)=54$$$.
The sum of the scores over all $$$10!$$$ permutations is $$$277379304$$$, and the remainder when this is divided by the prime $$$P=10^8+7$$$ is $$$77379290$$$, so print $$$77379290$$$. Note that for this input, the prime number $$$P$$$ is the 9-digit integer $$$10^8+7$$$.
Using only resistors with resistance $$$1\;[\Omega]$$$, construct a resistor with resistance $$$\sqrt{D}\;[\Omega]$$$.
You are given a positive integer $$$D$$$. Construct one connected undirected graph satisfying all of the following conditions. Under the constraints of this problem, it can be proven that such a graph always exists.
- The number of vertices $$$N$$$ is between $$$2$$$ and $$$300$$$, inclusive, and each vertex has a distinct label from $$$1$$$ to $$$N$$$
- The number of edges $$$M$$$ is at most $$$300$$$, and self-loops and multiple edges are allowed
- The "effective resistance from vertex $$$1$$$ to vertex $$$N$$$", defined as below, is within an absolute error of $$$\pm 10^{-6}$$$ from $$$\sqrt D$$$
Let $$$G$$$ be a connected undirected graph with $$$n$$$ vertices and $$$m$$$ edges $$$(n\geq2)$$$, and suppose that the $$$j$$$-th edge connects vertices $$$a_j,b_j$$$. Consider assigning a real number $$$V_i\;(i=1,2,\cdots,n)$$$ to each vertex of graph $$$G$$$, and a real number $$$I_j\;(j=1,2,\cdots,m)$$$ to each edge, so that all of the following equations are satisfied.
- $$$I_j = V_{a_j}-V_{b_j}\;\;(j=1,2,\cdots,m)$$$
- $$$\displaystyle\sum_{b_j=i} I_j-\sum_{a_j=i}I_j = 0\;\;(i=2,3,\cdots,n-1)$$$
- $$$\displaystyle\sum_{b_j=n} I_j-\sum_{a_j=n}I_j = 1$$$
It can be proven that such an assignment always exists, and furthermore that the value of $$$V_1-V_n$$$ is uniquely determined. We define this value as the "effective resistance from vertex $$$1$$$ to vertex $$$n$$$".
The input consists of a single positive integer $$$D$$$. ($$$1 \leq D \leq 5000$$$)
On the first line, print the number of vertices $$$N$$$ and the number of edges $$$M$$$ of the constructed graph, in this order, separated by spaces.
On each of the following $$$M$$$ lines, the $$$i$$$-th line $$$(i=1,2,\cdots, M)$$$ should contain the endpoints of the $$$i$$$-th chosen edge, separated by a space.
If there are multiple graphs satisfying the conditions, any one of them may be printed.
1
4 5 1 2 1 3 2 3 2 4 3 4
The following is an illustration of the output for the first example.
That the effective resistance from vertex $$$1$$$ to vertex $$$n$$$ is $$$1\;[\Omega]$$$ can be explained as follows.
- Since all resistors have resistance $$$1\;[\Omega]$$$, and by symmetry the potentials at vertices $$$2$$$ and $$$3$$$ are equal, the resistor between them can be treated as if it does not exist.
- As a result, the circuit reduces to two branches in parallel, each branch consisting of two $$$1\;[\Omega]$$$ resistors in series.
- The effective resistance of two $$$1\;[\Omega]$$$ resistors in series is $$$2\;[\Omega]$$$, and the effective resistance of two $$$2\;[\Omega]$$$ resistors in parallel is $$$1\;[\Omega]$$$.
The following output is also considered correct.
| 2 1 |
| 1 2 |
There is a string $$$S$$$ of length $$$N$$$ consisting of uppercase English letters. You may perform the following operation on $$$S$$$ any number of times.
- Choose a quadruple of integers $$$(i,j,k,l)$$$ such that $$$1 \leq i \lt j \lt k \lt l \leq \lvert S \rvert$$$, $$$S_i=$$$ K, $$$S_j=$$$ U, $$$S_k=$$$ P, and $$$S_l=$$$ C. Replace all of $$$S_i,S_j,S_k,S_l$$$ with X, and earn $$$(i \times j \times k \times l)$$$ yen.
The first line contains an integer $$$N$$$. ( $$$1 \leq N \leq 5 \times 10^5$$$ )
The second line contains a string $$$S$$$ of length $$$N$$$ consisting of uppercase English letters.
Print the answer.
10KKUPCUCAPC
1164
4TUNA
0
30KUCCKCKKPUKUPCUCPUCKPCKKUUPCPK
619704
Note that you are asked for the remainder of the maximum value, not the maximum possible remainder.
For the first example, you can earn $$$1164$$$ yen by performing the following operations.
- Choose $$$(i,j,k,l) = (1,3,4,7)$$$. You earn $$$1 \times 3 \times 4 \times 7 = 84$$$ yen. Then $$$S =$$$ XKXXCUXAPC.
- Choose $$$(i,j,k,l) = (2,6,9,10)$$$. You earn $$$2 \times 6 \times 9 \times 10 = 1080$$$ yen. Then $$$S =$$$ XXXXCXXXAXX.
For the second example, no operation can be performed even once, so print $$$0$$$.
You are given a sequence $$$A=(A_1,A_2,\dots,A_N)$$$ of length $$$N$$$ consisting of integers greater than or equal to $$$-1$$$. Using this sequence and a parameter $$$c$$$, perform the following operations.
- Initially, set the variable $$$x:=0$$$.
- For $$$i=1,2,\dots,N$$$, repeat the following operation.
- If $$$A_i = -1$$$, replace $$$x$$$ with $$$x := \max(0,x-c)$$$.
- Otherwise, replace $$$x$$$ with $$$x := x+A_i$$$.
Answer $$$Q$$$ questions of the following form.
- When the parameter $$$c=C_i$$$, find the maximum value attained by $$$x$$$ over the entire sequence of operations.
The first line contains $$$N,Q$$$ in this order. $$$(1 \le N,Q \le 3 \times 10^5)$$$
The second line contains $$$N$$$ integers $$$A_i$$$. $$$(-1 \le A_i \le 10^6)$$$
Each of the following $$$Q$$$ lines contains the value of $$$C_i$$$ for the $$$i$$$-th question. $$$(0 \le C_i \le 10^6)$$$
Print $$$Q$$$ lines.
On the $$$i$$$-th of these lines, print the answer to the $$$i$$$-th question.
20 11 50 100 50 100 0 200 -1 50 100 -1 200 -1 200 0 200 -1 200 200 -1 200 30 60 90 180 270 360 540 200 400 600 0
1700 1550 1400 950 570 500 500 850 500 500 1850
We explain the first question of the first example input.
- In this question, the parameter is $$$c=30$$$.
- Initially, the variable is $$$x=0$$$.
- Since $$$A_1 = 50$$$, $$$x$$$ is updated to $$$x=0+50=50$$$.
- Since $$$A_2 = 100$$$, $$$x$$$ is updated to $$$x=50+100=150$$$.
- $$$\dots$$$
- Since $$$A_6=200$$$, $$$x$$$ is updated to $$$x=300+200=500$$$.
- Since $$$A_7=-1$$$, $$$x$$$ is updated to $$$x = \max(0,500-30) = 470$$$.
- $$$\dots$$$
- Since $$$A_{19}=-1$$$, $$$x$$$ is updated to $$$x = \max(0,1530-30) = 1500$$$.
- Since $$$A_{20}=200$$$, $$$x$$$ is updated to $$$x=1500+200=1700$$$.
Including the omitted parts, the maximum value attained by $$$x$$$ over the entire sequence of operations is $$$1700$$$.
You are given two integers $$$N$$$ and $$$M$$$.
Output, in the format specified in the Output section, an $$$N \times N$$$ grid whose cells are colored either white or black and which satisfies the following conditions. If no such grid exists, print -1.
- The sizes of the connected components of white cells appearing in the grid consist of exactly $$$M$$$ distinct values
- The sizes of the connected components of black cells appearing in the grid consist of exactly $$$M$$$ distinct values
If there are multiple solutions, you may output any of them.
The first line contains integers $$$N,M$$$ in this order, separated by spaces. ( $$$2 \leq N \leq 2000, 1 \leq M \leq 2000$$$ )
If a grid satisfying the conditions exists, print $$$N$$$ lines. On the $$$i$$$-th of these lines $$$(1 \leq i \leq N)$$$, print a string $$$s_i$$$ of length $$$N$$$ as follows.
- If the cell in row $$$i$$$, column $$$j$$$ $$$(1 \leq j \leq N)$$$ of the constructed grid is colored white, then the $$$j$$$-th character of $$$s_i$$$ must be .(dot).
- If the cell in row $$$i$$$, column $$$j$$$ $$$(1 \leq j \leq N)$$$ of the constructed grid is colored black, then the $$$j$$$-th character of $$$s_i$$$ must be #.
If no grid satisfying the conditions exists, print -1 on the first line.
4 2
###. ..## ##.# .##.
2 3
-1
12 7
.#..#.#.##.# .#.#..#.##.# .##...#.##.# .#.#..#.##.# .#..#.##..## ......###### ######...... #...##..###. #.##.#.#.... #...##.#.... #.####.#.... #.####..###.
Two white cells $$$c_1,\ c_2$$$ are said to be connected if one can move from $$$c_1$$$ to $$$c_2$$$ by repeatedly moving to a vertically or horizontally adjacent cell and passing only through white cells.
A set $$$S$$$ of white cells is called a connected component if $$$S$$$ satisfies the following conditions.
- Any two cells in $$$S$$$ are connected.
- No white cell not contained in $$$S$$$ is connected to any cell contained in $$$S$$$.
Connected components of black cells are defined similarly.
For each connected component, its size is defined as the number of cells it contains.
Below is an appendix.
Explanation of Sample Output $$$1$$$
The sizes of the connected components of white cells are the two distinct values $$$1$$$ and $$$2$$$. The sizes of the connected components of black cells are also the two distinct values $$$4$$$ and $$$6$$$.
Figure for Sample Output $$$1$$$
Figure for Sample Output $$$3$$$
You are given a positive integer $$$N$$$.
Find the number of pairs of integers $$$(a,b)$$$ such that $$$1 \leq a,b \lt 2^N$$$ and the following condition is satisfied, modulo the prime $$$998244353$$$.
- There exists a non-degenerate triangle whose side lengths are $$$a,b,a\oplus b$$$.
Here, for integers $$$x,y$$$, $$$x\oplus y$$$ denotes the bitwise XOR of $$$x$$$ and $$$y$$$.
The first line contains an integer $$$N$$$. ($$$1 \leq N \leq 10^{18}$$$)
Print the number of pairs of integers $$$(a,b)$$$ satisfying the condition, modulo the prime $$$998244353$$$.
2
0
5
390
10000
851087540
For the second example, for instance, $$$(a,b)=(13,24)$$$ satisfies the condition. Since $$$a \oplus b = 13 \oplus 24 = 21$$$, there exists a non-degenerate triangle whose side lengths are $$$13,24,21$$$.
There are exactly $$$390$$$ pairs of integers $$$(a,b)$$$ satisfying the condition.
The bitwise XOR $$$x \oplus y$$$ of non-negative integers $$$x,y$$$ is defined as follows.
- In the binary representation of $$$x \oplus y$$$, the digit at the $$$2^k \ (k \geq 0)$$$ place is $$$1$$$ if and only if exactly one of the digits at the $$$2^k$$$ place in the binary representations of $$$x$$$ and $$$y$$$ is $$$1$$$; otherwise, it is $$$0$$$.
For example, $$$3 \oplus 5 = 6$$$ (in binary, $$$011 \oplus 101 = 110$$$).
This problem is supposed to be the easiest one in KUPC2025. It was removed when the contest was ported to Universal Cup.
An event was held over $$$N$$$ days, and the number of participants on day $$$i$$$ was $$$A_i$$$.
On which day was the number of participants the largest, and how many participants were there on that day?
It is guaranteed that the numbers of participants on different days are all distinct.
The first line contains an integer $$$N$$$. ( $$$1 \leq N \leq 10^5$$$ )
The second line contains $$$N$$$ integers $$$A_1,A_2,\dots,A_N$$$ in this order, separated by spaces. ( $$$1\leq A_i\leq 10^9, i \neq j \Rightarrow A_i \neq A_j$$$ )
Let the day with the largest number of participants be day $$$k$$$. Print $$$k$$$ and $$$A_k$$$ on one line, separated by a space.
41 2 4 3
3 4
931 4 15 9 26 5 35 89 7
8 89
1100
1 100
For the third example, the event may be held for only one day.
This problem is supposed to be the second easiest one in KUPC2025. It was removed when the contest was ported to Universal Cup.
Consider a calendar that starts on Sunday and ends on Saturday. In this problem, the definition of the calendar follows the Gregorian calendar.
More precisely, the calendar for month $$$M$$$ of year $$$Y$$$ is drawn in the following way.
- First, prepare a grid with $$$7$$$ columns and sufficiently many rows. Initially, all cells are blank. We number the rows from the top as row $$$1,2,\dots$$$, and the columns from the left as column $$$1,2,\dots,7$$$.
- Next, define column $$$1$$$ to be Sunday, column $$$2$$$ to be Monday, $$$\dots$$$, and column $$$7$$$ to be Saturday.
- Next, determine the day of the week of $$$Y$$$ year, $$$M$$$ month, $$$1$$$-st day, and write $$$1$$$ in the corresponding column of row $$$1$$$.
- After that, repeat writing day $$$d$$$ of month $$$M$$$ in year $$$Y$$$ until the last day of the month.
- If day $$$d$$$ is a Sunday, write $$$d$$$ in column $$$1$$$ of the row immediately below the row where the previous day was written.
- Otherwise, write $$$d$$$ in the cell immediately to the right of the cell where the previous day was written.
The figure shows the calendar for March 2026. The weekday labels have been added only for convenience.
For the calendar of month $$$M$$$ in year $$$Y$$$, we call the following structure a calendar square.
- When we take rows $$$u$$$ through $$$d$$$ and columns $$$l$$$ through $$$r$$$, every cell contains a number.
- Here, it must hold that $$$d-u=r-l$$$.
- In this case, we call this structure a calendar square of size $$$d-u+1$$$.
For example,
- The structure consisting only of day $$$14$$$ is a calendar square of size $$$1$$$.
- The structure consisting of days $$$22,23,29,30$$$ is a calendar square of size $$$2$$$.
- The structure consisting of days $$$3,4,5,6,10,11,12,13,17,18,19,20,24,25,26,27$$$ is a calendar square of size $$$4$$$.
For the calendar squares contained in month $$$M$$$ of year $$$Y$$$, find the size of the largest one.
The first line contains integers $$$Y,M$$$ in this order. ($$$1900 \le Y \le 2999, 1 \le M \le 12$$$)
Print the answer.
2026 3
4
This problem is supposed to be the third easiest one in KUPC2025. It was removed when the contest was ported to Universal Cup.
$$$N$$$ people play one round of rock-paper-scissors.
Determine whether there exists a way for them to choose their hands such that the total number of extended fingers among all players is exactly $$$M$$$.
Furthermore, determine whether, among such ways, there exists at least one in which the game has a winner (that is, it is not a draw).
The first line contains integers $$$N, M$$$ in this order. $$$(2 \leq N \leq 10^{18}, 0 \leq M \leq 10^{18})$$$
If there is no way for all players to choose their hands so that the total number of extended fingers is exactly $$$M$$$, print Impossible.
If such a way exists, then print Yes if there is at least one such way in which the game has a winner (that is, it is not a draw), and print No if there is no such way (that is, no matter how the hands are chosen, the game is always a draw).
2 7
Yes
3 0
No
4 3
Impossible
123456789123456789 987654321987654321
Impossible
For the first example, if the two players choose scissors and paper, respectively, then the total number of fingers is $$$7$$$, and the game has a winner. Therefore, print Yes.
For the second example, if the three players all choose rock, then the total number of extended fingers is $$$0$$$, but the game is a draw. Since there is no way for the three players to choose hands so that the total number of extended fingers is $$$0$$$ and the game has a winner, print No.
For the third example, there is no way for four players to choose hands so that the total number of extended fingers is $$$3$$$, so print Impossible.
Supplement: rules of rock-paper-scissors
Each person chooses exactly one of the three hands: "rock", "scissors", or "paper". The number of extended fingers for each hand is as follows.
- Rock: $$$0$$$
- Scissors: $$$2$$$
- Paper: $$$5$$$
The rules determining the winner are as follows.
- Rock beats scissors and loses to paper.
- Paper beats rock and loses to scissors.
- Scissors beat paper and lose to rock.
When there are $$$2$$$ players, in addition to the above, the game is a draw if both players choose the same hand. When there are $$$3$$$ or more players, the game has a winner if the hands chosen by all players consist of exactly $$$2$$$ of the $$$3$$$ possible hand types. For example, if among $$$5$$$ players, $$$2$$$ choose paper and $$$3$$$ choose rock, then the $$$2$$$ players who chose paper are the winners. If all players choose the same hand, or if all three hand types appear, then the game is a draw.
(Quoted and partially modified from Wikipedia "Rock paper scissors".)