Theme NexT works best with JavaScript enabled

## A - String

### 题目描述

A string is perfect if it has the smallest lexicographical ordering among its cyclic rotations.

For example: 0101 is perfect as it is the smallest string among (0101, 1010, 0101, 1010).

Given a 01 string, you need to split it into the least parts and all parts are perfect.

### 输入描述

The first line of the input gives the number of test cases, $T\ (T \leq 300)$ . $T$ test cases follow.

For each test case, the only line contains one non-empty 01 string. The length of string is not exceed $200$ .

### 输出描述

For each test case, output one string separated by a space.

### 题解

#### 解法

$n$ 不超过 $200$ ，暴力做即可。

## B - Irreducible Polynomial

### 题目描述

In mathematics, a polynomial is an expression consisting of variables (also called indeterminate) and coefficients, that involves only the operations of addition, subtraction, multiplication, and non-negative integer exponents of variables. For example, $x^2 + 4x + 7$ .

A polynomial is said to be irreducible if it cannot be factored into two or more non-trivial polynomials with real coefficients.

For example, $x^2+1$ is irreducible, but $x^2-2x+1$ is not (since $x^2-2x+1=(x-1)(x-1)$ .

Given a polynomial of degree $n$ with integer coefficients: $a_nx^n+a_{n-1}x^{n-1}+…+a_1x+a_0$ , you need to check whether it is irreducible or not.

### 输入描述

The first line of the input gives the number of test cases, $T\ (T \leq 100)$ . $T$ test cases follow.

For each test case, the first line contains one integers $n (0 \leq n \leq 20)$ . Next line contains $n + 1$ integer numbers $a_n, a_{n-1}, …, a_1, a_0$

• $-10^9 \leq a_i \leq 10^9$
• $a_n \ne 0$

### 输出描述

For each test case, output Yes if it is irreducible, otherwise No.

## C - Governing sand

### 题目描述

The Wow village is often hit by wind and sand,the sandstorm seriously hindered the economic development of the Wow village.

There is a forest in front of the Wowo village, this forest can prevent the invasion of wind and sand. But there is a rule that the number of tallest trees in the forest should be more than half of all trees, so that it can prevent the invasion of wind and sand. Cutting down a tree need to cost a certain amount of money. Different kinds of trees cost different amounts of money. Wow village is also poor.

There are n kinds of trees. The number of i-th kind of trees is $P_i$ , the height of i-th kind of trees is $H_i$ , the cost of cutting down one i-th kind of trees is $C_i$ .

(Note: “cutting down a tree” means removing the tree from the forest, you can not cut the tree into another height.)

### 输入描述

The problem is multiple inputs (no more than 30 groups).

For each test case.

The first line contines one positive integers $n (1 \leq n \leq 10^5)$ ,the kinds of trees.

Then followed $n$ lines with each line three integers $H_i (1 \leq H_i \leq 10^9)$ -the height of each tree, $C_i (1 \leq C_i \leq 200)$ -the cost of cutting down each tree, and $P_i(1 \leq P_i\leq 10^9)$ -the number of the tree.

### 输出描述

For each test case, you should output the minimum cost.

## D - Number

### 题目描述

I have a very simple problem for you. Given a positive integeter $n (1 \leq n \leq 1000000)$ and a prime number $p(2 \leq p \leq 1000000)$ , your job is to output a positive number which is divisible by $P$ and has exactly $n$ digits. Please output T_T if you can not find such number.

### 输入描述

The first line of the input file contains two integers $n (1 \leq n \leq 1000000)$ and $p (2 \leq p \leq 1000000)$ . $p$ is a prime number.

### 输出描述

Output one number (without leading zeros) or T_T

## E - Find the median

### 题目描述

Let median of some array be the number which would stand in the middle of this array if it was sorted beforehand. If the array has even length let median be smallest of of two middle elements. For example, median of the array $[10,3,2,3,2]$ is $3 (i.e. [2,2,\underline{3},3,10])$ . Median of the array $[1,5,8,1]$ is $1 (i.e.[1,\underline{1},5,8])$ .

At first, you’re given an empty sequence. There are $N$ operations. The i-th operation contains two integers $L_i$ and $R_i$ . This means that adding $R_i-L_i+1$ integers $L_i, L_i+1, … , R_i$ into the sequence. After each operation, you need to find the median of the sequence.

### 输入描述

The first line of the input contains an integer $N (1 \leq N \leq 400000)$ as described above.

The next two lines each contains six integers in the following format, respectively:

$-$ $X_1\ X_2\ A_1\ B_1\ C_1\ M_1$
$-$ $Y_1\ Y_2\ A_2\ B_2\ C_2\ M_2$

These values are used to generate $L_i, R_i$ as follows:

We define:
$-$ $X_i = (A_1 \times X_{i-1} + B_1 \times X_{i-2} + C_1)\ module\ M_1$ , for $i = 3\ to\ N$
$-$ $Y_i = (A_2 \times Y_{i-1} + B_2 \times Y_{i-2} + C_2)\ module\ M_2$ , for $i = 3\ to\ N$

We also define:
$-$ $L_i = min(X_i, Y_i) + 1$ , for $i = 1\ to\ N$ .
$-$ $R_i = max(X_i, Y_i) + 1$ , for $i = 1\ to\ N$ .

Limits:
$1 \leq N \leq 400000$

$0 \leq A_1 < M_1$

$0 \leq A_2 < M_2$

$0 \leq B_1 < M_1$

$0 \leq B_2 < M_2$

$0 \leq C_1 < M_1$

$0 \leq C_2 < M_2$

$0 \leq X_1 < M_1$

$0 \leq X_2 < M_1$

$0 \leq Y_1 < M_2$

$0 \leq Y_2 < M_2$

$1 \leq M_1 \leq 10^9$

$1 \leq M_2 \leq 10^9$

### 输出描述

You should output $n$ lines. Each line contains an integer means the median.

### 示例1

#### 说明

$L = [3, 2 ,4, 1, 7]$

$R = [4, 8, 8, 3, 9]$

## F - Energy stones

### 题目描述

CNZ lives in the forest, and he has $N$ energy stones, numbered from $1$ to $N$ .

CNZ need to eat energy generated by energy stones.

The $i$ -th energy stone initially contains $E_i$ units of energy and will increase $L_i$ units of energy each second.

The maximum energy of $i$ -th energy stone is $C_i$ , the stone’s energy stops increasing once it reach $C_i$ .

Each time he absorbs the energy of a continuous interval of stone. For example, if CNZ absorbs the energy of $[S, T]$ stones, all energy stones numbered from $S$ to $T$ will become zero units of energy. CNZ can get the sum of energy in this range.

CNZ will eat $M$ times. The i-th eating happens after $t_i$ seconds, and eat interval is $[S_i, T_i].$

What’s the total amount of energy CNZ has eaten after $M$ eating.

### 输入描述

The first line of the input gives the number of test cases, $T (T \leq 20)$ . $T$ test cases follow.

Each test case starts with a line containing the integer $N\ (1 \leq N \leq 10^5)$ , the number of energy stones .

Then, there are $N$ more lines, the i-th of which contains the three integers $E_i$ , $L_i$ and $C_i$ as described above.

The next line contains one integer $M$ .

Then, there are $M$ more lines, the $i$ -th of which contains the three integers $t_i$ , $S_i$ and $T_i$ as described above.

Limits:

• $1 \leq N \leq 10^5$
• $0 \leq E_i \leq C_i \leq 10^6$
• $0 \leq L_i \leq 10^6$
• $0 < M \leq 10^5$
• $0 < t_i \leq 2 \times 10^5$
• $t_{i-1} < t_i$
• $1 \leq S_i \leq T_i \leq N$

### 输出描述

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from $1$ ) and $y$ is the result.

