The Everfree Forest, located in the northwestern Equestrian Wasteland, is a large expanse of woodland that has yet to be exposed to megaspell radiation.
To learn Everfree Forest from a scientific perspective, Twilight Sparkle considers it as an undirected connected graph of $$$n$$$ vertices without self-loop and multiple edges, the degree of vertex in which is no more than $$$3$$$.
After field exploration, Twilight Sparkle believes there are exactly $$$k$$$ 3-degree vectices in this graph.
Now she wants to know, what's the maximal edges the graph could have, and what about the minimal edges?
The first line contains a single integer $$$T\ (1\le T\le 10^5)$$$ - the number of testcases.
Each testcase contains only one line, two integers $$$n,k\ (0\le k \lt n,6\le n\le 10^5,\sum n\le 10^5)$$$.
For each testcase:
The fisrt line contains a single integer $$$m_1$$$ - the maximal edges it could has.
The next $$$m_1$$$ lines, each line contaions two integer $$$u_i,v_i$$$ - the edges in it.
The next line contains a single integer $$$m_2$$$ - the minimal edges it could has.
Then next $$$m_2$$$ lines, each line contaions two integer $$$w_i,p_i$$$ - the edges in it.
You should make sure that the graph you output is an undirected connected graph of $$$n$$$ vertices without self-loop and multiple edges.
If there are multiple solutions, just output any of them, it could be proved that there exits at least one solution.
2 6 0 6 3
6 1 2 2 3 3 4 4 5 5 6 6 1 5 1 2 2 3 3 4 4 5 5 6 7 1 2 2 3 3 4 4 5 5 1 1 3 2 6 6 1 2 2 3 3 1 1 4 2 5 3 6
There are valid solutions of the test case.
 |  |  |  |
