Theme NexT works best with JavaScript enabled

## A - The power of Fibonacci

### 题目描述

Let $Fi$ be fibonacci number.

$F_0 = 0, F_1 = 1, F_i = F_{i-1} + F_{i-2}$

Given n and m, please calculate $\sum_{i = 0}^n F_i^m$

As the answer might be very large, output it module $1000000000$ .

### 输入描述

The first and only line contains two integers $n, m(1 \leq n \leq 1000000000, 1 \leq m \leq 1000)$ .

### 输出描述

Output a single integer, the answer module $1000000000$ .

### 示例1

#### 说明

$0^5 + 1^5 + 1^5 + 2^5 + 3^5 + 5^5 = 3402$

### 示例2

#### 说明

Don’t forget to mod $1000000000$

### 示例3

#### 说明

Time is precious.

### 题解

#### 解法

$10^9 = 2^9 \times 5^9$ ，可以拆分为 $512$ 和 $1953125$ 。这样可以知道斐波那契数列分别在模 $512$ 和 $1953125$ 意义下的循环节，易知两循环节分别为 $768$ 和 $7812500$ 。

### 题目描述

Let p = $1000000007$ .

Given two integers $b$ and $c$ , please find two integers $x$ and $y$ $(0 \leq x \leq y < p)$ , such that

$(x + y) \bmod p = b$

$(x \times y) \bmod p = c$

### 输入描述

The first line contains an integer $t$ , which is the number of test cases ( $1 \leq t \leq 10$ ).

In the following $t$ lines, each line contains two integers $b$ and $c$ ( $0 \leq b, c < p$ ).

### 输出描述

For each test case, please output $x, y$ in one line.

If there is a solution, because $x \leq y$ , the solution is unique.

If there is no solution, please output -1, -1 .

## C - Inversions of all permutations

### 题目描述

Given an array $a_i$ with length $n$ , and $a$ base $b$ .

For each permutation $\{ r_i \}$ of $\{ a_i \}$ , we count the number of inversions as $t ( \{ r_i \} )$ .

Please calculate $\sum_{\{r_i\} \text{is a permutation of} \{a_i\}} b^{t(\{r_i\})}$

As the answer might be very large, please output it modulo $1000000007$ .

### 输入描述

The first line contains $n, b (n \leq 100000, 1 \leq b \leq 1000000000)$ .

The second line contains $n$ integers, which are $a_i (0 \leq a_i \leq 100000)$ .

### 输出描述

Output the answer in one line.

As the answer might be very large, please output it modulo $1000000007$ .

### 示例1

#### 说明

There are $6$ permutations. The number of inversions are $0, 1, 1, 2, 2, 3$ .

### 示例2

#### 说明

There are $6$ permutations. The number of inversions are $0, 1, 2, 2, 3, 4$ .

If there are duplicate integers in $\{ a_i \}$ , the number of permutations are less than the factorial of $n$ ( $n!$ ).

### 示例3

#### 说明

Don’t forget to mod $1000000007$ .

## D - Knapsack Cryptosystem

### 题目描述

Given an array $\{ a_i \}$ with length $n$ , and the sum $s$ .

Please find a subset of $\{ a_i \}$ , such that the sum of the subset is $s$ .

https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem
https://blog.nowcoder.net/n/66ec16042de7421ea87619a72683f807

Because of some reason, you might not be able to open Wikipedia.

Whether you read it or not, this problem is solvable.

### 输入描述

The first line contains two integers, which are $n$ ( $1 \leq n \leq 36$ ) and $s$ ( $0 \leq s < 9e18$ )

The second line contains n integers, which are $\{ a_i \}$ ( $0 < a_i < 2e17$ ).

$\{ a_i \}$ is generated like in the Merkle–Hellman knapsack cryptosystem, so there exists a solution and the solution is unique.

Also, according to the algorithm, for any subset sum s, if there exists a solution, then the solution is unique.

### 输出描述

Output a $01$ sequence.

If the $i$ -th digit is $1$ , then $a_i$ is in the subset.

If the $i$ -th digit is $0$ , then $a_i$ is not in the subset.

### 示例1

#### 说明

This is the example in Wikipedia.

## E - All men are brothers

### 题目描述

There are $n$ people, who don’t know each other at the beginning.

There are m turns. In each turn, $2$ of them will make friends with each other.

The friend relation is mutual and transitive.

If A is a friend of B, then B is also a friend of A.

For example, if A is a friend of B, B is a friend of C, then A and C are friends.

At the beginning and after each turn, please calculate the number of ways to select four people from, such that any two of these four are not friends.

### 输入描述

