Theme NexT works best with JavaScript enabled

## A - Eddy Walker

### 题目描述

Eddy likes to walk around. Especially, he likes to walk in a loop called “Infinite loop”. But, actually, it’s just a loop with finite length(Anyway, the name doesn’t matter). Eddy can walk in a fixed length. He finds that it takes him N steps to walk through the loop a cycle. Then, he puts $N$ marks on the “Infinite loop” labeled with $0, 1, \ldots, N-1$ , where $i$ and $i+1$ are a step away each other, so as $0$ and $N-1$ . After that, Eddy stands on the mark labeled $0$ and start walking around. For each step, Eddy will independently uniformly randomly choose to move forward or backward. If currently Eddy is on the mark labeled $i$ , he will on the mark labeled $i+1$ if move forward or $i-1$ if move backward. If Eddy is on the mark labeled $N-1$ and moves forward, he will stand on the mark labeled $0$ . If Eddy is on the mark labeled $0$ and moves backward, he will stand on the mark labeled $N-1$ .

Although, Eddy likes to walk around. He will get bored after he reaches each mark at least once. After that, Eddy will pick up all the marks, go back to work and stop walking around.

You, somehow, notice the weird convention Eddy is doing. And, you record $T$ scenarios that Eddy walks around. For i-th scenario, you record two numbers $N_i$ , $M_i$ , where $N_i$ tells that in the i-th ​scenario, Eddy can walk through the loop a cycle in exactly $N_i$ steps ( Yes! Eddy can walk in different fixed length for different day.). While $M_i$ tells that you found that in the i-th scenario, after Eddy stands on the mark labeled $M_i$ ​, he reached all the marks.

However, when you review your records, you are not sure whether the data is correct or even possible. Thus, you want to know the probability that those scenarios will happen. Precisely, you are going to compute the probability that first $i$ scenarios will happen sequentially for each $i$ .

Precisely, you are going to compute the probability that first $i$ scenarios will happen sequentially for each $i$ .

### 输入描述

The first line of input contains an integers $T$ .

Following $T$ lines each contains two space-separated integers $N_i$ ​ and $M_i$ ​.

$1 \leq T \leq 1021$

$0 \leq M_i < N_i \leq 10^9$

### 输出描述

Output $T$ lines each contains an integer representing the probability that first i scenarios will happen sequentially.
you should output the number module $10^9+7(1000000007)$ .
Suppose the probability is $\dfrac{P}{Q}$ ​, the desired output will be $P \times Q^{-1}\mod 10^9+7$

### 题解

#### 解法

• 若设答案 $f(n,m)$ ，可以发现这个函数有如下性质：

• 函数是关于零点对称的，即 $f(n,m)=f(n,n−m)$
• 若 $m \neq 0,1,n−1$ ，则 $f(n,m)=\dfrac{f(n,m−1)+f(n,m+1)}{2}$
• 接着考虑 $n$ 的奇偶性

• 若 $n$ 为奇数，则设 $a=\lfloor \dfrac{n}{2} \rfloor ,b=\lceil \dfrac{n}{2} \rceil,c=b+1$ 。可以发现由如上两条性质，有 $f(n,a)=f(n,b)$ ，且 $f(n,b)=\dfrac{f(n,a)+f(n,c)}{2}$ ，因此可以得出 $f(n,a)=f(n,b)=f(n,c)$ 。以此类推则可以得出所有 $f(n,m)$ 相等，所以函数取值为 $\dfrac{1}{n−1}$
• 若 $n$ 为偶数，则设 $a= \dfrac{n}{2}-1 ,b= \dfrac{n}{2} ,c=\dfrac{n}{2} +1$ ，可以得出 $f(n,a)=f(n,c)$ ，且 $f(n,b)=\dfrac{f(n,a)+f(n,c)}{2}$ ，同样可以推出 $f(n,a)=f(n,b)=f(n,c)$ ，同理可证 $f(n,m)=\dfrac{1}{n−1}(m \neq 0)$
• 注意对 $n=1$ 的特判

## B - Eddy Walker 2

### 题目描述

As you may already know, Eddy likes to walk around. Especially, he likes to walk in a number line called “Infinite line”. Actually, it’s exactly a line with infinite length!

