Just some trivial

## A - Garbage Classification

### 题目描述

On the CVBB planet, garbage classification has been gradually executed to help save resources and protect the environment. Nowadays people have to be equipped with knowledge of distinguishing different types of garbage. Now, given the waste compositions of a discarded product, you are asked to determine which category it belongs to.

The waste compositions are represented as a string s consisting of only lowercase letters, where each letter represents a waste composition and has an equal proportion. Each waste composition in that product is in one of the three situations, dry, wet or harmful.

The product can be classified by the following rules:

• In case that at least 25% of its compositions is harmful, it is harmful garbage.
• In case that at most 10% of its compositions is harmful, it is recyclable garbage.
• In other cases, if the proportion of dry compositions in it is at least twice that of wet compositions, it is dry garbage, or otherwise, it is wet garbage.

### 输入描述

There are multiple test cases. The first line contains an integer T ( $1 \leq T \leq 50$ ), indicating the number of test cases. Test cases are given in the following.

For each test case, the first line contains a non-empty string $s$ ( $1 \le |s| \le 2000$ ) consisting of only lowercase letters.

The second line contains a string t of length 26, consisting of only characters in $\lbrace d, w, h \rbrace$ . The i-th character of t represents the situation of the waste composition denoted by the i-th lowercase letter, where d, w and h mean dry, wet or harmful respectively.

### 输出描述

For each test case, output Case #x: y in one line (without quotes), where $x$ indicates the case number starting from $1$ , and $y$ ( $y \in \lbrace \text{Harmful}, \text{Recyclable}, \text{Dry}, \text{Wet} \rbrace$ ) denotes the garbage type of the product in this test case.

### 题解

#### 题意

• 如果其中至少25%的成分是有害的，那就是有害垃圾。
• 如果它的成分中有10%以上是有害的，那么它就是可回收垃圾。
• 在其他情况下，如果干成分的比例至少是湿成分的两倍，则为干垃圾，否则为湿垃圾。

## B - Shorten IPv6 Address

### 题目描述

You are given an IPv6 address which is a 128-bit binary string. Please determine its shortest representation according to the following rules :

Express the address in hexadecimal representation and use a colon ‘:’ to split every four hex digits. Every four digits are called a field. For example, 0000:0000:0123:4567:89ab:0000:0000:0000.

Leading zeros in a field can be omitted. For example, the above IPv6 address can be shortened to 0:0:123:4567:89ab:0:0:0.

Consecutive zero fields (with colons near them) consisting of at least two fields can be replaced by a double colon ‘::’. Besides, no more than one double colon can be used in an address. For example, the above IPv6 address can be shortened to 0:0:123:4567:89ab:: or ::123:4567:89ab:0:0:0, but not ::123:4567:89ab::.

If there are multiple shortest forms of the same length, use the lexicographically (regard the shorten IPv6 address as string) smallest one.

If the above rules conflict with rules in the real world, please refer to the rules mentioned in this problem.

### 输入描述

There are multiple test cases. The first line contains an integer $T$ ( $1 \leq T \leq 1000$ ), indicating the number of test cases. Test cases are given in the following.

Each test case consists of only one line, containing a 128-bit binary string.

### 输出描述

For each test case, output Case #x: y in one line (without quotes), where x indicates the case number starting from 1, and y denotes the answer to this test case.

## C - Palindrome Mouse

### 题目描述

Doctor has a string s consisting of only lowercase letters. Doctor has got the set of all palindromic substrings of a string s, denoted by the set S. Now, he wants to choose two distinct strings a and b from the set S which satisfy that the string a is a substring of the string b. How many different pairs (a, b) can Doctor choose?

### 输入描述

There are multiple test cases. The first line contains an integer T ( $1 \leq T \leq 5$ ), indicating the number of test cases. Test cases are given in the following.

Each test case consists of only one line, containing a non-empty string s ( $1 \leq |s| \leq 100000$ ), consisting of only lowercase letters.

### 输出描述