| maximal edges in testcase 1 | minimal edges in testcase 1 | maximal edges in testcase 2 | minimal edges in testcase 2 |
This is an easy math problem.
We define a function $$$f(x)$$$ to represent how many pairs of factors $$$(p,q)$$$ of $$$x$$$ satisfy that $$$p$$$ and $$$q$$$ are coprime. When $$$p\not=q$$$ , $$$(p,q)$$$ and $$$(q,p)$$$ are different pairs.
$$$$$$ f(x)=\sum_{p,q|x}[ gcd(p,q)=1 ] $$$$$$
Now we want to calculate
$$$$$$ g(n)=\sum_{i=1}^n f(i) $$$$$$
The answer maybe too large, so you only need to output the result of its modulo of 998244353
A single integer $$$n(1\le n\le 10^{10})$$$
A single integer $$$g(n)$$$
10
48
A tree is an undirected connected graph with $$$n$$$ nodes and $$$n - 1$$$ edges. A leaf node refers to a node with degree 1, that is, a node connected to only one node.
You are given an unrooted tree, there are hamsters in some nodes of this tree, and your task is to catch all the hamsters. For this, you can place mousetraps at some nodes. If the hamster moves to the node where the mousetrap is placed, it will be caught immediately. Note that in this problem we consider the capacity of the mousetrap to be infinite, that is, the mousetrap at a single node can also hold an infinite number of hamsters.
Every second, each hamster moves to an adjacent vertex. A hamster cannot move along the same edge twice in a row, unless it entered a leaf node from a non-leaf node in the previous step, in which case it can return from the original edge. Find the minimum number of nodes to place mousetraps so that all hamsters will eventually be caught, regardless of their initial positions and escape strategies.
The first line of input contains a positive integer $$$n(1 \leq n \leq 10^5)$$$, representing the number of nodes in the tree.
The following $$$n - 1$$$ lines, each line contains 2 positive integers $$$u, v(1\leq u, v\leq n)$$$, indicating that there is an edge connecting node $$$u$$$ and node $$$v$$$.
Print a positive integer representing the minimum number of nodes on which to place the mousetrap.
3 1 2 2 3
1
10 2 8 5 10 3 4 1 6 3 9 1 7 4 8 10 8 1 8
2
For the first testcase, you can place a mousetrap at node 2, because every possible route of the hamsters will certainly include node 2.
The girls of HTT like drinking tea. But one day, they wanted a change and decided to try coffee in the next $$$n$$$ days.
Now Mugi, who always provides food and drinks for HTT, will go to the shop to buy some coffee. She learns that the price of coffee on day $$$i$$$ is $$$a_i$$$ . Now she has $$$m$$$ coupons. The $$$i$$$ th coupon can be used before day $$$r_i$$$ (it can also be used on day $$$r_i$$$) and can reduce the price of coffee on that day by $$$w_i$$$ . $$$\textbf{Notice that the price can be a negative number after using the coupon.}$$$ Each coupon can be used only once, and Mugi cannot use more than one coupon per day.
Since the girls of HTT still need to drink tea, Mugi decided to choose $$$\textbf{exactly}$$$ $$$k$$$ days to buy coffee. Now she wants to know the minimum money she will spend (or the maximum money she can get) to choose exactly $$$k$$$ days to buy coffee.
The first line contains two integers $$$n,m\ (1 \le n \le 10^5, 1 \le m \le 2 \times 10^5)$$$ - the number of days and the number of coupons.
The second line contains $$$n$$$ integers $$$a_1,a_2,...,a_n(1 \le a_i \le 10^9)$$$ , and $$$a_i$$$ denoting the price of coffee on day $$$i$$$ .
Next $$$m$$$ lines, each line contains two integers $$$r_i,w_i(1 \le r_i \le n,1 \le w_i \le 10^9)$$$ , denoting that the $$$i$$$ th coupon can be used before day $$$r_i$$$ and can reduce the price by $$$w_i$$$ .
Next line contains an integer $$$k(1 \le k \le n)$$$ , denoting the number of days that Mugi will buy coffee.
One integer - the minimum money Mugi will spend to buy coffee. Notice that the answer can be a negative integer.
5 2 1 2 3 4 5 3 1 4 2 5
12
7 3 4 3 1 10 3 8 6 4 9 3 8 4 5 5
-5
In the first example, Mugi can use coupon $$$1$$$ on day $$$1$$$ and use coupon $$$2$$$ on day $$$2$$$ to spend $$$0+0+3+4+5=12$$$.
In the second example, Mugi can use coupon $$$1$$$ on day $$$2$$$, coupon $$$2$$$ on day $$$3$$$ and coupon $$$3$$$ on day $$$1$$$. Then she can choose to buy coffee on day $$$1,2,3,5,7$$$ and spend $$$(-1)+(-6)+(-7)+3+6=-5$$$ .
Find the number of $$$x$$$ satisfied the following condition:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10000$$$) — the number of testcases. Each testcase contains two integers $$$n$$$ and $$$a$$$ in a line. ($$$1 \leq a \leq n \leq 10^{18}$$$)
For each testcase, print the number of $$$x$$$ satisfied the given conditions in a single line. Since the answer can be large, print it modulo $$$998244353$$$.
11 1
2
There are $$$n$$$ cats here, numbered from $$$1$$$ to $$$n$$$. They desire to fight.
We call the cat numbered $$$i$$$ as "Cat $$$i$$$". For every $$$i \in [1, n]$$$, Cat $$$i$$$ wants to fight with every nonadjacent cat.
For example, when $$$n = 4$$$, Cat $$$1$$$ wants to fight with $$$3$$$ and $$$4$$$, Cat $$$2$$$ wants to fight with $$$4$$$, Cat $$$3$$$ wants to fight with $$$1$$$, Cat $$$4$$$ wants to fight with $$$1$$$ and $$$2$$$.
You should arrange rounds to satisfy their desires. In each round, you can choose some cats from them, and divide the chosen cats into two nonempty groups. Obviously, a cat can't appears in both groups in a single round.
And in this round, every pair $$$(i, j)$$$ which Cat $$$i$$$ and $$$j$$$ is chosen and set in different groups will fight with each other.
Be careful, you cannot arrange adjacent cats to fight in any round. They will feel unhappy. Formally, if you want to choose Cat $$$i$$$ and Cat $$$i+1$$$ in a round, they should in the same group.
For example, you can arrange $$$[1, 2, 4]$$$ to fight with $$$[6, 7]$$$. But you can't arrange $$$[1, 2, 4]$$$ to fight with $$$[3, 6, 7]$$$, because $$$3$$$ don't want to fight with $$$2$$$ or $$$4$$$.
We don't care about how many fights actually happened in all rounds. In other words, for each pair $$$(i, j)$$$ when $$$|i-j| \gt 1$$$, they should fight at least once in all rounds. Arrange two cats to fight again and again is not banned, although it may be useless.
To save time, you should find the minimum number of rounds to satisfy them all, and how to arrange each round.
If there are mutiple solutions, output any of them.
The input contains an integer $$$n$$$ ($$$3 \leq n \leq 10^3$$$) — the number of cats waiting for fight.
The first line contains an integer $$$m$$$ — the number of rounds you arrange.
The following $$$2m$$$ lines shows each round you arrange. For each round, print two lines for your two groups:
The first line contains $$$n_1$$$ — the number of cats in first group, and followed with $$$n_a$$$ integers $$$a_1, a_2, ... a_{n_1}$$$, donates the cat's id.
The second line is similar, contains $$$n_2$$$ and $$$b_1, b_2, ... b_{n_2}$$$.
3
1 1 1 1 3
4
2 2 1 2 1 4 1 1 1 3
In the first example, we only need one round to let Cat $$$1$$$ and Cat $$$3$$$ fight with each other.
In the second example, we can prove $$$2$$$ is the minimum rounds we need. $$$(1, 3), (1, 4), (2, 4)$$$ needs to fight in this example. And there are many correct solutions for $$$n = 4$$$. The following solution is considered correct too:
2
1 1
2 4 3
2 1 2
1 4
Microsoft Hearts is a classical game of Microsoft Windows. Let's look at Microsoft Hearts of 2 players.
Each player has $$$n$$$ cards initially. There is one of the four suits on one single card: H-Heart$$$\heartsuit$$$, S-Spade$$$\spadesuit$$$, D-Diamond$$$\diamondsuit$$$, C-Club$$$\clubsuit$$$.
The cards are ranked by the point on it. The smallest is 2, and the greatest is A, in which A stands for 14, T stands for 10, i.e. 2<3<4<5<6<7<8<9<T<J<Q<K<A.
The game has following rules.
Each round, the player who has the token would put one of his/her card out. Then the other player can play as following restrictions.
At the end, when players put all 13 cards out, a player's score is the number of HEART cards of his/her scoring area. The player with minor score wins. If the scores are the same, Alice wins.
Additional, we don't consider the "Shoot the Moon" of Spade$$$\spadesuit$$$ Q. Just follow the rules above.
Now, Alice and Bob are playing a Microsoft Hearts of 2 players. Both of them know the cards of each other. At the beginning, Alice has the token to put the card out first.
Alice wants to know, if both of them play the game optimally for themselves, whether she will win the game. Output "Yes" or "No".
The first line contains a single positive integer $$$n\ (n\le 13)$$$, denoting the number of cards of one player.
The following two lines, each line contains $$$n$$$ strings, denoting Alice's and Bob's cards, respectively. The string contains the rank and the suit. For example "7H" stands for $$$\heartsuit7$$$, "TS" stands for $$$\spadesuit10$$$.
Print one single line.
If Alice wins, print "Yes". Otherwise, print "No".
3 AH JH 7S 3H TD 5H
No
How many positive integer sequences of length $$$n$$$ satisfy that $$$1 \le a_i \le m$$$, and the adjacent elements are coprime.
The answer maybe too large, so you only need to output the result of its modulo of 998244353.
Two positive ingeter $$$n(1\le n \le 1000)$$$,$$$m(1\le m \le 1000)$$$.
An integer represents the answer.
2 5
19
Starlight Glimmer has a bracket sequence $$$s$$$ of lenght $$$n$$$, which only contains character '(', ')' and '?'.
She also has a value sequence $$$v$$$ of lenght $$$n$$$ constructed by two integer constants $$$a,b$$$ that $$$v_i=ai+b$$$.
Define that the partition of a sequence is a pair sequence $$$(l_i,r_i)$$$ of length $$$m$$$ if it satisfies $$$l_1\le r_1 \lt l_2\le r_2 \lt \dots \lt l_{m-1}\le r_{m-1} \lt l_m\le r_m$$$ and any substring $$$(l_i,r_i)$$$ is a valid bracket sequence.
The substring $$$(l,r)$$$ of $$$s$$$ is a string removed first $$$l-1$$$ characters and last $$$n-r$$$ characters of $$$s$$$, and Starlight Glimmer believes it valid if:
According to the above, Starlight Glimmer defines the value of $$$s$$$ is $$$\max_{partition}\sum v_{r_i+1-l_i}$$$.
Now Starlight Glimmer should and find the maximal value of $$$s$$$ if she replace all '?' to '(' or ')' in a optimal way.
The first line contains a single integer $$$n\ (1\le n\le 5\times 10^5)$$$ - the length of $$$s$$$.
The second line contains a string $$$s$$$ of lenght $$$n$$$ - denoting the bracket sequence $$$s$$$.
The third line contains two integer $$$a,b\ (-10^6\le a,b\le 10^6)$$$ - denoting $$$v_i=ai+b$$$.
Print a single integer - the maximal value of $$$s$$$ after replacement.
10 (?)(??(?)? 1 2
14
For the testcase, $$$v=[3,4,5,6,7,8,9,10,11,12]$$$.
The result of a possible replacement is '(()()(()))', and Starlight Glimmer could choose $$$(2,3),(4,5),(6,9)$$$ as a partition, the value of it is $$$v_2+v_2+v_4=4+4+6=14$$$.
You are given an array $$$A$$$ with $$$n$$$ integers. If an interval $$$[L,R]$$$ satisfies that the sequence $$$(A_L,A_{L+1},\cdots,A_R)$$$ has at least an odd number and at least an even number, we consider the interval $$$[L,R]$$$ as a perfect interval.
Now you are given $$$q$$$ questions, each question contains an interval $$$[X,Y]$$$. You need to answer how many intervals $$$[L,R]$$$ satisfying $$$(X \leq L \leq R \leq Y)$$$ are perfect.
The first line contains two integers $$$n$$$ and $$$q$$$ $$$(1 \leq n,q \leq 5\cdot 10^5)$$$, indicating the length of array $$$A$$$ and the number of questions.
The second line contains $$$n$$$ integers, indicating $$$A_i$$$ $$$(0\leq A_i \leq 10^9)$$$.
From the third line to $$$(q+2)$$$-th line each line contains two intergers $$$X$$$ and $$$Y$$$ $$$(1 \leq X \leq Y \leq n)$$$, indicating the interval $$$[X,Y]$$$.
The output has $$$q$$$ lines, each line contains one interger, indicating the answer of each question.
10 5 1 3 4 1 3 4 3 1 7 9 1 5 3 9 2 10 4 7 1 2
8 17 29 5 0
Sunset Shimmer defines the value of a permutation $$$p$$$ of length $$$n$$$ is $$$\sum_{i=1}^np_i\oplus i$$$, the $$$\oplus$$$ represents bitwise XOR.
Now she wants to know the maximal value of permutation of lenght $$$n$$$.
The first line contains a single integer $$$T\ (1\le T\le 10^5)$$$ - the number of testcases.
Each testcase contains a single integer $$$n(1\le \sum n\le 10^5)$$$ - the length of the permutation.
For each testcase, print one line of $$$n$$$ integers , represents the maximal value permutation of length $$$n$$$.
If there are multiple solutions, just output any of them.
2 3 5
3 1 2 5 1 4 3 2
FYC is a fucking cute boy who wants to write a beautiful love letter to the girl he likes. FYC knows a kind of character magic, and to show his sincerity, he first writes a love letter and then wishes to polish it with his own magic.
A love letter is a string, and a beautiful love letter must be a palindrome. FYC hopes that throughout the polishing process, his love letters will always be beautiful, that is, before using magic, during the process of being modified by magic, and after being modified by magic, love letters are always palindrome strings. The magic of FYC is carried out on the magic dictionary. There are $$$n$$$ pages in the dictionary, and each page has a string. If the current love letter of FYC is the same as a certain substring of a certain page, then the love letter can be combined with the substring, and then modified by magic. FYC has the following three kinds of magic:
1. If the substring of the current string has two identical characters outside the two ends, you can spend $$$a_{ij}$$$ costs to add these two identical characters to your love letter.
2. You can spend $$$b_{ij}$$$ costs to delete the characters on both ends of the current love letter, but your love letter cannot be empty.
3. If in a certain position in the entire magic dictionary, there exists a substring that is the same as the substring you currently hold, you can spend $$$|i-j|$$$ costs to jump to the position of another substring, $$$i$$$ and $$$j$$$ are the two page numbers where the string is located. However, the distance of the page number between the target string and the current string cannot exceed $$$k$$$.
FYC has done some operations, but he doesn't know what to do next, and now he wants to ask for your help. That is, the love letter has now been placed on a certain substring on a certain page of the magic dictionary, and now it is hoped that you will use magic to transform the love letter into what he wants, and take it off a certain page . Please tell him what is the minimum cost he needs to spend.
The first line $$$n$$$ and $$$k$$$ indicate a total of $$$n$$$ strings and the range limit of operation $$$3$$$;
The next $$$3n$$$ lines have the following format:
On the first line there is a string representing what the string on page $$$i$$$ of the dictionary looks like. The length of the $$$i^{th}$$$ string is $$$m_i$$$.
The second line contains $$$26$$$ integer, indicating the cost of adding the two identical corresponding character $$$(a-z)$$$ to the current page at the $$$operation 1$$$.
The third line has $$$26$$$ numbers, which represent the cost of deleting $$$(a-z)$$$ the two identical corresponding character in the current page $$$operation 2$$$.
A number on the next line represents the page number of the string where the starting string is located, and a string of characters represents the starting string;
The next line is a number indicating which page FYC wants to get the target string from, and a number indicating which page FYC wants to get the target string in the end;
It is guaranted that all given letters are lower case letters.
$$$1 \le n \le 100000$$$
$$$1 \le m_i \le 1000000$$$
$$$\sum m \le 1000000$$$
$$$k \le n$$$
A line that represents the minimum mana cost. If FYC can't get the love letter he wants, output -1;
2 1 ababa 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ababa 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 a 2 bab
2
Now there are $$$n$$$ people lining up to get some water, the $$$i^{th}$$$ person wants to get $$$c_i$$$ liters of water into his or her bottle.
When the bucket of water on the water dispenser runs out (Each bucket of water provides $$$C$$$ liters of water) , the one who is using the water dispenser (includes the last one) will replace the bucket on the dispenser with a new bucket or water, even if he or she have got enough water. Then he or she leaves right away, so one may leaves with less water than one wants.
Now you want to know how many buckets of water needed (including the first bucket).
The first line contains a single integer $$$T\ (1\le T\le 100)$$$ - the number of testcases.
Each testcase contains two lines.
The first line contains two integers $$$n,C\ (1\le \sum n\le 10^6,1\le C\le 10^3)$$$.
The second line contains $$$n$$$ integers $$$c_i\ (1\le c_i\le10^3)$$$.
For each testcase, print a positive integer representing the number of buckets needed.
4 3 1 6 4 5 4 1 1 6 4 5 2 10 5 2 5 10 8 6 7 10 2
4 5 1 3