## HDU 6053 TrickGCD 容斥 DFS 分段快速查询

http://acm.hdu.edu.cn/showproblem.php?pid=6053

# TrickGCD

Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)

### Problem Description

You are given an array $A$ , and Zhu wants to know there are how many different array $B$ satisfy the following conditions?
* $1\leq B_{i} \leq A_{i}$
* For each pair( l , r ) ($1 \leq l \leq r \leq n$) , $gcd( b_{l} , b_{l+1} ... b_{r} )\ge 2$

### Input

The first line is an integer T($1 \leq T \leq 10$) describe the number of test cases.
Each test case begins with an integer number n describe the size of array $A$.
Then a line contains $n$ numbers describe each element of $A$
You can assume that $1 \leq n , A_{i} \leq 10^5$

### Output

For the $k$th test case , first output "Case #k: " , then output an integer as answer in a single line . because the answer may be large , so you are only need to output answer $mod$ $10^9+7$

1
4
4 4 4 4

Case #1: 17

## HDU 6052 To my boyfriend 询问分块 容斥 单调栈

http://acm.hdu.edu.cn/showproblem.php?pid=6052

# To my boyfriend

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

### Problem Description

Dear Liao
I never forget the moment I met with you. You carefully asked me: "I have a very difficult problem. Can you teach me?". I replied with a smile, "of course". You replied:"Given a matrix, I randomly choose a sub-matrix, what is the expectation of the number of **different numbers** it contains?"
Sincerely yours,
Guo

### Input

The first line of input contains an integer T(T≤8) indicating the number of test cases.
Each case contains two integers, n and m (1≤n, m≤100), the number of rows and the number of columns in the grid, respectively.
The next n lines each contain m integers. In particular, the j-th integer in the i-th of these rows contains g_i,j (0≤ g_i,j < n*m).

### Output

Each case outputs a number that holds 9 decimal places.

1
2 3
1 2 1
2 1 2

### Sample Output

1.666666667

Hint

6(size = 1) + 14(size = 2) + 4(size = 3) + 4(size = 4) + 2(size = 6) = 30 / 18 = 6(size = 1) + 7(size = 2) + 2(size = 3) + 2(size = 4) + 1(size = 6)

## HDU 6050 Funny Function 矩阵快速幂 矩阵变化

http://acm.hdu.edu.cn/showproblem.php?pid=6050

# Funny Function

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

### Problem Description

Function $F_{x,y}$satisfies:

For given integers N and M,calculate $F_{m,1}$ modulo 1e9+7.
Input
There is one integer T in the first line.
The next T lines,each line includes two integers N and M .
1<=T<=10000,1<=N,M<2^63.
Output
For each given N and M,print the answer in a single line.

2
2 2
3 3

2
33

### 思路

$$F_j = Sum_{n+1} - F_1$$
$$F_{j-1} = Sum_{n+1} - F_n$$
$$Sum_j = 2* Sum_{n+1} - F_1 - F_n$$
$$F_1 = Sum_{n+1} - F_n$$

## HDU 6047 Maximum Sequence 贪心 优先队列

http://acm.hdu.edu.cn/showproblem.php?pid=6047

# Maximum Sequence

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

### Problem Description

Steph is extremely obsessed with “sequence problems” that are usually seen on magazines: Given the sequence 11, 23, 30, 35, what is the next number? Steph always finds them too easy for such a genius like himself until one day Klay comes up with a problem and ask him about it.
Given two integer sequences {ai} and {bi} with the same length n, you are to find the next n numbers of {ai}: $a_{n+1}…a_{2n}$. Just like always, there are some restrictions on $a_{n+1}…a_{2n}$: for each number $a_i$, you must choose a number $b_k$ from {bi}, and it must satisfy $a_i$≤max{$a_j$-j│$b_k$≤j<i}, and any $b_k$ can’t be chosen more than once. Apparently, there are a great many possibilities, so you are required to find max{$\sum_{n+1}^{2n}a_i$} modulo $10^9$+7 .

### Input

The input contains no more than 20 test cases.
For each test case, the first line consists of one integer n. The next line consists of n integers representing {ai}. And the third line consists of n integers representing {bi}.
1≤n≤250000, n≤a_i≤1500000, 1≤b_i≤n.

### Output

For each test case, print the answer on one line: max{$\sum_{n+1}^{2n}a_i$} modulo $10^9$+7。

### Sample Output

Hint

For the first sample: 1. Choose 2 from {bi}, then a_2…a_4 are available for a_5, and you can let a_5=a_2-2=9; 2. Choose 1 from {bi}, then a_1…a_5 are available for a_6, and you can let a_6=a_2-2=9;

## HDU 6044 Limited Permutation DFS计算方案数