For each test case, output Case #x: y in one line (without quotes), where x indicates the case number starting from 1, and y denotes the answer to this test case.

### 题解

#### 解法

• next链：除奇根偶根，所有父亲都是儿子的子串。
• fail链：父亲是儿子的后缀，所以除奇根偶根所有父亲都是儿子的子串。

## D - Move

### 题目描述

After the struggle of graduating from college, TangTang is about to move from a student apartment to his new home.

TangTang has n items to move, the i-th of which is of volume viv_ivi​. He can pack all these items into at most K boxes of the same volume.

TangTang is so clever that he uses the following strategies for packing items:

• Each time, he would put items into a box by the next strategy, and then he would try to fill another box.
• For each box, he would put an unpacked item of the largest suitable volume into the box repeatedly until there is no such item that can be fitted in the box.

Now, the question is what is the minimum volume of these boxes required to pack all items.

### 输入描述

There are multiple test cases. The first line contains an integer $T$ ( $1 \leq T \leq 20$ ), indicating the number of test cases. Test cases are given in the following.

For each test case, the first line contains two integers $n, K$ ( $1 \leq n, K \leq 1000$ ), representing the number of items and the number of boxes respectively.

The second line contains n integers $v_1$ , $v_2$ , $\ldots$ , $v_n$ ( $1 \leq v_1, v_2, \ldots, v_n \leq 1000$ ), where the i-th integer viv_ivi represents the volume of the i-th item.

### 输出描述

For each test case, output Case #x: y in one line (without quotes), where x indicates the case number starting from 1, and y denotes the answer to this test case.

## E - Androgynos

### 题目描述

In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H. The complement of a graph G is a graph H on the same vertices such that two distinct vertices of H are adjacent if and only if they are not adjacent in G.

Give a positive integer n, check whether there exists a simple undirected graph G having n vertices, which is isomorphic to its complement graph H. If the graphs G and H exist, report them with any possible isomorphism.

### 输入描述

There are multiple test cases. The first line contains an integer $T$ ( $1 \leq T \leq 5$ ), indicating the number of test cases. Test cases are given in the following.

Each test case consists of only one line, containing an integer $n$ ( $1 \leq n \leq 2000$ ).

### 输出描述

For each test case, output Case #x: y in one line (without quotes), where $x$ indicates the case number starting from $1$ , and $y$ ( $y \in \lbrace \text{Yes}, \text{No} \rbrace$ ) denotes whether or not the graphs exist in this test case.

If the graphs exist, then output ( $n + 1$ ) extra lines.

The first $n$ lines represent the graph G, where each line contains a binary string of length $n$ . In the $i$ -th line, the $j$ -th character $G_{i, j}$ is 1 when the $i$ -th vertex and the $j$ -th one are adjacent, or otherwise, in case they are not adjacent, $G_{i, j}$ is 0. Note that $G_{i, i}$ must be 0 and $G_{i, j}$ must be the same as $G_{j, i}$ .

The last line contains $n$ space-separated integers $f_1$ , $f_2$ , $\ldots$ , $f_n$ , representing an isomorphism of graphs G and H in which the $i$ -th vertex in the graph G is mapped to the $f_i$ -th vertex in the complement graph H. Note that every two consecutive integers in one line should be separated by a single space, $\text{please do not add any tailing space in your output}$ .

## F - K-ary Heap

### 题目描述

A K-ary heap of size n is an array $[a_0, a_1, \ldots, a_{n - 1}]$ , and for each pair of indices i and j which satisfy $0 \leq i \leq n - 1$ , $K \cdot i + 1 \leq j \leq \min \lbrace K \cdot i + K, n - 1 \rbrace$ , $a_j$ is strictly greater than $a_i$ .

Considering all possible K-ary heaps of size n which are also permutations obtained from 1 to n, let us write down these heaps in lexicographical order, and then label them starting from 1. For example, when $n = 3, K = 2$ , there are two possible heaps $[1, 2, 3]$ and $[1, 3, 2]$ , which are labeled $1$ and $2$ respectively.