The first line contains two integers, $n$ and $m$ ( $n \leq 100000, m \leq 200000$ ), which are the number of people, and the number of turns.

In the following $m$ lines, the $i$ -th line contains two integers $x$ and $y$ ( $1 \leq x \leq n, 1 \leq y \leq n, x \neq y$ ), which means the $x$ -th person and the $y$ -th person make friends in the $i$ -th turn.

The $x$ -th person and $y$ -th person might make friends in several turns.

### 输出描述

Output $m+1$ lines, each line contains an integer, which is the number of quadruples.

Output at the beginning and after each turn, so there are $m+1$ lines.

Don’t use int.

## F - Birthday Reminders

### 题目描述

Today is Tomori’s birthday! Usually, people get many birthday wishes on social media, but Tomori has decided to hide her birthday on social media, and thus does not expect many (if any) wishes from her friends.

Tomori has N friends. Some of the friends actually remembered her birthday! For each friend iii, he or she will remember Tomori’s birthday at time $t_i$ and give her a birthday wish at that instant (or not remember her birthday at all if $t_i = -1$ ).

Some of Tomori’s friends are very considerate however, and decides to remind others about her birthday. Friend $i$ will remind friend $p_i$ about Tomori’s birthday after he or she has wished her. Formally, if Friend $i$ gave Tomori a birthday wish at time $t$ , then he or she will remind friend $p_i$ to give Tomori a birthday wish at time $t+1$ (and friend $p_i$ will give her a birthday wish at time $t+1$ and remind friend $p_{p_i}$ at time $t+2$ and so on, assuming that they have not already gave her a birthday wish). The sequence $p_i$ forms a permutation, i.e. each friend will be reminded by exactly one friend. Note that $p_i = i$ is possible, which means that the friend will not remind anyone about Tomori’s birthday after sending their wish.

The day is over and at the end of the day, Tomori receives the wish from Friend i at time $b_i$ (if $b_i = -1$ , it means that friend $i$ never wished her for her birthday). Note that $b_i$ might not be equal to $t_i$ as he or she might be reminded by another friend at an earlier time.

Tomori receives the wishes, but she actually can’t distinguish between her friends, so she only knows the number of wishes she received at each particular time. Now, she wonders, over all possible permutations $\{ p_i \}$ , how many possible different days she could have experienced. Two permutations $p, q$ correspond to different days if at some point of time, the number of friends who wished Tomori was different.

### 输入描述

The first line of input contains a single integer $N$ ( $1 \leq N \leq 100$ ).

The next line of input contains N space-separated integers, the i-th of which denotes $t_i$ ( $t_i = -1$ or $1 \leq ti \leq 100$ ).

### 输出描述

Output a single integer, the number of different days Tomori could have experienced. Since the answer might be too large, output it modulo $1000000007$ .

### 示例1

#### 说明

There are 6 possible permutations.

If $p = \{1, 2, 3\}$ , then $b = \{-1, 2, 1\}$ .

If $p = \{1, 3, 2\}$ , then $b = \{-1, 2, 1\}$ .

If $p = \{2, 1, 3\}$ , then $b = \{3, 2, 1\}$ .

If $p = \{2, 3, 1\}$ , then $b = \{2, 2, 1\}$ .

If $p = \{3, 1, 2\}$ , then $b = \{3, 2, 1\}$ .

If $p = \{3, 2, 1\}$ , then $b = \{2, 2, 1\}$ .

There are $3$ distinct possible days Tomori could have experienced.

Please note that even if we have $b = \{1, 2, 2\}$ with some permutation, it is considered the same as $b = \{2, 2, 1\}$ , since Tomori can’t distinguish between her friends.

## G - Checkers

### 题目描述

There are $N$ black checker pieces on the coordinate plane. The $i$ -th checker piece is located at point $(X_{i}, Y_{i})$ . You are playing a new type of game with these checker pieces.

A move is defined as follows :

Place a white checker piece $W$ at some coordinate $(2x, y)$ where $x, y$ are integers. While there exist a black checker piece $B$ at distance exactly $1$ from $W$ , you may choose to capture $B$ by moving $W$ to the symmetric point of its current position with respect to $B$ , and remove $B$ . Note that multiple checker pieces may occupy the same point at the same time. Once no such operation is possible or you choose to stop performing such operation, W is removed.

Each black checker piece has a $\frac{1}{2}$ probability of getting removed before the game starts. What is the expected minimum number of moves required to complete the game? Let E be this expected value. It can be proven that $E \cdot 2^{N}$ is an integer. Output $E \cdot 2^{N} \bmod 1000000007$

### 输入描述