http://acm.hdu.edu.cn/showproblem.php?pid=6044

# Limited Permutation

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

### Problem Description

As to a permutation $p_1, p_2, \cdots, p_n$ from $1$ to $n$, it is uncomplicated for each $1 \leq i \leq n$ to calculate $(l_i, r_i)$ meeting the condition that $\min(p_L, p_{L + 1}, \cdots, p_R) = p_i$ if and only if $l_i \leq L \leq i \leq R \leq r_i$ for each $1 \leq L \leq R \leq n$.
Given the positive integers $n$, $(l_i, r_i)$ $(1 \leq i \leq n)$, you are asked to calculate the number of possible permutations $p_1, p_2, \cdots, p_n$ from $1$ to $n$, meeting the above condition.
The answer may be very large, so you only need to give the value of answer modulo $10^9 + 7$.

### Input

The input contains multiple test cases.
For each test case:
The first line contains one positive integer $n$, satisfying $1 \leq n \leq 10^6$.
The second line contains $n$ positive integers $l_1, l_2, \cdots, l_n$, satisfying $1 \leq l_i \leq i$ for each $1 \leq i \leq n$.
The third line contains $n$ positive integers $r_1, r_2, \cdots, r_n$, satisfying $i \leq r_i \leq n$ for each $1 \leq i \leq n$.
It's guaranteed that the sum of $n$ in all test cases is not larger than $3 \cdot 10^6$.
Warm Tips for C/C++: input data is so large (about 38 MiB) that we recommend to use fread() for buffering friendly.

### Output

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 of corresponding case.

3
1 1 3
1 3 3
5
1 2 2 4 5
5 2 5 5 5

Case #1: 2
Case #2: 3

## HDU 6036 I Curse Myself 仙人掌的最小生成树

http://acm.hdu.edu.cn/showproblem.php?pid=6041

# I Curse Myself

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

### Problem Description

There is a connected undirected graph with weights on its edges. It is guaranteed that each edge appears in at most one simple cycle.
Assuming that the weight of a weighted spanning tree is the sum of weights on its edges, define $V(k)$ as the weight of the $k$-th smallest weighted spanning tree of this graph, however, $V(k)$ would be defined as zero if there did not exist $k$ different weighted spanning trees.
Please calculate $\displaystyle\left(\sum_{k=1}^{K}{k \cdot V(k)}\right) \bmod 2^{32}$.

### Input

The input contains multiple test cases.
For each test case, the first line contains two positive integers $n, m$ $(2 \leq n \leq 1000, n-1 \leq m \leq 2n-3)$, the number of nodes and the number of edges of this graph.
Each of the next $m$ lines contains three positive integers $x, y, z$ $(1 \leq x, y \leq n, 1 \leq z \leq 10^6)$, meaning an edge weighted $z$ between node $x$ and node $y$. There does not exist multi-edge or self-loop in this graph.
The last line contains a positive integer $K$ $(1 \leq K \leq 10^5)$.

### Output

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 of corresponding case.
Sample Input

## HDU6040 Hints of sd0061 分治排序

http://acm.hdu.edu.cn/showproblem.php?pid=6040

# Hints of sd0061

Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

### Problem Description

sd0061, the legend of Beihang University ACM-ICPC Team, retired last year leaving a group of noobs. Noobs have no idea how to deal with $m$ coming contests. sd0061 has left a set of hints for them.
There are $n$ noobs in the team, the $i$-th of which has a rating $a_i$. sd0061 prepares one hint for each contest. The hint for the $j$-th contest is a number $b_j$, which means that the noob with the $(b_j + 1)$-th lowest rating is ordained by sd0061 for the $j$-th contest.
The coach asks constroy to make a list of contestants. constroy looks into these hints and finds out: $b_i + b_j \leq b_k$ is satisfied if $b_i \neq b_j,$ $b_i < b_k$ and $b_j < b_k$.
Now, you are in charge of making the list for constroy.

### Input

There are multiple test cases (about $10$).
For each test case:
The first line contains five integers $n, m, A, B, C$. $(1 \leq n \leq 10^7, 1 \leq m \leq 100)$
The second line contains $m$ integers, the $i$-th of which is the number $b_i$ of the $i$-th hint. $(0 \leq b_i < n)$
The $n$ noobs' ratings are obtained by calling following function $n$ times, the $i$-th result of which is $a_i$.

### Output

For each test case, output "Case #$x$: $y_1$ $y_2$ $\cdots$ $y_m$" in one line (without quotes), where $x$ indicates the case number starting from $1$ and $y_i$ $(1 \leq i \leq m)$ denotes the rating of noob for the $i$-th contest of corresponding case.

## HDU 6039 Gear Up 并查集 dfs序 线段树

http://acm.hdu.edu.cn/showproblem.php?pid=6039

