Theme NexT works best with JavaScript enabled

## A - Equivalent Prefixes

### 题目描述

Two arrays $u$ and $v$ each with m distinct elements are called equivalent if and only if $\mathrm{RMQ}(u, l, r) = \mathrm{RMQ}(v, l, r)$ for all $1 \leq l \leq r \leq m$

where $\mathrm{RMQ}(w, l, r)$ denotes the index of the minimum element among $w_l, w_{l + 1}, \dots, w_{r}$ .

Since the array contains distinct elements, the definition of minimum is unambiguous.

Bobo has two arrays a and b each with n distinct elements. Find the maximum number $p \leq n$ where $\{a_1, a_2, \dots, a_p\}$ and $\{b_1, b_2, \dots, b_p\}$ are equivalent.

### 输入描述

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains an integer n.

The second line contains n integers $a_1, a_2, \dots, a_n$ .

The third line contains n integers $b_1, b_2, \dots, b_n$ .

• $1 \leq n \leq 10^5$
• $1 \leq a_i, b_i \leq n$
• $\{a_1, a_2, \dots, a_n\}$ are distinct.
• $\{b_1, b_2, \dots, b_n\}$ are distinct.
• The sum of n does not exceed $5 \times 10^5$ .

### 输出描述

For each test case, print an integer which denotes the result.

## B - Integration

### 题目描述

Bobo knows that $\displaystyle\int_{0}^{\infty} \dfrac{1}{1 + x^2}\ \mathrm{d}x = \frac{\pi}{2}$ .

Given n distinct positive integers $a_1, a_2, \dots, a_n$ , find the value of $\displaystyle\frac{1}{\pi} \int_{0}^{\infty} \frac{1}{\prod_{i = 1}^n(a_i^2 + x^2)}\ \mathrm{d}x$ .

It can be proved that the value is a rational number $\dfrac{p}{q}$ .
Print the result as $(p \cdot q^{-1}) \bmod (10^9+7)$ .

### 输入描述

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains an integer $n$ .
The second line contains n integers $a_1, a_2, \dots, a_n$ .

• $1 \leq n \leq 10^3$
• $1 \leq a_i \leq 10^9$
• $\{a_1, a_2, \dots, a_n\}$ are distinct.
• The sum of $n^2$ does not exceed $10^7$ .

### 输出描述

For each test case, print an integer which denotes the result.

### 题解

#### 解法

• 令 $\displaystyle c_{i} = \dfrac{1}{\prod_{j \neq j}(a_{j}^2-a_{i}^2)}$
• 则 $\displaystyle\dfrac{1}{\prod_{j \neq j}(a_{i}^2 + x) } = \sum \dfrac{c_{i}}{a_{i}^2+x}$
• 所以 $\displaystyle\int_{0}^{\infty} \dfrac{c_{i}}{a_{i}^2+x} dx = \dfrac{c_{i}}{2 \times a_{i}} \times \pi$
• 所以 $\displaystyle\frac{1}{\pi} \int_{0}^{\infty} \frac{1}{\prod_{i = 1}^n(a_i^2 + x^2)}\ \mathrm{d}x = \sum\dfrac{c_{i}}{2 \times a_{i}}$

## C - Euclidean Distance

### 题目描述

Bobo has a point $A$ in the $n$ dimension real space $\mathbb{R}^n$ , whose coodinate is $(a_1 / m, a_2 / m, \dots, a_n / m)$ where $a_i$ and $m$ are both integers. He wants to find another point $P = (p_1, p_2, \dots, p_n)$ meeting the following requirements.

• $p_1, p_2, \dots, p_n \in \mathbb{R}$ . That is, they are real numbers.
• $p_1, p_2, \dots, p_n \geq 0$
• $p_1 + p_2 + \dots + p_n = 1$
• The (squared) Euclidean distance between P and A, which is $|A - P|_2^2 = \sum_{i = 1}^n (a_i / m - p_i)^2$ , is minimized.

It can be proved the minimum is always a rational number. Print the squared distance in fraction. Note to print an integer $n$ as n instead of n/1.

### 输入描述

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains two integers $n$ and $m$ .
The second line contains n integers $a_1, a_2, \dots, a_n$ .