The first line of input contains a single integer $N$ ( $1 \leq N \leq 600$ ).

The next $N$ lines contains $2$ space-separated integers $X_i, Y_i$ ( $0 \leq X_i \leq 99, 0 \leq Y_i \leq 5$ ), denoting the coordinates of the checker pieces.

### 输出描述

Output a single integer, the value of $E \cdot 2^{N} \bmod 1000000007$ .

## H - Cutting Bamboos

### 题目描述

There are $n$ bamboos arranged in a line. The $i$ -th bamboo from the left has height $h_{i}$ .

You are given $q$ queries of the type $(l, r, x, y)$ . For each query $(l, r, x, y)$ we consider only the $l$ -th to $r$ -th bamboo inclusive. We want to make $y$ horizontal cuts through these bamboos, such that after each cut, the total length of bamboo cut is the same, and after all $y$ cuts there is no bamboo left. For example, if there are $3$ bamboos of height $3, 4, 5$ respectively and $y = 4$ . The first cut should be at height $3$ , after which the heights of the bamboos are $3, 3, 3$ respectively and the total amount of bamboo cut is $0 + 1 + 2 = 3$ . Then, the next $3$ cuts should be at height $2, 1, 0$ respectively. You want to find out what is the height the $x$ -th cut is performed.

Note that after each query, the bamboos are not actually cut, so the heights of the bamboos remain constant after each query.

### 输入描述

The first line of input contains two space-separated integers $n, q$ ( $1 \leq n \leq 200000, 1 \leq q \leq 100000$ ).

The next line of input contains $n$ space-separated integers, the $i$ -th of which denotes $h_i$ , the height of the $i$ -th bamboo ( $1 \leq h_i \leq 100000$ ).

The next $q$ lines of input contains $4$ space-separated integers each, denoting $l, r, x, y$ ( $1 \leq l \leq r \leq n, 1 \leq x \leq y \leq 10^9$ ).

### 输出描述

Output q lines of real numbers, the $i$ -th line contains the answer to the $i$ -th query. Your answer will be accepted if its absolute or relative error is less than $10^{-6}$ .

### 示例1

#### 说明

For the first query, we only consider the bamboos of height $5, 1, 7$ .

The first cut should be at height $4.7$ , the total amount of bamboo obtained is $0.3 + 0 + 2.3 = 2.6$ .

The second cut should be at height $3.4$ , the total amount of bamboo obtained is $1.3 + 0 + 1.3 = 2.6$ .

The third cut should be at height $2.1$ , the total amount of bamboo obtained is $1.3 + 0 + 1.3 = 2.6$ .

The fourth cut should be at height $\dfrac{13}{15}$ , the total amount of bamboo obtained is $\dfrac{37}{30} + \dfrac{2}{15} + \dfrac{37}{30} = 2.6$ .

The fifth cut should be at height $0$ , the total amount of bamboo obtained is $\dfrac{13}{15} + \dfrac{13}{15} + \dfrac{13}{15} = 2.6$ .

Note that the output values are not exact, but are within the precision requirements.

## I - KM and M

### 题目描述

Find the value of $\displaystyle\sum_{k = 1}^{N} ((kM) \& M) \bmod (10^{9} + 7)k=1$ ，where $\&$ denotes the bitwise AND operator.

### 输入描述

The first and only line of input contains two space-separated integers $N, M$ ( $1 \leq N \leq 10^18, 1 \leq M \leq 10^11$ ).

### 输出描述

Output a single integer, the answer to the problem.

### 示例1

#### 说明

The sum is $6 + 4 + 2 + 0 = 12$ .

## J - Symmetrical Painting

### 题目描述

Initially, the entire coordinate plane is colored white.

$N$ rectangles were painted black. The $i$ -th rectangle has bottom-left corner $(i-1, L_i)$ and top-right corner $(i,R_i)$ for $1 \le i \le n$ . You want to paint some of the black area white so that the remaining black part has a horizontal axis of symmetry. Find the maximum possible area of the remaining black part.

### 输入描述

The first line of input contains a single integer $N$ ( $1 \leq N \leq 300000$ ), denoting the number of rectangles.

The next $N$ lines of input contain two space-separated integers each, denoting $L_i, R_i$ ( $1 \leq Li < Ri \leq 10^9$ ).

### 输出描述

Output a single integer, the answer to the problem.

### 示例1

#### 说明

It is optimal to paint second rectangle entirely white and a rectangle with bottom-left corner $(0, 4)$ and top-right corner $(1, 5)$ white. Then, the remaining black figure has axis of symmetry at $y = 2.5$ . The remaining black area is $4$ .