Given a K-ary heap of size n which is also a permutation obtained $1$ to $n$ , we want you to find the label of this heap after doing the aforementioned process. As the answer can be very large, we request you to report the label modulo $(10^{9} + 7)$ .

### 输入描述

There are multiple test cases. The first line contains an integer $T$ ( $1 \leq T \leq 20$ ), indicating the number of test cases. Test cases are given in the following.

For each test case, the first line contains two integers $n, K$ ( $1 \leq n, K \leq 3000$ ).

The second line contains n distinct integers $a_0$ , $a_1$ , $\ldots$ , $a_{n - 1}$ ( $1 \leq a_0, a_1, \ldots, a_{n - 1} \leq n$ ). We ensure that the given heap is a valid K-ary heap and also a permutation obtained from $1$ to $n$ .

### 输出描述

For each test case, output Case #x: y in one line (without quotes), where $x$ indicates the case number starting from $1$ , and $y$ denotes the label of the heap in this test case modulo $(10^{9} + 7)$ .

## G - Is Today Friday?

### 题目描述

No, it’s not Friday :(

TangTang loves Friday and he has made up a list of n days which are all Friday! Each date in this list is formed as yyyy/mm/dd, where yyyy is a four-digit number representing the year, mm is a two-digit number representing the month and dd is a two-digit number representing the day. TangTang only considers years between $1600$ and $9999$ (inclusive), so each year in the list always has four digits, but the months and the days may have leading zeros when it’s necessary. For example, August 3rd, 2019 should be formed as 2019/08/03.

To store safely, TangTang ciphered the list using a simple substitution cipher. He substituted each digit by a letter between A and J such that the same digits correspond to the same letter and different digits to different letters.

### 输入描述

There are multiple test cases. The first line contains an integer $T$ ( $1 \leq T \leq 10$ ), indicating the number of test cases. Test cases are given in the following.

For each test case, the first line contains an integer $n$ ( $1 \leq n \leq 100000$ ), indicating the number of dates.

Each of the next n lines contains a string in the form of yyyy/mm/dd, representing a ciphered date, where each digit is substituted by an uppercase letter between ‘A’ and ‘J’.

### 输出描述

For each test case, output Case #x: y in one line (without quotes), where $x$ indicates the case number starting from $1$ , and $y$ denotes the answer to this test case.

If there is no way to restore the list, then $y$ is Impossible.

Otherwise, y is a string consisting of ten distinct digits, representing the key to decipher the list. More specifically, the $i$ -th digit in y corresponds to the $i$ -th uppercase letter.

If there are at least two ways, then $y$ is the smallest possible string in the lexicographical order.

## H - Train Driver

### 题目描述

It’s time for training! WJJ, DYX and ZZH from the team Nonsense Time want to find a place in BUAA (shorten for Beihang University) to hold their team training. BUAA can be regarded as an undirected connected graph $G = (V, E)$ with n nodes as places and m edges as routes, where the length of each edge is $1$ .

Since there is no fixed place in BUAA for programming competition training, they have to find a meeting place and make training at that place. They always want to minimize the total distance they need to consume from their previous locations to the meeting place so that they save more energy for training.

However, their previous locations are not always fixed as well. As we know, each of DYX and ZZH is always at one of the places they usually stay at, such as dormitory, canteen, etc., but WJJ may be at anywhere inside BUAA! They constantly need to estimate the total distance they would consume, so they build a statistic model for themselves.

In this model, DYX may show up with equal probability at a node randomly chosen from the set $A$ , ZZH may show up with equal probability at a node randomly chosen from the set $B$ , and WJJ may show up with equal probability at a node randomly chosen from BUAA. When they want training, they will find a place to meet such that the total distance can be minimized.

As the coach of Nonsense Time, please help them to calculate the expected minimum total distance based on this model.

### 输入描述

There are multiple test cases. The first line contains an integer $T$ ( $1 \leq T \leq 5$ ), indicating the number of test cases. Test cases are given in the following.

For each test case, the first line contains two integers $n, m$ ( $1 \leq n, m \leq 100000$ ), representing the number of nodes and the number of edges in BUAA respectively.

Each of the next $m$ lines contains two integers $u, v$ ( $1 \leq u, v \leq n$ ), representing an undirected edge between the u-th node and the $v$ -th one.

The next line begins with an integer $S_A$ ( $1 \leq S_A \leq \min \lbrace n, 20 \rbrace$ ), indicating the size of the set $A$ , and then $S_A$ distinct integers follow, representing the indices of nodes in the set $A$ .

The last line begins with an integer $S_B$ ( $1 \leq S_B \leq \min \lbrace n, 20 \rbrace$ ), indicating the size of the set $B$ , and then $S_B$ distinct integers follow, representing the indices of nodes in the set $B$ .

We ensure that each given index is ranged from $1$ to $n$ .

### 输出描述

For each test case, output Case #x: y in one line (without quotes), where $x$ indicates the case number starting from $1$ , and y denotes the irreducible fraction form of the answer to this test case. Note that the denominator should be omitted when it equals $1$ .

### 题解

#### 题意

$n$ 个点 $m$ 个边，一个人随机出现在集合 $A$ 中的点里，一个人随机出现在集合 $B$ 中的点里，还有一个人在整个地图中随机出现。询问这三个人会合在一起的最短路径之和的期望值。

## I - Can They Go to Galar?

### 题目描述

Pokemons are planning their travel to the new region Galar. However, it is difficult to allow all of them to go there due to limited funds.

There are $n$ pokemons all over the world, numbered from $1$ to $n$ . We decide who can go to Galar according to the following rules.

We start with a cactus (i.e. a connected graph in which every edge belongs to at most one simple cycle) having $n$ vertices and $m$ bidirectional edges, where the $i$ -th vertex represents the pokemon $i$ and each edge has a probability to go through.

Pokemons go to Galar in rounds. In the first round, only the pokemon $1$ is allowed to go to Galar. In the $i$ -th round ( $i = 2, 3, \ldots$ ), if pokemon $u$ has got the permission to Galar in the ( $i - 1$ )-th round, pokemon $v$ hasn’t got the permission yet, and there is an edge between pokemon $u$ and pokemon $v$ with probability $w$ to go through, then pokemon $v$ will have a probability $w$ to go to Galar in this round. If there is no pokemon that can get permission, the further rounds will be skipped. You can see the note after the sample for better understanding of this procedure.

Please calculate the expected population of pokemons that can travel to Galar. In order to avoid precision issues, output the expected value modulo $998244353$ . Formally, let the answer be $\dfrac{p}{q}$ , you need to output the minimum non-negative integer $r$ satisfying that $p \equiv q r \pmod{998244353}$ . For example, $9 \equiv 4 \times 748683267 \pmod{998244353}$ .

### 输入描述

There are multiple test cases. The first line contains an integer $T$ ( $1 \leq T \leq 10$ ), indicating the number of test cases. Test cases are given in the following.

For each test case, the first line contains two integers $n, m$ ( $0 \leq n, m \leq 100000$ , $n \geq 1$ ), representing the number of vertices and the number of edges in the cactus respectively.

Each of the next $m$ lines contains four integers $u, v, a, b$ ( $1 \leq u, v \leq n$ , $0 \leq a \leq b \leq 10^5$ , $b \geq 1$ ), representing an edge between the $u$ -th vertex and the $v$ -th one with probability $\frac{a}{b}$ to go through. We ensure that the given graph is a cactus with no self-loops or multiple edges.

### 输出描述

For each test case, output Case #x: y in one line (without quotes), where $x$ indicates the case number starting from $1$ , and $y$ denotes the answer to this test case modulo $998244353$ .

### 示例1

#### 说明

In the second example case, there are six possible cases in total as following.

1. $\lbrace 1 \rbrace \to \emptyset$ with probability $\dfrac{1}{4}$ .
2. $\lbrace 1 \rbrace \to \lbrace 2 \rbrace \to \emptyset$ with probablity $\frac{1}{8}$ .
3. $\lbrace 1 \rbrace \to \lbrace 2 \rbrace \to \lbrace 3 \rbrace \to \emptyset$ with probablity $\dfrac{1}{8}$ .
4. $\lbrace 1 \rbrace \to \lbrace 3 \rbrace \to \emptyset$ with probablity $\dfrac{1}{8}$ .
5. $\lbrace 1 \rbrace \to \lbrace 3 \rbrace \to \lbrace 2 \rbrace \to \emptyset$ with probablity $\dfrac{1}{8}$ .
6. $\lbrace 1 \rbrace \to \lbrace 2, 3 \rbrace \to \emptyset$ with probablity $\dfrac{1}{4}$ .

Hence, the answer is $1 \times \dfrac{1}{4} + 2 \times \dfrac{1}{8} + 3 \times \dfrac{1}{8} + 2 \times \dfrac{1}{8} + 3 \times \dfrac{1}{8} + 3 \times \dfrac{1}{4} = \dfrac{9}{4}$ .

### 题目描述

Rowlet is playing a very popular game in the pokemon world. Recently, he has encountered a problem and wants to ask for your help.

In this game, there is a technology tree system. There are n kinds of technology in this game, each of them has m levels numbered from $1$ to $m$ . In the beginning, all technologies have no level (regard as level $0$ ). When the $i$ -th technology is at the ( $j - 1$ )-th level, the player can pay $c_{i j}$ pokedollars (currency used in this game) to upgrade this technology into the $j$ -th level. However, sometimes upgrading is so easy that the cost might be negative, which implies the player may gain profit from upgrading technologies.

Moreover, if all technologies have been upgraded to level $j$ , the player will gain an additional profit of $d_{j}$ pokedollars. However, sometimes too many technologies of the same level might be confusing, hence the profit can be negative as well.

Rowlet wants to determine the optimal strategy that can bring him the most pokedollars. Help him to find the maximum gain. Note that Rowlet may upgrade nothing, and in that case, the profit is zero.

### 输入描述

There are multiple test cases. The first line contains an integer $T$ ( $1 \leq T \leq 10$ ), indicating the number of test cases. Test cases are given in the following.

For each test case, the first line contains two integers $n, m$ ( $1 \leq n, m \leq 1000$ ), representing the number of technologies and the number of levels respectively.

The $i$ -th of the next $n$ lines contains $m$ integers, where the $j$ -th number is $c_{i j}$ ( $-10^{9} \leq c_{i j} \leq 10^{9}$ ).

The last line contains $m$ integers, where the $j$ -th number is $d_{j}$ ( $-10^{9} \leq d_{j} \leq 10^{9}$ ).

We ensure that the sum of $n \cdot m$ in all test cases is at most $2 \times 10^{6}$ .

### 输出描述

For each test case, output Case #x: y in one line (without quotes), where $x$ indicates the case number starting from $1$ , and $y$ denotes the answer(in pokedollars) to this test case.

### 示例1

#### 说明

In the first example, Rowlet can upgrade the first technology to level $1$ and the second technology to level $2$ , which costs $1 + 2 - 1 = 2$ pokedollars, but Rowlet can get $4$ pokedollars as the bonus of upgrading all technologies to level $1$ , so the answer is $4 - 2 = 2$ pokedollars .

In the second example, Rowlet can upgrade all technologies to level $2$ , which costs $1\times3 + 2\times3=9$ pokedollars, but Rowlet can get $6$ pokedollars as the bonus of upgrading all technologies to level $1$ and $7$ pokedollars as the bonus of upgrading all technologies to level $2$ , so the answer is $6 + 7 - 9 = 4$ pokedollars.

### 题解

#### 题意

Rowlet在口袋妖怪世界中扮演一个非常受欢迎的游戏。最近，他遇到了一个问题，想要求你的帮助。

Rowlet希望确定能够为他带来最多刺激的最佳策略。帮助他找到最大的收益。请注意，Rowlet可能不会升级，在这种情况下，利润为零。