## 题目概览

A Competition 签到
B Xor of Sequences 签到
C Max GCD 2 签到，枚举
D Nowhere $$P$$ 签到，找规律
*E Level K Palindrome
*F Max Matrix 线段树 / 平衡树
G Spanning Tree 并查集 + 矩阵树定理
*H Shipping

## A - Competition

Time Limit: 2 sec / Memory Limit: 1024 MB

Score: 100 points

### Problem Statement

A Supermarket Takahashi sells an $$X$$-gram beef pack for $$Y$$ yen

Another Supermarket Snuke has decided to sell a beef pack at a lower price per gram

In Snuke, one beef pack weighs $$Z$$ grams. What is the greatest possible price (a non-negative integer) for Snuke's beef pack such that it is strictly cheaper than Takahashi's beef pack per gram?

### Constraints

• All values in input are integers
• $$1\leqslant X,Y,Z\leqslant 10^3$$

### Input

Input is given from Standard Input in the following format:

$$X\ Y\ Z$$

### Sample Output 1

Both stores sell $$100$$-gram packs, so Snuke can just make it one yen cheaper than that in Takahashi

### Sample Output 2

Takahashi sells beef for $$\frac{971}{103}=9.4271...$$ yen per gram. Snuke can sell $$593$$ grams of beef for $$5590$$ yen to make it $$\frac{5590}{593}=9.4266...$$ yen per gram

### Sample Output 3

The price is allowed to be $$0$$ yen

### 解题思路

$$\lfloor\frac{yz}{x}\rfloor-[x\mid yz]$$

Show code

## B - Xor of Sequences

Time Limit: 2 sec / Memory Limit: 1024 MB

Score: 200 points

### Problem Statement

We have two strictly increasing integer sequences $$A=(A_1,A_2,...,A_N)$$ and $$B=(B_1,B_2,...,B_M)$$

Find all integers that appear in exactly one of $$A$$ and $$B$$ and print them in ascending order

### Constraints

• All values in input are integers
• $$1\leqslant N,M\leqslant 10^3$$
• $$1\leqslant A_1<A_2<...<A_N\leqslant 10^3$$
• $$1\leqslant B_1<B_2<...<B_M\leqslant 10^3$$

### Input

Input is given from Standard Input in the following format:

$$N\ M$$

$$A_1\ A_2\ ...\ A_N$$

$$B_1\ B_2\ ...\ B_M$$

### Output

Print all integers that appear in exactly one of $$A$$ and $$B$$

in ascending order, with space as separator

### Sample Output 1

$$1$$ is contained in both $$A$$ and$$B$$

$$2$$ is contained in only $$A$$

$$3$$ is contained in only $$B$$

Thus, we should print $$2$$ and $$3$$

### Sample Output 2

You can print an empty line or nothing

Show code

## C - Max GCD 2

Time Limit: 2 sec / Memory Limit: 1024 MB

Score: 300 points

### Problem Statement

Given are integers $$A$$ and $$B$$. Find the maximum possible value of $$\gcd(x,y)$$ when we choose integers x and y so that $$A\leqslant x<y\leqslant B$$

Here, $$\gcd(x,y)$$ denotes the greatest common divisor of $$x$$ and $$y$$

### Constraints

• $$A$$ and $$B$$ are integers
• $$1\leqslant A<B\leqslant 2\times 10^5$$

### Input

Input is given from Standard Input in the following format:

$$A\ B$$

### Sample Output 1

We have three ways to choose $$(x,y)$$ such that $$A\leqslant x<y\leqslant B$$: $$(2,3),(2,4),(3,4)$$, where the greatest common divisors are $$1,2,1$$, respectively, so the maximum possible value is $$2$$

### Sample Output 2

We have $$\gcd(199999,200000)=1$$

Show code

## D - Nowhere P

Time Limit: 2 sec / Memory Limit: 1024 MB

Score: 400 points

### Problem Statement

You are given a prime number $$P$$ not less than $$2$$, which you don't like

Let's call an array of integers $$A_1,A_2,...,A_N$$ very good if it satisfies the following condition:

• there is no $$i$$ with $$1\leqslant i\leqslant N$$ and $$A_1+A_2+...+A_i\equiv0\pmod P$$

Consider all $$(P-1)^N$$ arrays of length $$N$$ with elements from $$1$$ to $$P-1$$. How many of them are very good?

As this number can be very big, output it modulo $$10^9+7$$

### Constraints

• $$N$$ and $$P$$ are integers
• $$1\leqslant N\leqslant 10^9$$
• $$2\leqslant P\leqslant 10^9$$

### Input

Input is given from Standard Input in the following format:

$$N\ P$$

### Output

Print the count modulo $$10^9+7$$

### Sample Output 1

Two arrays, $$(1,1,2)$$ and $$(2,2,1)$$, satisfy the condition

### 题意简述

$\forall i\in[1,n]_{\mathbb{N}},~\sum_{j=1}^iA_j{\equiv}\llap{/\,}0\pmod P$