## G - Make Shan Happy

### 题目描述

Shan is a kind of fish and looks very beautiful in dress.

There is a tree whose root is 1. Every node i in this tree owns a weight $W_i$ , satisfying that if $x$ is an ancestor of $y$ then $W[x] \le W[y]$ .

Shan have several questions, each question can be represented as a pair(x,k), Shan wants to find the biggest node y such that $y - k \le W[lca(x,y)]$ .

Shan is not happy today, can you help her to answer these questions?

### 输入描述

First line two integers: $n(\le 10^5)$ and $m(\le 10^5)$

Second line $n$ integers, the $i_{th}$ integer represents $Wi$

Next $n-1$ lines, two integers each line u and v meaning that there an edge between $u$ and $v$ .

Next $m$ lines, two integers each line $x (1 \le x \le n)$ and $k( -10^6 \le k \le 10^6)$ representing a question.

### 输出描述

$m$ lines. One integer each line, $i_{th}$ integer represents the answer to $i_{th}$ question, and output $0$ if there is no such node.

## H - Pair

### 题目描述

Given three integers $A$ , $B$ , $C$ .Count the number of pairs < $x\ , y$ > (with $1 \leq x \leq A$ and $1 \leq y \leq B$ )

such that at least one of the following is true:

• ( $x\ and\ y$ ) > $C$
• ( $x\ xor\ y$ ) < $C$

(“and”, “xor” are bit operators)

### 输入描述

The first line of the input gives the number of test cases, $T\ (T \leq 100)$ . $T$ test cases follow.

For each test case, the only line contains three integers $A$ , $B$ and $C$ . $1 \leq A,B,C \leq 10^9$

### 输出描述

For each test case, the only line contains an integer that is the number of pairs satisfying the condition given in the problem statement.

## I - Chessboard

### 题目描述

CSL likes playing tricks very much. The unlucky TL always becomes the target of CSL’s tricks.

Today CSL came to trick TL again. He saw that TL has a very very large checkerboard and many glass balls. So he have an idea. He said to TL:

“What a big chessboard you have… How about play a game with me ? I will give you $N$ and $M$ ,and you can choose an arbitrarily large square area on the chessboard (assuming you choose a $k \times k$ square area) and place a number of glass balls on each of the squares (each square should place not less than $M$ glass balls). Your placement needs to be satisfied:

If we choose $k$ squares of different rows and columns, then no matter how we choose, the total number of glass balls in this $k$ squares should always be the same, and should not greater then $N$ .

You just need to tell me how many ways you have to satisfy this. If you can’t tell me, the chessboard and glass balls will all belong to me ！

TL doesn’t want to give the chessboard and glass ball to CSL, but he knows that the clever CSL has already worked out the answer in his mind. Can you help him solve this problem?

### 输入描述

The first line of the input is a single integer $T (T \leq 5)$ indicating the number of test cases.

Each of the following $T$ lines contains $2$ integers $N$ and $M$ (meaning as description)

$T \leq 5$ , $1 \leq n,m \leq 2000$

### 输出描述

For each test case, output the answer in a single line. because the answer may be very big, so just print the result after mod $998244353$

### 示例1

#### 备注 ### 题解

#### 解法

• 设 $Ai$ 为第 $i$ 行全为 $1$ ，其它位置全为 $0$ 的方阵。
• 设 $Bj$ 为第 $j$ 列全为 $1$ ，其它位置全为 $0$ 的方阵。
• 一个 $k$ 行 $k$ 列，任取 $k$ 个元素，每个元素不同行不同列的方阵，一定可以由 $\{A1,A2,….,B1,B2…..\}$ 的生成的线性空间中。也就是 $\sum_{i=1}^ka_iA_i+\sum_{j=1}^kb_jB_k$
• 于是有 $\sum_{i=1}^ka_i+\sum_{j=1}^kb_j \geq n$
• 但很可惜，如上线性空间的基中只有 $2k−1$ 个向量，因此表出方式不唯一。
• 对于不同的表出方式，令 $d=\min_{i=1}^ka_i$ 做变换 $ai:=ai−d$ , $bi:=bi+d$ ，于是我们识破了本质相同的矩阵的不同表出方式。
• 对于一个确定的 $k$ ，答案为 $\sum_{i=1}^ka_i+\sum_{j=1}^kb_j \leq n$ (存在 $a_i=0$ )
• 枚举 $k$ ，用 $\sum_{i=1}^ka_i+\sum_{j=1}^kb_j≤n$ ,( $a_i,b_j \geq 0$ ) 的解数，减去 $\sum_{i=1}^ka_i+\sum_{j=1}^kb_j \leq n$ ,( $b_j \geq 0,ai \geq 1$ ) 的解数即可，复杂度 $\mathcal{O}(n)$

## J - A+B problem

### 题目描述

Reversed number is a number written in arabic numerals but the order of digits is reversed. The first digit becomes last and vice versa. And all the leading zeros are omitted.

For example: the reversed number of $1234$ is $4321$ . The reversed number of $1000$ is $1$ .

We define reversed number of $x$ as $f(x)$ . Given you two positive integers $A$ and $B$ , you need to calculate the reversed sum: $f(f(A)+f(B))$ .

### 输入描述

The first line of the input gives the number of test cases, $T\ (T \leq 300)$ . $T$ test cases follow.

For each test case, the only line contains two positive integers: $A$ and $B$ . ( $1 \leq A, B \leq 2^{31}-1$ )

### 输出描述

For each test case, output a single line indicates the reversed sum.

### 题解

#### 题意

$f(x)$ 被定义为反转数字 $x$ ,并去除前导零之后的数，输入两个数 $x,y$ ,询问 $f(f(A)+f(B))$ 。

## K - Function

### 题目描述

CSL likes to study various functions. Recently, he became fascinated with a new function. He named it $CSL$ function. Its expression is as follows:

CSL(p,x) = 3log_{p}x + 1

Where p is a prime number. But CSL doesn’t like floating point numbers and even numbers, nevertheless, he likes square numbers very much, so he decided to add some restrictions to his $CSL$ functions:

1. if $CSL(p,x)$ is not integer，then let $CSL(p,x)=0$
2. if $CSL(p,x)$ is integer，but $p$ is $2$ or $p$ can’t be expressed as the sum of two squares（which means: $\nexists a,b \in N^+,s.t. \ a^2+b^2=p$ ）,then let $CSL(p,x)=1$

TL saw the function of $CSL$ . He thought it was not interesting enough, so he also defined a $tl$ function:

tl(p,x)=max_{d|x}(CSL(p,d))

Where p is a prime number too. $TL$ asked $CSL$ proudly: I will give you an $x$ , Could you calculate $\sum_{d|x}\prod_{p}tl(p,d)$ (in which $p$ passing through all the prime numbers)?

$CSL$ thought about it and told $TL$ the answer quickly. and he asked $TL$ ：so if I give you a $n$ , Could you calculate $\sum_{d=1}^{n}\prod_{p}tl(p,d)$ ?

$TL$ can’t do this, so he turned up to you for help.

### 输入描述

The first line of the input is a single integer $T (T \leq 5)$ indicating the number of test cases.

Each of the following $T$ lines contains one integer $n$ (meaning as description)

$T \leq 5$

$n \leq 10^{9}$