Just something trivial

## A - digits 2

### 题目描述

You are given a positive integer $n$ which is at most $100$ .

Please find a positive integer satisfying the following conditions:

1. The sum of all digits of this number is dividable by $n$ .
2. This number is also dividable by $n$ .
3. This number contains no more than $10^4$ digits.

If such an integer doesn’t exist, output Impossible (without quotation marks).

If there are multiple such integers, please output any one.

### 输入描述

The first line contains one integer $T$ indicating that there are $T$ tests.

Each test consists an integer $n$ in a single line.

• $1 \le T \le 100$

• $1 \le n \le 100$

### 输出描述

For each query, output one line containing the answer. The number you print cannot have leading zeros. If there are multiple answers, you can print any. If such an integer doesn’t exist, output Impossible (without quotation marks) in a single line.

### 示例1

#### 说明

For the last test, $888$ is dividable by $12$ $(888 = 12 \times 74)$ and $8 + 8 + 8 = 24$ is also dividable by $12$ $(24 = 12 \times 2)$ .

## B - generator 1

### 题目描述

You are given four positive integers $x_0, x_1, a, b$ . And you know $x_i = a \cdot x_{i-1} + b \cdot x_{i-2}$ for all $i \ge 2$ .

Given two positive integers $n$ , and $MOD$ , please calculate $x_n$ modulo $MOD$ .

Does the problem look simple? Surprise! The value of $n$ may have many many digits!

### 输入描述

The input contains two lines.

The first line contains four integers $x_0, x_1, a, b$ $1 \le x_0, x_1, a, b \le 10^9$ .

The second line contains two integers $n$ , $MOD$ ( $1 \le n < 10^{(10^6)}$ , $10^9 < MOD \le 2 \times 10^9$ , $n$ has no leading zero).

### 输出描述

Print one integer representing the answer.

### 示例1

#### 说明

The resulting sequence $x$ is Fibonacci sequence. The $11$ -th item is $89$ .

## C - generator 2

### 题目描述

There is a sequence of length $n$ : $x_0, x_1, x_2, \ldots, x_{n-1}$ . Please answer Q queries. Each query consists of one integer v, asking the minimum index $i$ such that $x_i = v$ . If the sequence doesn’t have any number with value $v$ , you only need to output $-1$ .

Does the problem look simple? Surprise! The value of n may be as large as $10^{18}$ !

Because $n$ is so large. We will only give you four integers $x_0, a, b, p$ to generate the sequence. For all $i>0$ , the sequence is generated as $x_i = (a \cdot x_{i-1} + b) \mod p$ .

### 输入描述

The first line of input contains an integer $T$ ( $T \le 4$ ) denoting there are $T$ tests in the input.

Each test contains $Q+2$ lines.

The first line of each test contains five integers $n, x_0, a, b, p$ ( $1 \le n \le 10^{18}, 0 \le x_p,a,b < p \le 10^9 + 9$ , $p$ is a prime number).

The second line contains one integer $Q$ ( $Q \le 1000$ ).

Each of the following $Q$ lines contains one integer $v$ ( $0 \le v < p$ ).

### 输出描述

For each query, print one integer as the answer in one line.

### 示例1

#### 说明

For the first test, the sequence looks like $1, 2, 3, \dots, 1000000008, 0$ . So the position of the first occurrence of value $v$ is $v - 1$ except for value $0$ which occurs at $1000000008$ .

## D - generator 3

### 题目描述

Here is another simple problem: Given n points in the $2$ -dimensional plane, please calculate the area of the convex hull.

However, as you might already have guessed, the value of $n$ is very large! So you’ll use the following generator to generate all those points:

You are given nine integers $x_0, y_0, a_x, a_y, b_x, b_y, p_x, p_y, n$ .

There are two recursive equations: $x_i= (a_x \times x_{i-1} + b_x) \mod p_x$ and $y_i= (a_y \times y_{i-1} + b_y) \mod p_y$ for all $0 < i < n$ .

The given n points are $(x_i, y_i)$ for $0 \le i < n$ .

### 输入描述

The input consists of only one line.

This line contains nine integers in the following order: $x_0, y_0, a_x, a_y, b_x, b_y, p_x, p_y, n$ .

• $0 \le x_0, a_x, b_x < p_x < 2 \times 10^5$

• $0 \le y_0, a_y, b_y < p_y < 2 \times 10^5$

• $3 \le n \le 10^{18}$