Show code

## E - Level K Palindrome

Time Limit: 2 sec / Memory Limit: 1024 MB

Score: 500 points

### Problem Statement

As a token of his gratitude, Takahashi has decided to give Snuke a level-$$K$$ palindrome. A level-$$L$$ palindrome, where $$L$$ is a non-negative integer, is defined as follows:

• Let $$\operatorname{rev}(s)$$ denote the reversal of a string $$s$$
• A string $$s$$ is said to be a palindrome when $$s=\operatorname{rev}(s)$$
• The empty string and a string that is not a palindrome are level-$$0$$ palindromes
• For any non-empty level-($$L-1$$) palindrome $$t$$, the concatenation of $$t$$,$$\operatorname{rev}(t)$$ in this order is a level-$$L$$ palindrome
• For any level-($$L-1$$) palindrome $$t$$ and any character $$c$$, the concatenation of $$t$$,$$c$$,$$\operatorname{rev}(t)$$ in this order is a level-$$L$$ palindrome

Now, Takahashi has a string $$S$$. Determine whether it is possible to make $$S$$ an exactly level-$$K$$ palindrome by doing the following action zero or more times: choose a character in $$S$$ and change it to another lowercase English letter. If it is possible, find the minimum number of changes needed to make $$S$$ a level-$$K$$ palindrome

### Constraints

• $$K$$ is an integer
• $$0\leqslant K\leqslant 5\times 10^5$$
• $$S$$ consists of lowercase English letters
• $$1\leqslant |S|\leqslant 5\times 10^5$$

### Input

Input is given from Standard Input in the following format:

$$K\ S$$

### Output

If it is possible to get an exactly level-$$K$$ palindrome, print the minimum number of changes needed. If it is impossible, print impossible

### Sample Output 1

We can find the level of aabaaaabaa as follows:

• the empty string is a level-$$0$$ palindrome
• a is a concatenation of (empty string), a, (empty string) in this order, so it is a level-$$1$$ palindrome
• aa is a concatenation of a, a in this order, so it is a level-$$2$$ palindrome
• aabaa is a concatenation of aa, b, aa in this order, so it is a level-$$3$$ palindrome
• aabaaaabaa is a concatenation of aabaa, aabaa in this order, so it is a level-$$4$$ palindrome

Thus, aabaaaabaa is already a level-$$4$$ palindrome and needs no changes

### Sample Output 2

We can, for example, change aabaaaabaa to acbcaacbca to get a level-$$2$$ palindrome

Note that aabaaaabaa is not a level-$$2$$ palindrome

### 题意简述

• 定义其反转为: $$\operatorname{rev}(s)$$, 则 $$s$$ 是回文串 $$\iff s=\operatorname{rev}(s)$$
• $$+$$ 运算定义为字符串的拼接
• 定义字符串上的变换为：将其中某一字符替换为一小写英文字母

• 空串，非回文串为 $$0$$ 阶回文串
• $$i$$ 阶非空回文串 $$s$$, 定义 $$s+\operatorname{rev}(s)$$$$i+1$$ 阶回文串
• $$i$$ 阶回文串 $$s$$ 和单个字符 $$c$$, 定义 $$s+c+\operatorname{rev}(s)$$$$i+1$$ 阶回文串

Show code

## F - Max Matrix

Time Limit: 3 sec / Memory Limit: 1024 MB

Score: 600 points

### Problem Statement

We have a sequence a of length $$N$$ and a sequence $$b$$ of length $$M$$. Initially, every element in $$a$$ and $$b$$ is $$0$$

You are asked to process $$Q$$ queries. In the $$i$$-th query, given three integers $$T_i$$, $$X_i$$, and $$Y_i$$, do the following:

• if $$T_i=1$$: replace $$a_{X_i}$$ with $$Y_i$$
• if $$T_i=2$$: replace $$b_{X_i}$$ with $$Y_i$$

Then, after processing each query, print the value $$\displaystyle\sum_{i=1}^N\sum_{j=1}^M\max(a_i,b_j)$$

### Constraints

• $$1\leqslant N\leqslant 2\times 10^5$$
• $$1\leqslant M\leqslant 2\times 10^5$$
• $$1\leqslant Q\leqslant 2\times 10^5$$
• $$T_i$$ is $$1$$ or $$2$$
• If $$T_i=1$$, $$1\leqslant X_i\leqslant N$$
• If $$T_i=2$$, $$1\leqslant X_i\leqslant M$$
• $$1\leqslant Y_i\leqslant 10^8$$
• All values in input are integers

### Input

Input is given from Standard Input in the following format:

$$N\ M\ Q$$

$$T_1\ X_1\ Y_1$$

$$T_2\ X_2\ Y_2$$

$$T_3\ X_3\ Y_3$$

$$\vdots$$

$$T_Q\ X_Q\ Y_Q$$

### Output

Print $$Q$$ integers as instructed in Problem Statement, with newline as separator

### Sample Output 1