• $1 \leq n \leq 10^4$
• $1 \leq m \leq 10^3$
• $-m \leq a_i \leq m$
• The sum of n does not exceed $5 \times 10^5$ .

### 输出描述

For each test case, print a fraction which denotes the result.

### 题解

#### 题意

• $p_1,p_2 \dots p_n$ 都是实数
• $p_i\geq 0$
• $p_1+p_2+\dots +p_n=1$
• $\displaystyle \sum\limits_{i=1}^{n}(\frac{a_i}{m}-p_i)^2$ 尽可能小

## D - Parity of Tuples

### 题目描述

Bobo has n m-tuple $v_1, v_2, \dots, v_n$ , where $v_i = (a_{i, 1}, a_{i, 2}, \dots, a_{i, m})$ . He wants to find $\mathrm{count}(x)$ which is the number of $v_i$ where $a_{i, j} \wedge x$ has odd number of ones in its binary notation for all $j$ . Note that $\wedge$ denotes the bitwise-and.

Print $\bigoplus_{x = 0}^{2^k - 1} \left(\mathrm{count}(x) \cdot 3^x \bmod (10^9+7)\right)$ for given $k$ , where $\oplus$ denotes bitwise-xor.

### 输入描述

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains three integers $n$ , $m$ and $k$ .
The ith of the following $n$ lines contains $m$ integers $a_{i, 1}, a_{i, 2}, \dots, a_{i, m}$ .

• $1 \leq n \leq 10^5$
• $1 \leq m \leq 10$
• $1 \leq k \leq 20$
• $0 \leq a_{i, j} < 2^k$
• There is exactly one test case with $n = 10^5$ , $m = 10$ and $k = 20$ . The other $300$ test cases have $n \leq 10^3$ , $m \leq 4$ and $k \leq 10$ .

### 输出描述

For each test case, print an integer which denotes the result.

## E - ABBA

### 题目描述

Bobo has a string of length $2(n + m)$ which consists of characters A and B. The string also has a fascinating property it can be decomposed into $(n + m)$ subsequences of length $2$ , and among the $(n + m)$ subsequences $n$ of them are AB while other m of them are BA.

Given n and m, find the number of possible strings modulo $(10^9+7)$ .

### 输入描述

The input consists of several test cases and is terminated by end-of-file.

Each test case contains two integers n and m.

• $0 \leq n, m \leq 10^3$
• There are at most $2019$ test cases, and at most $20$ of them has $\max\{n, m\} > 50$ .

### 输出描述

For each test case, print an integer which denotes the result.

### 题解

#### 解法

$dp$ 的边界是我们在前 $n$ 个位置可以直接放 $A$ ，也可以在前 $m$ 个位置直接放 $B$ 。

## F - Random Point in Triangle

### 题目描述

Bobo has a triangle ABC with $A(x_1, y_1), B(x_2, y_2)$ and $C(x_3, y_3)$ . Picking a point $P$ uniformly in triangle $ABC$ , he wants to know the expectation value $E = \max\{S_{PAB}, S_{PBC}, S_{PCA}\}$ where $S_{XYZ}$ denotes the area of triangle $XYZ$ .

Print the value of $36 \times E$ . It can be proved that it is always an integer.

### 输入描述

The input consists of several test cases and is terminated by end-of-file.

Each test case contains six integers $x_1, y_1, x_2, y_2, x_3, y_3$ .

• $|x_1|, |y_1|, |x_2|, |y_2|, |x_3|, |y_3| \leq 10^8$
• There are at most $10^5$ test cases.

### 输出描述

For each test case, print an integer which denotes the result.

## G - Substrings 2

### 题目描述

Two strings $u_1 u_2 \dots u_k$ and $v_1 v_2 \dots v_l$ are isomorphic if and only if $k = l$ and there exists a injection $\phi$ such that $u_i = \phi(v_i)$ for all $i \in \{1, 2, \dots, k\}$ .
Note that a function f is injection if and only if $f(x) \neq f(y)$ for all $x \neq y$ .

Bobo would like to choose some strings from all $\dfrac{n(n + 1)}{2}$ substrings of the given string $s_1 s_2 \dots s_n$ .
Find out the maximum number of strings he may choose so that no two chosen strings are isomorphic.