# Gear Up

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

### Problem Description

constroy has some gears, each with a radius. Two gears are considered adjacent if they meet one of the following conditions:
1. They share a common edge (i.e. they have equal linear velocity).
2. They share a common shaft (i.e. they have equal angular velocity).
It is guaranteed that no pair of gears meets both of the above conditions.
A series of continuous adjacent gears constitutes a gear path. There is at most one gear path between each two gears.
Now constroy assigns an angular velocity to one of these gears and then asks you to determine the largest angular velocity among them.
sd0061 thinks this problem is too easy, so he replaces some gears and then asks you the question again.

### Input

There are multiple test cases (about $30$).
For each test case:
The first line contains three integers $n, m, q$, the number of gears, the number of adjacent pairs and the number of operations. $(0 \leq m < n \leq 10^5, 0 \leq q \leq 10^5)$
The second line contains $n$ integers, of which the $i$-th integer represents $r_i$, the radius of the $i$-th gear. $(r_i \in \{2^\lambda \mid 0 \leq \lambda \leq 30\})$
Each of the next $m$ lines contains three integers $a, x, y$, the $x$-th gear and the $y$-th gear are adjacent in the $a$-th condition. $(a \in \{1, 2\}, 1 \leq x, y \leq n, x \neq y)$
Each of the next $q$ line contains three integers $a, x, y$, an operation ruled in the following: $(a \in \{1, 2\}, 1 \leq x \leq n, y \in \{2^\lambda \mid 0 \leq \lambda \leq 30\})$
$a = 1$ means to replace the $x$-th gear with another one of radius $y$.
$a = 2$ means to assign angular velocity $y$ to the $x$-th gear and then determine the maximum angular velocity.

### Output

For each test case, firstly output "Case #$x$:" in one line (without quotes), where $x$ indicates the case number starting from $1$, and then for each operation of $a = 2$, output in one line a real number, the natural logarithm of the maximum angular velocity, with the precision of $3$ digits.

## HDU 6038 Function 循环节 方案数

http://acm.hdu.edu.cn/showproblem.php?pid=6038

# Function

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

### Problem Description

You are given a permutation $a$ from $0$ to $n - 1$ and a permutation $b$ from $0$ to $m - 1$.
Define that the domain of function $f$ is the set of integers from $0$ to $n - 1$, and the range of it is the set of integers from $0$ to $m - 1$.
Please calculate the quantity of different functions $f$ satisfying that $\displaystyle f(i) = b_{f(a_i)}$ for each $i$ from $0$ to $n - 1$.
Two functions are different if and only if there exists at least one integer from $0$ to $n - 1$ mapped into different integers in these two functions.
The answer may be too large, so please output it in modulo $10^9 + 7$.

### Input

The input contains multiple test cases.
For each case:
The first line contains two numbers $n,$ $m$. $(1 \leq n \leq 100000, 1 \leq m \leq 100000)$
The second line contains $n$ numbers, ranged from $0$ to $n - 1$, the $i$-th number of which represents $a_{i - 1}$.
The third line contains $m$ numbers, ranged from $0$ to $m - 1$, the $i$-th number of which represents $b_{i - 1}$.
It is guaranteed that $\sum{n} \leq 10^6,$ $\sum{m} \leq 10^6$.

### Output

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 of corresponding case.

3 2
1 0 2
0 1
3 4
2 0 1
0 2 3 1

Case #1: 4
Case #2: 4

### 思路

$f(i) = b_{f(a_i)} = b_{b_{f(a_{a_i})}} = \underbrace{b_{\cdots b_{f(i)}}}_{l\text{ times }b}$

## HDU6035 Colorful Tree DFS + 统计对答案的贡献

http://acm.hdu.edu.cn/showproblem.php?pid=6035

# Colorful Tree

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

### Problem Description

There is a tree with $n$ nodes, each of which has a type of color represented by an integer, where the color of node $i$ is $c_i$.
The path between each two different nodes is unique, of which we define the value as the number of different colors appearing in it.
Calculate the sum of values of all paths on the tree that has $\frac{n(n-1)}{2}$ paths in total.

### Input

The input contains multiple test cases.
For each test case, the first line contains one positive integers $n$, indicating the number of node. $(2 \leq n \leq 200000)$
Next line contains $n$ integers where the $i$-th integer represents $c_i$, the color of node $i$. $(1 \leq c_i \leq n)$
Each of the next $n - 1$ lines contains two positive integers $x, y$ $(1 \leq x, y \leq n, x \neq y)$, meaning an edge between node $x$ and node $y$.
It is guaranteed that these edges form a tree.

### Output

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 of corresponding case.

### 思路

PS：栈的容器类型需要换成vector，开$10^5$个栈会直接MLE的