If we write $$\max(a_i,b_j)$$ at the $$i$$-th row and $$j$$-th column in a grid, the four queries will change it as follows:

### Sample Output 3

The integers to be printed may not fit into a $$32$$-bit integer type

### 题意简述

• $$a$$ 中的某个数赋一个值
• $$b$$ 中的某个数赋一个值

Show code

## G - Spanning Tree

Time Limit: 2 sec / Memory Limit: 1024 MB

Score: 600 points

### Problem Statement

We have a graph with $$N$$ vertices numbered $$1,2,...,N$$. Initially, it has no edges

Now, let us add some number of undirected edges to $$G$$ so that the following condition holds for any $$i,j(i\ne j)$$

• If $$A_{i,j}=1$$, there is an edge directly connecting Vertex $$i$$ and Vertex $$j$$
• if $$A_{i,j}=0$$, there is no edge directly connecting Vertex $$i$$ and Vertex $$j$$
• if $$A_{i,j}=-1$$, either is fine

Among the graphs that can be $$G$$ after addition, how many are trees?

Since the count can be enormous, find it modulo $$10^9+7$$

### Constraints

• All values in input are integers
• $$2\leqslant N\leqslant 300$$
• $$-1\leqslant A_{i,j}=A_{j,i}\leqslant 1$$
• $$A_{i,i}=0$$

### Input

Input is given from Standard Input in the following format:

$$N$$

$$A_{1,1}\ ...\ A_{1,N}$$

$$\vdots$$

$$A_{N,1}\ ...\ A_{N,N}$$

### Output

Print the count modulo $$10^9+7$$

### Sample Output 1

We need an edge between Vertex $$1$$ and Vertex $$2$$, and we must not add an edge between Vertex $$1$$ and Vertex $$4$$ or between Vertex $$3$$ and Vertex $$4$$

Thus, we have the following two valid graphs:

### Sample Output 4

When we distinguish the vertices, there are $$11^9$$ trees with $$11$$ vertices

### 题意简述

$$n$$ 个点，考虑以这 $$n$$ 个点为顶点，满足如下条件的所有图:

• 无向图
• 给出一个矩阵 $$A$$
• $$A_{i,j}=1$$, 则点 $$i$$ 和点 $$j$$ 间有一条无向边
• $$A_{i,j}=0$$, 则点 $$i$$ 和点 $$j$$ 间没有边
• $$A_{i,j}=-1$$, 则为上述两种情况的任一种

Show code

## H - Shipping

Time Limit: 5 sec / Memory Limit: 1024 MB

Score: 600 points

### Problem Statement

In the Republic of AtCoder, there are $$N$$ cities called City $$1$$ through City $$N$$ and $$N$$ canals called Canal $$1$$ through Canal $$N$$

Canal $$i$$ connects City $$i$$ and City $$A_i$$ bidirectionally, and you have to pay the toll of $$C_i$$

yen to go through it, but after paying the toll once, you can use it any number of times in any direction

It is guaranteed that you can reach from any city to any city using some canals

You are asked to deliver $$M$$ cargoes in this country. The $$i$$-th cargo should be delivered from City $$X_i$$ to City $$Y_i$$

There is no way other than using the canals to deliver the cargoes, but you yourself can travel between the cities freely without using the canals

Find the minimum total toll you have to pay to deliver all $$M$$ cargoes

### Constraints

• $$3\leqslant N\leqslant 2\times 10^5$$
• $$1\leqslant M\leqslant 2\times 10^5$$
• $$1\leqslant A_i\leqslant N$$
• $$A_i\ne i$$
• $$1\leqslant C_i\leqslant 10^9$$
• It is possible to reach from any city to any city by using some canals
• $$1\leqslant X_i\leqslant N$$
• $$1\leqslant Y_i\leqslant N$$
• $$X_i\ne Y_i$$
• All values in input are integers

### Input

Input is given from Standard Input in the following format:

$$N\ M$$

$$A_1\ C_1$$

$$A_2\ C_2$$

$$A_3\ C_3$$

$$\vdots$$

$$A_N\ C_N$$

$$X_1\ Y_1$$

$$X_2\ Y_2$$

$$X_3\ Y_3$$

$$\vdots$$

$$X_M\ Y_M$$

### Output

Print the minimum total toll you have to pay, as an integer

### Sample Output 1

The figure below shows the cities and canals in this country, where numbers along the lines representing canals represent the tolls:

You can deliver the cargoes as follows to make the total toll $$10$$ yen:

• The $$1$$-st cargo: use Canal $$1,4$$ to deliver it on the route: City $$4,1,3$$
• The $$2$$-nd cargo: use Canal $$3,1$$ to deliver it on this route: City $$2,3,1$$

### Sample Output 2

Multiple canals may connect the same pair of cities

### 题意简述

• $\forall i\in[1,M]_{\mathbb{N}},~\operatorname{dis}(x_i,y_i)\ne\infty$

### 代码参考

Show code

1. 打 * 的是还没写的题↩︎