• There may be multiple points in the same position

### 输出描述

Please output one integer denoting the area of the convex hull (of the generated n points) multiplied by $2$ .

It can be proved that two times such area is always an integer.

## E - independent set 1

### 题目描述

Note:For C++ languages, the memory limit is 100 MB. For other languages, the memory limit is 200 MB.

In graph theory, an independent set is a set of nonadjacent vertices in a graph. Moreover, an independent set is maximum if it has the maximum cardinality (in this case, the number of vertices) across all independent sets in a graph.

An induced subgraph $G’(V’, E’)$ of a graph $G(V, E)$ is a graph that satisfies:

• $V’ \subseteq V$ .
• edge $(a,b) \in E’$ if ans only if $a \in V’, b \in V’$ ans edge $(a, b) \in E$ .

Now, given an undirected unweighted graph consisting of $n$ vertices and $m$ edges. This problem is about the cardinality of the maximum independent set of each of the $2^n$ possible induced subgraphs of the given graph. Please calculate the sum of the $2^n$ such cardinalities.

### 输入描述

The first line contains two integers $n$ and $m$ ( $2 \le n \le 26, 0 \le m \le \frac{n \times (n-1)}{2}$ ) —- the number of vertices and the number of edges, respectively. Next m lines describe edges: the i-th line contains two integers $x_i, y_i$ ( $0 \le x_i < y_i < n$ ) —- the indices (numbered from $0$ to $n - 1$ ) of vertices connected by the $i$ -th edge.

The graph does not have any self-loops or multiple edges.

### 输出描述

Print one line, containing one integer represents the answer.

### 示例1

#### 说明

The cardinalities of the maximum independent set of every subset of vertices are: {}: 0, {0}: 1, {1}: 1, {2}: 1, {0, 1}: 1, {0, 2}: 1, {1, 2}: 2, {0, 1, 2}: 2 . So the sum of them are $9$ .

## F - maximum clique 1

### 题目描述

You are given a set $S$ containing $n$ distinct positive integers $a_1, a_2, \ldots, a_n$ .

Please find a subset of $S$ which has the maximum size while satisfying the following constraint:

The binary representations of any two numbers in this subset must have at least two different bits.

If there are multiple valid subsets, please output any one of them.

### 输入描述

The input contains only two lines.

The first line contains an integer $N$ denoting the size of $S$ .

The second line contains $N$ positive integers $a_1, a_2, \ldots, a_N$ denoting the members of set $S$ .

• $1 \le N \le 5000$

• $1 \le a_i \le 10^9$

• all $a_i$ are distinct

### 输出描述

You should output two lines.

The first line contains one integer $m$ denoting the size of the subset you found.

The second line contains m positive integers denoting the member of this subset.

### 示例1

#### 说明

$3 (112)$ and $1 (012)$ has only $1$ different bit so they can not be in the set together. $4 (1002)$ and $1 (0012)$ has $2$ different bits so they can be in the set together.

Following unordered pairs are allowed to be in the set together: $<1, 2>, <1, 4>, <2, 4>, <2, 5>, <3, 4>, <3, 5>$ . Thus the maximum set is of size $3 ({1, 2, 4})$ .

## G - subsequence 1

### 题目描述

You are given two strings s and t composed by digits (characters 0 $\sim$ 9). The length of s is n and the length of t is m. The first character of both s and t aren’t 0.

Please calculate the number of valid subsequences of s that are larger than t if viewed as positive integers. A subsequence is valid if and only if its first character is not 0.

Two subsequences are different if they are composed of different locations in the original string. For example, string 1223 has $2$ different subsequences 23.

### 输入描述

The first line contains one integer $T$ , indicating that there are $T$ tests.

Each test consists of $3$ lines.

The first line of each test contains two integers $n$ and $m$ , denoting the length of strings $s$ and $t$ .

The second line of each test contains the string $s$ .

The third line of each test contains the string $t$ .

• $1 \le m \le n \le 3000$

• sum of $n$ in all tests $\le 3000$ .

• the first character of both $s$ and $t$ aren’t 0.

### 输出描述

For each test, output one integer in a line representing the answer modulo 998244353.

### 示例1

#### 说明

For the last test, there are $6$ subsequences 11, $4$ subsequcnes 111 and $1$ subsequence 1111 that are valid, so the answer is 11.

DP+排列组合强行推（X

## H - subsequence 2

### 题目描述