Eddy is at number $0$ and starts to walk around. Since Eddy is a little drunk(just finished his work, make sense), he will not walk in a fixed length. Instead, he will independently uniformly randomly walk in an integer length between $1$ and $K$ . That is, he will walk for $1$ unit of length in a probability of $\dfrac{1}{K}$ ​, $2$ units in $\dfrac{1}{K}$ , $\cdots$ , $K$ units in $\dfrac{1}{K}$ . If he currently stands on number $i$ and walk for $j$ unit of length, he will end up on number $i+j$ .

Since Eddy is drunk, he will walk around infinitely. You, somehow, notice this weird thing and start wondering whether will Eddy ever step on the number $N$ . However, you don’t want to wait for such stupid thing. You would like to compute the probability that Eddy would ever step on number $N$ .

### 输入描述

The first line of input contains an integers T.

Following T lines each contains two space-separated integers $K_i$ and $N_i$ .

If $N_i = -1$ , $N_i$ ​ is a number approaching infinity.

• $1 \leq T \leq 10$
• $1 \leq K_i \leq 1021$
• $\textbf{-1} \leq N_i \leq 10^{18}$

### 输出描述

For each $i$ , output one line containing a number representing the probability.

you should output the number module $10^9+7(1000000007)$

Suppose the probability is $\dfrac{P}{Q}$ , the desired output will be $P \times Q^{-1} \mod 10^9+7$

### 题解

#### 题意

T组数据，每次给定一对 $n$ 和 $k$ 。现在你从 $0$ 号点出发， 每次有 $\dfrac{1}{k}$ 的概率前进 $1$ 步， $\dfrac{1}{k}$ 的概率前进 $2$ 步， $\dfrac{1}{k}$ 的概率前进 $3$ 步 $\dots$ $\dfrac{1}{k}$ 的概率前进 $k$ 步 ， 询问你经过 $n$ 号点的期望。特别的，如果 $n$ 为 $-1$ ，则表示询问 $n$ 无限大时经过它的概率。

#### 解法

• n为有限远处时

• 令 $P_{i}$ 表示从经过 $i$ 点的概率。那么 $\displaystyle P_{i}=\sum_{j=max(i-k,1)}^{i-1} P_{j} \times \dfrac{1}{k}$
• 表示从前 $k$ 步转移过来，转移概率为 $\dfrac{1}{k}$
• 然后我们发现这个公式是个线性递推式，于是套用BM算法
• 注意至少要推入 $2 \times k$ 项
• n为无限远处时

• 假设到达某一个无穷远处的期望为 $E$
• 那么有 $\displaystyle E = \sum_{i=1}^{k} i \times \dfrac{1}{k} = \dfrac{1+k}{2}$
• 所以此时 $P_{n}$ 为 $\dfrac{2}{1+k}$

## C - Go on Strike!

### 题目描述

There are $N$ cities in Eddy’s neverland. There are some flights to connect some pair of cities. Except flight, there’s no any other way to shuttle between cities.

However, in some cases, flight attendants may go on strike to fight for their rights. Therefore, some flight may be shut down for a period of time. On the other hand, some flight may come out to compete the market.

In Eddy’s neverland, each flight must propose its expected cost to be granted the license to fly. Then, Eddy will choose some flights and grant them the licenses. In order to keep the neverland great, Eddy will choose a minimum total cost flights to grant the license such that each city is possible to connect to each other city by the granted flights.

Since the new coming flight and flight shut down events come everyday, Eddy is not able to find out the best combination of flights with minimum total cost. Please help Eddy to keep his neverland great. Reporting the chosen combination would be too large to check. You only need to tell Eddy what is the most flights needed to connect two cities is under the chosen flights(Not the total cost!).

### 输入描述

The first line of input contains two space-separated integers $N$ and $Q$ , where $N$ is the number of cities and $Q$ is the number of events.

Following $Q$ lines each contains four space-separated integers $q_i, u_i, v_i, c_i$ . If $q_i = 1$ , there is a new flight coming out between city $u_i$ and city $v_i$ with cost $c_i$ . If $q_i = 0$ , the flight attendants of the flight connecting city $u_i$ and $v_i$ with cost $c_i$ has gone on strike and the flight is shut down.

• $1 \leq N \leq 10^4$
• $1 \leq Q \leq 2 \times 10^4$
• $0 \leq q_i \leq 1$
• $1 \leq u_i \neq v_i \leq N$
• $0 \leq c_i \leq 10^9$

It’s guaranteed that if $q_i = 0$ , the required flight exists.

### 输出描述

Output $Q$ lines each contains an integer representing the most flights needed to connect two cities in the chosen combination. If there exists two cities which can not be connected through the current flights, output $\texttt{“-1”}$ .