### 输入描述

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains an integer n.
The second line contains a string $s_1, s_2, \dots, s_n$ .

• $1 \leq n \leq 5\times 10^4$
• $1 \leq s_i \leq n$
• There are at most $10^3$ test cases, and at most $5$ of them have $n > 50$ .

### 输出描述

For each test case, print an integer which denotes the result.

## H - XOR

### 题目描述

Bobo has a set A of n integers $a_1, a_2, \dots, a_n$ .

He wants to know the sum of sizes for all subsets of A whose xor sum is zero modulo $(10^9+7)$ .

Formally, find $\displaystyle\left( \displaystyle\sum{S \subseteq A, \oplus_{x \in S} x = 0} |S| \right) \bmod (10^9+7)$ . Note that $\oplus$ denotes the exclusive-or (XOR).

### 输入描述

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains an integer n.
The second line contains n integers $a_1, a_2, \dots, a_n$ ​.

• $1 \leq n \leq 10^5$
• $0 \leq a_i \leq 10^{18}$
• The number of test cases does not exceed $100$ .
• The sum of n does not exceed $2 \times 10^6$ .

### 输出描述

For each test case, print an integer which denotes the result.

### 题解

#### 解法

• 首先计算一次线性基 $R$ 。

• 对于每一个不在基底中的元素，它对答案的贡献为 $\displaystyle 2^{n-|R|-1}$ 。因为我们可以任取每一个不在基底中的元素组成一个数，线性基的特性保证基底中的数唯一的方案来表示这个数。而任取其他不在基底中的数的方案数有 $\displaystyle 2^{n-|R|-1}$ 种。
• 对于每一个在基底中的元素，首先把其余的 $n-1$ 个元素重新生成一个基底 $D$ ，如果该元素还是可以插入到基底 $D$ 中，那么就说明该元素对答案贡献为0，否则贡献为 $\displaystyle 2^{ n-|D|-1}$ 。
• 优化

• 每次生成 $D$ 的时间复杂度是 $\mathcal{O}(n)$ ，生成 $n$ 次的时间复杂度是 $\mathcal{O}(n^2)$ 。因此考虑优化时间复杂度，对于每个不在基底中的元素，建立一个基 $B$ ，每次将扔掉一个元素的基 $R$ 与基 $B$ 合并。

## I - Points Division

### 题目描述

Bobo has a set P of n distinct points $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$ .

The i-th point has two weights $a_i$ ​ and $b_i$ ​.

He wants to partition the points into two sets $A$ and $B$ (That is, $A \cup B = P$ and $A \cap B = \emptyset$ .

A partition (A, B) is valid if and only if there exists no $\in A$ and $j \in B$ where $x_i \geq x_j$ ​ and $y_i \leq y_j$ ​.

Find the maximum of $\left(\sum_{i \in A} a_i \right) + \left(\sum_{j \in B} b_j\right)$ among all valid partitions $(A, B)$ .

### 输入描述

The input consists of several test cases and is terminated by end-of-file.

The first line of each test cases contains an integer $n$ .

The i-th of the following $n$ lines contains four integers $x_i, y_i, a_i, b_i$ .

• $1 \leq n \leq 10^5$
• $1 \leq x_i, y_i, a_i, b_i \leq 10^9$
• $(x_i, y_i) \neq (x_j, y_j)$ for all $i \neq j$
• The sum of n does not exceed $5 \times 10^5$ .

### 输出描述

For each test case, print an integer which denotes the result.

## J - Fraction Comparision

### 题目描述

Bobo has two fractions $\frac{x}{a}$ and $\frac{y}{b}$ . He wants to compare them. Find the result.

### 输入描述

The input consists of several test cases and is terminated by end-of-file.

Each test case contains four integers $x, a, y, b$ .

• $0 \leq x, y \leq 10^{18}$
• $1 \leq a, b \leq 10^9$
• There are at most $10^5$ test cases.

### 输出描述

For each test case, print = if $\dfrac{x}{a} = \dfrac{y}{b}$ . Print < if $\dfrac{x}{a} < \dfrac{y}{b}$ . Print > otherwise.