You are given a labeled tree on $$$n$$$ vertices with labels $$$1\dots n$$$. Vertex $$$1$$$ is the root, and along every edge from a vertex to its parent, labels strictly decrease (equivalently, labels strictly increase along any path from the root to a vertex). Formally, if $$$p(v)$$$ is the parent of $$$v$$$, then $$$\text{label}[v] \gt \text{label}[p(v)]$$$, and $$$\text{label}[1] = 1$$$.
The first line contains a single integer $$$t$$$ $$$(1 \le t \le 2000)$$$ — the number of test cases. Each test case consists of a single integer $$$n$$$ $$$(1 \le n \le 20)$$$.
For each test case, print a single integer — the number of decreasing trees on $$$n$$$ labeled vertices.
4 1 2 3 4
1 1 2 6
- For $$$n = 1$$$: there is exactly one valid tree: just vertex 1.
- For $$$n = 2$$$: there is exactly one valid tree: $$$1 \to 2$$$.
- For $$$n = 3$$$: there are exactly two valid trees: the star $$$1 \to 2, 1 \to 3$$$ and the chain $$$1 \to 2 \to 3$$$.
- For $$$n = 4$$$: there are exactly six valid trees.
Alice has a dartboard consisting of $$$N$$$ concentric convex polygons numbered from $$$1$$$ to $$$N$$$ (from innermost to outermost). Each polygon $$$i$$$ has a score $$$S_i$$$ and is given by its vertices in the plane. When a dart lands on the dartboard, its score is $$$S_i$$$, where $$$i$$$ is the smallest index such that the dart lies inside polygon $$$i$$$. In other words, if a dart lies inside multiple polygons, the innermost one determines the score.
Alice throws $$$M$$$ darts in total:
- For $$$K$$$ darts (precision mode), Alice chooses a polygon $$$t$$$. The dart lands uniformly at random inside polygon $$$t$$$.
- For the remaining $$$(M-K)$$$ darts, each dart lands uniformly at random inside the outermost polygon.
Alice wants to maximize her expected total score. Find this maximum expected score. Since the answer is a rational number $$$\frac{P}{Q}$$$, output it as $$$P \times Q^{-1} \pmod{10^9+7}$$$.
The first line contains three integers $$$N, M, K$$$ $$$(1 \le N \le 10^3, 1 \le M \le 10^3, 0 \le K \le M)$$$ — the number of polygons, total darts, and precision darts.
The second line contains $$$N$$$ integers $$$S_1, S_2, \ldots, S_N$$$ $$$(1 \le S_i \le 10^3)$$$ — the scores of the polygons.
Then for each polygon $$$i$$$ $$$(1 \le i \le N)$$$:
- The first line contains an integer $$$v_i$$$ $$$(3 \le v_i \le 10^3)$$$ — the number of vertices of polygon $$$i$$$.
- Each of the next $$$v_i$$$ lines contains two integers $$$x_j, y_j$$$ $$$(|x_j|, |y_j| \le 10^3)$$$ — the coordinates of the vertices in counterclockwise order.
It is guaranteed that polygons are concentric and strictly nested: polygon $$$i$$$ lies strictly inside polygon $$$i+1$$$.
Print a single integer — the maximum expected total score modulo $$$10^9+7$$$.
3 565 552 939 327 520 5 -475 -422 447 -175 731 54 -479 404 -811 23 7 -832 -272 191 -747 361 -548 927 310 264 739 -517 677 -866 -24 7 -864 -403 -447 -882 138 -873 983 284 929 969 -301 843 -934 374
600579066
You are given an array of $$$N$$$ integers $$$a_1, a_2, \dots, a_N$$$.
A subarray is called valid if the greatest common divisor (GCD) of all its elements is a prime number.
Your task is to determine the maximum possible length of any valid subarray.
The first line contains a single integer $$$T$$$ ($$$1 \le T \le 2 \cdot 10^5$$$) — the number of test cases.
Then $$$T$$$ test cases follow. Each test case consists of two lines:
The first line of each test case contains a single integer $$$N$$$ ($$$1 \le N \le 2 \cdot 10^5$$$) — the size of the array.
The second line contains $$$N$$$ integers $$$a_1, a_2, \dots, a_N$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$) — the elements of the array.
It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, print a single integer — the length of the longest valid subarray. If there is no such subarray, print $$$-1$$$.
1 5 2 4 6 9 3
3
3 2 6 12 6 6 9 15 21 27 33 5 5 10 15 20 25
-1 6 5
Explanation:
Test case 1:
The array is $$$[2, 4, 6, 9, 3]$$$. - The subarray $$$[6, 9, 3]$$$ has GCD $$$3$$$, which is a prime number. Its length is $$$3$$$, which is the maximum possible length among all valid subarrays.
Test case 2:
1. Array: $$$[6, 12]$$$ — GCD of any subarray is not prime. So the answer is $$$-1$$$. 2. Array: $$$[6, 9, 15, 21, 27, 33]$$$ — the entire array has GCD $$$3$$$, which is prime. Maximum length is $$$6$$$. 3. Array: $$$[5, 10, 15, 20, 25]$$$ — the entire array has GCD $$$5$$$, which is prime. Maximum length is $$$5$$$.
You will be given $$$T$$$ test cases.
In each test case, you are given a grid of size $$$N \times M$$$ containing integers. Your task is to choose exactly one number from each row so that the bitwise AND of all the chosen numbers is strictly greater than $$$0$$$.
Formally, you need to choose integers $$$c_1, c_2, \dots, c_{N}$$$ with $$$1 \le c_i \le M$$$ such that $$$$$$ a_{1,c_1} \;\&\; a_{2,c_2} \;\&\; \cdots \;\&\; a_{N,c_N} \; \gt \; 0, $$$$$$ where $$$a_{i,j}$$$ denotes the element in the $$$i$$$-th row and $$$j$$$-th column of the grid.
The first line contains a single integer $$$T$$$ ($$$1 \le T \le 2 \cdot 10^5$$$) — the number of test cases.
The first line of each test case contains two integers $$$N$$$ and $$$M$$$ — the number of rows and columns in the grid. Then follow $$$N$$$ lines, each containing $$$M$$$ integers — the elements of the grid $$$a_{i,j}$$$.
Constraints
$$$1 \le N, M \le 2 \cdot 10^5$$$
$$$0 \le a_{i,j} \le 10^{14}$$$
$$$1 \le \sum (N \cdot M) \le 2 \cdot 10^5$$$ over all test cases.
For each test case, print YES if it is possible to choose exactly one number from each row such that their bitwise AND is greater than $$$0$$$. Otherwise, print NO.
1 2 2 3 3 4 8
NO
1 2 3 3 5 8 4 1 16
YES
Test 1. The grid is:
We must choose one number from each row. Some possible pairs are: $$$(3,4) \Rightarrow 3 \& 4 = 0$$$ , $$$(3,8) \Rightarrow 3 \& 8 = 0$$$ . No matter how we choose, the bitwise AND is $$$0$$$. Hence the answer is NO.
3 3
4 8
Test 2. The grid is:
If we pick $$$5$$$ from the first row and $$$1$$$ from the second row, then $$$5 \& 1 = 1 \gt 0$$$. So a valid selection exists. Hence the answer is YES.
3 5 8
4 1 16
You are given an array $$$A$$$ of length $$$N$$$ (1-indexed). There are $$$Q$$$ operations, and the $$$i$$$-th operation is described by three integers $$$L$$$, $$$R$$$, $$$d$$$, meaning add the integer $$$d$$$ to every element $$$A[L], A[L+1], \dots, A[R]$$$. All $$$Q$$$ operations are applied to the array in the given order.
After all operations are applied, you must answer $$$M$$$ independent queries. Each query gives an integer $$$K$$$, and you should output the K-th largest value in the resulting array.
The first line contains three integers $$$N, Q, M$$$ $$$(1 \le N \le 2\times 10^5, \, 1 \le Q \le 2\times 10^5, \, 1 \le M \le 2\times 10^5)$$$ — the array length, the number of range updates, and the number of queries.
The second line contains $$$N$$$ integers $$$A_1, A_2, \ldots, A_N$$$ ($$$\lvert A_i \rvert \le 10^9$$$ for all $$$i$$$) — the initial array.
Each of the next $$$Q$$$ lines contains three integers $$$L, R, d$$$ $$$(1 \le L \le R \le N, \, -10^6 \le d \le 10^6)$$$ describing a range addition.
The next line contains $$$M$$$ integers $$$K_1, K_2, \ldots, K_M$$$ $$$(1 \le K_i \le N)$$$ — the queries.
All integers are separated by single spaces.
Print $$$M$$$ lines. On the $$$i$$$-th line, output a single integer — the $$$K_i$$$-th largest element of the array after all updates.
5 3 3 1 2 3 4 5 1 3 10 2 5 -4 5 5 100 1 2 5
101 11 0
There are $$$\mathbf{n}$$$ houses connected by $$$n - 1$$$ bidirectional roads, forming a tree. The houses are numbered from $$$1$$$ to $$$n$$$, and house $$$1$$$ is the root of the tree. Each house has an integer value $$$a_i$$$, which is called its house value.
You are given $$$q$$$ queries. In each query, you are given two houses $$$u$$$ and $$$v$$$. Your task is to determine whether the path from $$$u$$$ to $$$v$$$ is safe.
A path is considered safe if the product of all house values along the path from $$$u$$$ to $$$v$$$ is a perfect square.
A perfect square is a non-negative integer that can be expressed as the square of another integer (e.g., $$$0, 1, 4, 9, 16, 25, \ldots$$$). Negative numbers are not considered perfect squares.
The first line contains a single integer $$$n$$$ $$$(2 \leq n \leq 2 \times 10^5)$$$ — the number of houses.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-2 \times 10^5 \leq a_i \leq 2 \times 10^5$$$) — the value of the i-th house.
Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ $$$(1 \leq u, \,v \leq n, \, u \neq v)$$$ indicating a road between house $$$u$$$ and house $$$v$$$.
The next line contains an integer $$$q$$$ $$$(1 \leq q \leq 10^5)$$$ — the number of queries.
Each of the next $$$q$$$ lines contains two integers $$$x$$$ and $$$y$$$ $$$(1 \leq x, \, y \leq n)$$$ representing a query to check whether the path from house $$$x$$$ to house $$$y$$$ is safe or not.
In each query, print Yes if the path is safe; print No otherwise.
7 1 4 1 -2 4 -2 -2 1 2 1 3 2 4 2 5 3 6 3 7 3 6 7 4 5 2 5
Yes No Yes
- For $$$Query = 1$$$: The house value of the path from $$$6 \to 7$$$ are $$$\mathbf{-2, \, 1, \, -2}$$$ and product of them is $$$\mathbf{4}$$$. Which is a perfect square. So, the answer is Yes.
- For $$$Query = 2$$$: The house value of the path from $$$4 \to 5$$$ are $$$\mathbf{-2, \, 4, \, 4}$$$ and product of them is $$$\mathbf{-32}$$$. Which is not a perfect square. So, the answer is No.
- For $$$Query = 3$$$: The house value of the path from $$$2 \to 5$$$ are $$$\mathbf{4, \, 4}$$$ and product of them is $$$\mathbf{16}$$$. Which is a perfect square. So, the answer is Yes.
You are given a sequence of non-negative integers. Your task is to find its MEX.
The MEX (Minimum EXcluded number) of a sequence of non-negative integers is defined as the smallest non-negative integer that does not appear in the sequence.
The first line contains a single integer $$$T$$$ — the number of test cases.
Each test case consists of two lines:
- The first line contains a single integer $$$N$$$ — the size of the sequence.
- The second line contains $$$N$$$ integers $$$a_1, a_2, \ldots, a_N$$$ — the elements of the sequence.
$$$1 \leq T \leq 10^{5}$$$, $$$1 \leq N \leq 10^{5}$$$, $$$0 \leq a_i \leq 10^{9}$$$, $$$\sum N \text{ across all test cases} \leq 10^{6}$$$
For each test case, print a single integer — the MEX of the given sequence.
2 4 0 1 2 4 5 0 2 3 1 4
3 5
- For the first test case: The sequence is $$$[0, 1, 2, 4]$$$. The smallest non-negative integer not in the sequence is $$$\mathbf{3}$$$. Hence the MEX is $$$3$$$.
- For the second test case: The sequence is $$$[0, 2, 3, 1, 4]$$$. The smallest non-negative integer not in the sequence is $$$\mathbf{5}$$$. Hence the MEX is $$$5$$$.
Mr. Benzene wants permission to go on a bachelor trip, but his mathematician wife isn't convinced.
She says:
Solve this math problem first — or you're cleaning the room all week!"
Mr. Benzene must find the smallest non-negative integer $$$\mathbf{n}$$$ such that the number of ways to express $$$\mathbf{n}$$$ as the sum of exactly $$$\mathbf{k}$$$ non-negative integers is at least $$$\mathbf{m}$$$. If he fails, he faces a week of messy floors and dust bunnies.
The first line contains an integer $$$\textbf{T}$$$ $$$(1 \leq $$$T$$$ \leq 10^{5})$$$ the number of test cases.
Each of the next $$$T$$$ lines contains two integers $$$\textbf{k}$$$ and $$$\textbf{m}$$$ $$$(1 \leq $$$k$$$ ,\, $$$m$$$ \leq 10^{18})$$$.
For each test case, output Case $$$\mathbf{X: n}$$$, where $$$\mathbf{X}$$$ is the test case number (starting from 1) and $$$\mathbf{n}$$$ is the smallest integer that satisfies the condition, or $$$\mathbf{-1}$$$ if no such answer exists.
3 3 15 3 16 5 35
Case 1: 4 Case 2: 5 Case 3: 3
Consider the first test case: $$$\mathbf{k = 3}, \mathbf{m = 15}$$$. Iterative approach:
- For $$$n = 0$$$: Ways = $$$(0,0,0)$$$ $$$\to$$$ 1 way. Total ways = 1 $$$ \lt 15$$$.
- For $$$n = 1$$$: Ways = $$$(0,0,1), (0,1,0), (1,0,0)$$$ $$$\to$$$ 3 ways. Total ways = 3 $$$ \lt 15$$$.
- For $$$n = 2$$$: Ways = $$$(0,0,2),\, (0,1,1),\, (0,2,0),\, (1,0,1),\, (1,1,0),\, (2,0,0)$$$ $$$\to$$$ 6 ways. Total ways = 6 $$$ \lt 15$$$.
- For $$$n = 3$$$: Ways = $$$(0,0,3),\, (0,1,2),\, (0,2,1),\, (0,3,0),\, (1,0,2),\, (1,1,1),\, (1,2,0),\, (2,0,1), \\ (2,1,0), (3,0,0)$$$ $$$\to$$$ 10 ways. Total ways = 10 $$$ \lt 15$$$.
- For $$$n = 4$$$: Ways = $$$(0,0,4),\, (0,1,3),\, (0,2,2),\, (0,3,1),\, (0,4,0),\, (1,0,3),\, (1,1,2),\, (1,2,1), \\ (1,3,0),\, (2,0,2),\, (2,1,1),\, (2,2,0),\, (3,0,1),\, (3,1,0),\, (4,0,0)$$$ $$$\to$$$ 15 ways. Total ways = 15 $$$\ge 15$$$ (Condition met!).
So, the answer is $$$\mathbf{4}$$$.
Long ago, in a kingdom of words, there was a librarian who loved palindromes. Whenever she found a scroll of letters, she tried to cut it into pieces so that each piece could be rearranged into a palindrome. She called such magical pieces AnapalinDromes. For example, the piece "aabb" is an AnapalinDrome as it could be rearranged to "abba", which is a palindrome. Similarly, "a", "aa", and "aba" are AnapalinDromes.
Now she has given you a scroll written as a string $$$s$$$. Your task is to help her count the following:
- Consider all possible ways to partition the string into one or more contiguous substrings, such that every substring is an AnapalinDrome.
- The score of a partition is the number of substrings in it.
- You must find the sum of scores over all valid partitions.
Since the number can be large, output it modulo $$$10^9 + 7$$$.
The first line contains a single integer $$$t$$$ — the number of test cases. Each of the next $$$t$$$ lines contains a string $$$s$$$ consisting of lowercase English letters.
- $$$1 \le t \le 10^5$$$
- $$$1 \le |s| \le 10^5$$$
- The total length of all strings across all test cases does not exceed $$$10^5$$$.
- Strings consist of lowercase English letters only.
For each test case, print a single integer - the sum of scores of all valid partitions of the string, modulo $$$10^9 + 7$$$.
2 aab abc
6 3
- For $$$s = \texttt{aab}$$$: the valid partitions are:
- aab $$$\rightarrow$$$ score = 1
- aa | b $$$\rightarrow$$$ score = 2
- a | a | b $$$\rightarrow$$$ score = 3
- For $$$s = \texttt{abc}$$$: the only valid partition is a | b | c with score = 3.
You are given a tree with $$$n$$$ nodes numbered from $$$1$$$ to $$$n$$$. Each node $$$i$$$ has an integer value $$$a_i$$$. The tree is rooted at node $$$1$$$.
You will receive $$$q$$$ queries. In the $$$i$$$-th query, you are given two integers $$$u_{\text{input}}$$$ and $$$v_{\text{input}}$$$. Your task is to determine the number of nodes $$$x$$$ satisfying:
- $$$x$$$ is an ancestor of both $$$u$$$ and $$$v$$$ (a node is considered an ancestor of itself).
- $$$\gcd(a_x, a_u) = 1$$$ and $$$\gcd(a_x, a_v) = 1$$$.
The queries are encrypted. The actual nodes for the $$$i$$$-th query are computed as:
$$$u = u_{\text{input}} \oplus \text{last}, \quad v = v_{\text{input}} \oplus \text{last},$$$
where $$$\text{last}$$$ is the answer to the previous query (assume $$$\text{last} = 0$$$ for the first query).
The first line contains an integer $$$n$$$ — the number of nodes.
The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ — the values of the nodes.
Each of the next $$$n-1$$$ lines contains two integers $$$x, y$$$, denoting an edge of the tree.
The next line contains an integer $$$q$$$ — the number of queries.
Each of the following $$$q$$$ lines contains two integers $$$u_{\text{input}}, v_{\text{input}}$$$.
Constraints
- $$$1 \le n \le 5 \times 10^4$$$
- $$$1 \le a_i \le 5 \times 10^4$$$
- $$$1 \le x, y, u, v \le n$$$
- $$$1 \le q \le 5 \times 10^4$$$
Print $$$q$$$ integers, each on its own line — the answer to each query.
5 2 3 6 5 7 1 2 1 3 3 4 3 5 3 2 4 4 5 3 3
1 2 0
- Query 1: $$$u = 2 \oplus 0 = 2$$$, $$$v = 4 \oplus 0 = 4$$$. Common ancestors = $$$\{1\}$$$. Node 1 has value 2, coprime with both 3 and 5. Answer = 1.
- Query 2: $$$u = 4 \oplus 1 = 5$$$, $$$v = 5 \oplus 1 = 4$$$. Common ancestors = $$$\{1,3\}$$$. Node 1 (value 2) coprime with 5 and 7, Node 3 (value 6) coprime with 5 and 7. Answer = 2.
- Query 3: $$$u = 3 \oplus 2 = 1$$$, $$$v = 3 \oplus 2 = 1$$$. Answer = 0.
We, the organizers of Comilla University (CoU), have always nurtured the spirit of competitive programming. Every year, we try to host IUPCs, celebrating teamwork, logic, and innovation.
However, we have long carried a bigger dream: to host a national level IUPC with top-notch facilities. The limitation of our current infrastructure has held us back, as we cannot yet welcome contestants from all over the country.
The new campus of CoU is under construction, and we eagerly await its completion. We are hoping to organize the national-level IUPC in the next year. With new halls and facilities, we are excited to finally bring our dream to life and host a national-level celebration of programming.
For now, your task is simple — print the line that expresses our excitement and dream.
There is no input for this problem.
Print the following exact line:
We want national level IUPC in CoU
no input
We want national level IUPC in CoU