It’s guaranteed that the chosen combination will be unique.

### 示例2

#### 说明

First two flights are not enough to make each pair of cities connected.First three flights are enough to make each pair of cities connected. The most flights needed to connect some pair of cities results from connecting city $2$ and city $3$ which needs two flights to connect(so as city $2$ and city $4$ , city $3$ and city $4$ ).The forth flights won’t be included in the chosen combination. The scenario remains the same.

## D - Kth Minimum Clique

### 题目描述

Given a vertex-weighted graph with N vertices, find out the K-th minimum weighted clique.

A subset of vertices of an undirected graph is called clique if and only if every two distinct vertices in the subset are adjacent. The weight of a clique is the summation of the weight of vertices in it.

### 输入描述

The first line of input contains two space-separated integers $N$ , $K$ .

The second line of input contains $N$ space-separated integers $w_i$ representing the weight of each vertex.

Following $N$ lines each contains $N$ characters $e_{ij}$ . There’s an edge between vertex $i$ and vertex $j$ if and only if $e_{ij} =\texttt{“1”}$ .

• $1 \leq N \leq 100$
• $1 \leq K \leq 10^6$
• $0 \leq w_i \leq 10^9$
• $e_{ij} \in \texttt{“01”}$
• $e_{ii} = \texttt{“0”}$
• $e_{ij} = e_{ji}$

### 输出描述

Output one line containing an integer representing the answer. If there’s less than $K$ cliques, output $\texttt{“-1”}$ .

## E - MAZE

### 题目描述

Given a maze with $N$ rows and $M$ columns, where $b_{ij}$ represents the cell on the i-row, j-th column. If $b_{i, j} = \texttt{“1”}$ , it’s a wall and can’t not be passed. If you are on the cell $b_{i, j}$ , you can go to $b_{i+1, j}$ , $b_{i, j-1}$ , or $b_{i,j+1}$ as long as it’s not a wall.

Sometime, a cell may be changed into wall, or vise versa. You need to find out the number of way to pass through the maze starting at some given cell and finishing at some given cell.

If the starting cell or finishing cell is a wall, there’s clearly no way to pass through the maze.

Note that you can’t go back to the cell you just from.

### 输入描述

The first line of input contains three space-separated integers $N$ , $M$ , $Q$ .

Following $N$ lines each contains M characters $b_{ij}$ ​ representing the maze .

Following $Q$ lines each contains three space-separated integers $q_i, a_i, b_i$ .

If $q_i = 1$ , the state of cell $b_{a_i, b_i}$ is changed.

If $q_i = 2$ , you need to find out the number of way to start at cell $b_{1, a_i}$ ​​ and finish at cell $b_{N, b_i}$ ​​.

• $1 \leq N, Q \leq 50000$
• $1 \leq M \leq 10$
• $b_{ij} \in \texttt{“01”}$
• $1 \leq q_i \leq 2$
• If $q_i = 1$ , $1 \leq a_i \leq N$ and $1 \leq b_i \leq M$ .
• If $q_i = 2$ , $1 \leq a_i, b_i \leq M$ .

### 输出描述

For each $q_i = 2$ , Output one line containing an integer representing the answer module $10^9+7(1000000007)$ .

## F - Partition problem

### 题目描述

Given $2N$ people, you need to assign each of them into either red team or white team such that each team consists of exactly $N$ people and the total competitive value is maximized.

Total competitive value is the summation of competitive value of each pair of people in different team.

The equivalent equation is $\displaystyle\sum_{i=1}^{2N} \sum_{j=i+1}^{2N}$ ( $v_{ij}$ if $i$ -th person is not in the same team as j-th person else $0$ )

### 输入描述

The first line of input contains an integers $N$ .

Following $2N$ lines each contains $2N$ space-separated integers $v_{ij}$ is the j-th value of the i-th line which indicates the competitive value of person i and person j.

• $1 \leq N \leq 14$
• $0 \leq v_{ij} \leq 10^{9}$
• $v_{ij} = v_{ji}$

### 输出描述

Output one line containing an integer representing the maximum possible total competitive value.

### 题解

#### 解法

n不超过14，因此可以暴力枚举分组情况，对于每一种情况，计算当前情况的价值。

## G - Polygons

### 题目描述

Lines make polygons. Given $N$ lines, please tell how many closed polygons are formed by these $N$ straight lines and what is the largest and smallest area of them? Moreover, could you tell $q_i$ -th largest area?

### 输入描述