There is a hidden string of length $n$ composed of the first $m$ lowercase English letters. For any two different English letters, we will tell you a subsequence of the hidden string constructed by removing all other letters from the hidden string.

For example, if the hidden string is apple and the chosen letters are e and p, the resulting subsequence would be ppe; if the chosen letters are a and x, the resulting subsequence would be a.

Now, please recover the hidden string. Output -1 if there are no possible hidden string. Output any one if there are multiple possible hidden strings.

### 输入描述

The first line contains two integers $n$ and $m$ .

Following are $\dfrac{m \times (m-1)}{2}$ groups of two lines. The first line in each group contains a two-letter string composed of $c1, c2$ , and an integer $LEN$ . The second line contains a string composed of letters $c1, c2$ with length $LEN$ , indicates the resulting subsequence by removing all other letters except $c1$ and $c2$ from the hidden string.

• $1 \le n \le 10^4$

• $2 \le m \le 10$

• $0 \le LEN \le n$

• all unordered pairs of letters in first m small English letters will occur exactly once.

### 输出描述

If there is at least one possible hidden string, please output any. Otherwise, output -1.

### 题解

#### 题意

• $c1、c2、len$ ：表示除去其他非 $c1、c2$ 之外的字母剩下的串长度为 $len$
• $s$ ：除去其他非 $c1、c2$ 之外的字母剩下的字符串，长度为 $len$

## I - three points 1

### 题目描述

You are given five positive integers $w, h, a, b, c$ . Please construct $3$ points $X, Y, Z$ in the $2$ -dimensional plane such that the distance between $X$ and $Y$ is $a$ the distance between $X$ and $Z$ is $b$ , the distance between $Y$ and $Z$ is $c$ . Furthermore, the $x$ coordinates of all constructed points must be in the range $[0, w]$ , and the $y$ coordinates of all constructed points must be in the range $[0,h]$ .

The value of the constructed coordinates $X, Y, Z$ can be real numbers. The input guarantees that at least one solution exists.

### 输入描述

The first line contains an integer $T$ indicating there are $T$ tests.

Each test consists of a single line containing five integers: $w, h, a, b, c$ .

$1 \le w, h, a, b, c \le 50$

$1 \le T \le 5 \times 10^4$

### 输出描述

For each test, output one line containing six numbers, the first two numbers are the coordinate of $X$ , the third and fourth numbers are the coordinate of $Y$ , the last two numbers are the coordinate of $Z$ . If there are multiple solutions, please output any one.

All absolute error within $1e^{-6}$ will be ignored.

### 示例1

#### 说明

For the last test, the distance between $(1, 0)$ and $(0, 0)$ is $1$ , the distance between $(1, 0)$ and $(3, 0)$ is $2$ , and the distance between $(0, 0)$ and $(3, 0)$ is $3$ .

## J - three points 2

### 题目描述

Here is an unweighted tree (Graph theorem literature) with $n$ vertices along with $Q$ queries. Each query consists of three integers $a, b, c$ . Please find three vertices $X, Y, Z$ such that the distance between $X$ and $Y$ is $a$ , the distance between $X$ and $Z$ is $b$ , and the distance between $Y$ and $Z$ is $c$ .

The distance of two vertices is the number of edges in the simple path between them.

### 输入描述

The first line of input contains an integer n denoting the number of vertices.

The $i$ -th line of the following $n-1$ lines contains two integers $x_i, y_i$ denoting an edge connecting vertex $x_i$ and vertex $y_i$ (vertices are numbered from $0$ to $n-1$ ).

The $(n+1)$ -th line contains an integer $Q$ denoting the number of queries.

The following $Q$ lines each contains a query represented by three positive integers $a, b, c$ .

• $3 \le n, Q \le 2 \times 10^5$

• $1 \le a,b,c \le n-1$

### 输出描述

For each query, if there exist three vertices $X, Y, Z$ satisfying that the distance between $X$ and $Y$ is $a$ , the distance between $X$ and $Z$ is $b$ , and the distance between $Y$ and $Z$ is $c$ , output one line containing three numbers indicating the index of $X, Y$ , and $Z$ . If there is no solution, please output only one integer -1 in a line. If there are multiple solutions, output any one.

### 示例1

#### 说明

For the first test, the simple path between $0$ and $2$ is $0-1-2$ , the simple path between $0$ and $3$ is $0-1-3$ , and the simple path between $2$ and $3$ is $2-1-3$ . All of them have a distance of $2$ .