The first line of input contains an integers $N$ indicating the number of lines.

Following $N$ lines each contains four space-separated integers $x_1, y_1, x_2, y_2$ ​ indicating two points on the i-th line.

The next line contains an integer $M$ indicating the number of questions.

Following $M$ lines each contains an integer $q_i$ ​.

• $3 \leq N \leq 1000$
• $1 \leq M \leq 10000$
• $|x_i|, |y_i| \leq 1000$
• $1 \leq q_i \leq 10^9$

No three lines intersect in one point

No two lines coincide

There is at least $1$ closed polygon

### 输出描述

First output a single line containing three numbers, the number of closed polygons, the largest area and the smallest area.

Then, output m lines each contains a number indicating $q_i$ ​-th largest area.

If $q_i$ ​ is greater than the number of polygons, output $\texttt{“Invalid question”}$ (without quotes) instead.

Your answer will be considered correct if its absolute or relative error doesn’t exceed $10^{-4}$

## H - Second Large Rectangle

### 题目描述

Given a $N \times M$ binary matrix. Please output the size of second large rectangle containing all $\texttt{“1”}$ .

Containing all $\texttt{“1”}$ means that the entries of the rectangle are all $\texttt{“1”}$ .

A rectangle can be defined as four integers $x_1, y_1, x_2, y_2$ where $1 \leq x_1 \leq x_2 \leq N$ and $1 \leq y_1 \leq y_2 \leq M$ . Then, the rectangle is composed of all the cell $(x, y)$ where $x_1 \leq x \leq x_2$ and $y_1 \leq y \leq y2$ . If all of the cell in the rectangle is $\texttt{“1”}$ , this is a valid rectangle.

Please find out the size of the second largest rectangle, two rectangles are different if exists a cell belonged to one of them but not belonged to the other.

### 输入描述

The first line of input contains two space-separated integers $N$ and $M$ .

Following $N$ lines each contains $M$ characters $c_{ij}$ ​.

• $1 \leq N, M \leq 1000$
• $N \times M \geq 2$
• $c_{ij} \in \texttt{“01”}$

### 输出描述

Output one line containing an integer representing the answer. If there are less than $2$ rectangles containning all $\texttt{“1”}$ , output $\texttt{“0”}$ .

## I - Inside A Rectangle

### 题目描述

Given $N \times M$ grid, each cell has a value $a_{ij}$ , you can choose at most two rectangles such that sum of values of the cell belonging to $\textbf{exactly}$ one rectangle is maximized.

A rectangle can be defined as four integers $x_1, y_1, x_2, y_2$ where $1 \leq x_1 \leq x_2 \leq N$ and $1 \leq y_1 \leq y_2 \leq M$ . Then, the rectangle is composed of all the cell $(x, y)$ where $x_1 \leq x \leq x_2$ and $y_1 \leq y \leq y2$ .

After choosing the rectangles, the resulting value will be the sum of values of the cell belonging to $\textbf{exactly}$ one of them.

### 输入描述

The first line of input contains two space-separated integers $N$ and $M$ .

Following N lines each contains M space-separated integers $a_{ij}$ ​.

• $1 \leq N, M \leq 50$
• $-10^5 \leq a_{ij} \leq 10^5$

### 输出描述

Output one line containing an integer representing the answer.

## J - Subarray

### 题目描述

Given an array A of length $10^9$ containing only $1$ and $-1$ . The number of 1 is not more than $10^7$ .
Please count how many pairs of $(l, r)$ satisfy $\sum\limits_{i=l}^r A_i > 0$ and $0 \leq l \leq r < 10^9$ .

### 输入描述

The first line of input contains an integers $N$ indicating how many segments of $A$ is $1$ .
Following $N$ lines each contains two space-separated integers $l_i, r_i$ ​ indicating that $A_j$ ​ is $1$ for $l_i \leq j \leq r_i$ ​

• $0 < n \leq 10^6$
• $l_i \leq r_i$
• $r_i + 1 < l_{i+1}$ for $0 \leq i < n - 1$
• $0 \leq l_0$
• $r_{n-1} < 10^9$
• $\sum (r_i - l_i + 1) \leq 10^7$

### 输出描述

Output one line containing an integer representing the answer.

### 题解

#### 解法

• $f_{i} = max(0,f_{i-1}-(l_{i}-r_{i-1}-1))+r_{i}-l_{i}+1$
• $g_{i} = max(0,g_{i+1}-(l_{i+1}-r_{i}-1))+r_{i}-l_{i}+1$