## HDU 6155 Subsequence Count 线段树维护矩阵DP转移

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

$$dp[i][0] = dp[i-1][0] + dp[i-1][1] + 1$$

$$dp[i][1] = dp[i-1][1]$$

$$dp[i][0] = dp[i-1][0]$$

$$dp[i][1] = dp[i-1][0] + dp[i-1][1] + 1$$

$$\begin{bmatrix} dp[i+1][0]\\ dp[i+1][1]\\1 \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1\\ 0 & 1 &0\\0 & 0 & 1 \end{bmatrix}\begin{bmatrix} dp[i][0]\\ dp[i][1]\\1 \end{bmatrix}$$

$$\begin{bmatrix} dp[i+1][0]\\ dp[i+1][1]\\1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0\\ 1 & 0 &0\\0 & 0 & 1 \end{bmatrix}\begin{bmatrix} dp[i][0]\\ dp[i][1]\\1 \end{bmatrix}$$

## HDU 6153 A Secret KMP计数

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

## 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 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 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

## 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 6004 Periodical Cicadas 中国剩余定理 + 二维RMQ

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

Time Limit: 14000/7000 MS (Java/Others)    Memory Limit: 80000/80000 K (Java/Others)

### Problem Description

Nearly all cicadas spend years underground as juveniles, before emerging above ground for a short adult stage of several weeks to a few months.
The seven periodical cicada species are so named because, in any one location, all of the members of the population are developmentally synchronized they emerge as adults all at once every seven years.
The lifecycles of most periodical cicada species range from two to seventeen years, although some could be longer.
There is a forest which can be roughly divided into a matrix of size N ×M. The upper-left region is (1, 1) and the lower-right region is (N, M).
A population of periodical cicadas live within each region of the matrix. The population in region (i, j) emerged in year $a_{i,j}$ for the first time, and re-emerges every $b_{i,j}$ years. i.e. they are $b_{i,j}$ - periodical cicadas.
Given a selected rectangular area, entomologists wonder if there is a time when all cicadas in that area emerge together.

### Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test cases begin with two integers N and M.
The following N lines each consists of M integers $a_{i,j}$ representing the year cicadas emerged in region (i, j) for the first time.
The following N more lines each consists of M integers $b_{i,j}$ representing the periodical cycle of the cicadas in that region.
Then comes a line with an integer Q representing the number of queries. The following Q lines each consists of 4 integers: $x_1, y_1, x_2, y_2,$ representing the upper-left and lower-right coordinate of the selected rectangular area.

### Output

For each test case, first output one line containing “Case #x:”, where x is the test case number (starting from 1).
The following Q lines each consists of an integer which is the year when all cicadas in the selected area emerge together for the first time or -1 if it’s impossible.

### limits

$\bullet 1 ≤ T ≤ 10.$
$\bullet 1 ≤ N, M ≤ 200.$
$\bullet 0 ≤ a_{i,j} < b_{i,j} ≤ 40.$
$\bullet 1 ≤ x_1 ≤ x_2 ≤ N.$
$\bullet 1 ≤ y_1 ≤ y_2 ≤ M.$
$\bullet$ 1 ≤ Q ≤ 500000.

2
3 4
3 1 1 2
1 1 2 1
1 0 5 5
5 4 2 3
2 2 3 2
4 2 6 6
5
2 2 2 2
1 1 3 4
1 4 2 4
1 1 1 2
2 2 3 4
1 2
0 1
2 2
1
1 1 1 2

Case #1:
1
-1
5
13
-1
Case #2:
-1

## HDU5957 Query on a graph 基环树 + BFS序列 + 线段树区间维护

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

# Query on a graph

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

### Problem Description

You are given a connected simple graph(in which both multiple edges and loops are disallowed) with N nodes and N edges. In this graph each node has a weight, and each edge has the same length of one unit. Define D(u,v) as the distance between node u and node v. Define S(u,k) as the set of nodes x which satisfy D(u,x) ≤ k.
We will ask you to perform some instructions of the following forms.
MODIFY u k d: weight of all nodes in S(u,k) increase by d or decrease by -d.
QUERY u k: ask for the sum of weight of all nodes in S(u,k).
In the beginning, the weight of all nodes are 0.

### Input

The first line of input contains an integer t, the number of test cases. t test cases follow. For each test case, in the first line there is an integer N(N ≤ 100000). The i-th line of the next N line describes the i-th edge: two integers u,v denotes an edge between u and v. In the next line, an integer Q(Q ≤ 100000) indicates the number of instructions. Next Q lines contain instructions MODIFY u k d or QUERY u k, where |d|≤ 100 and 0 ≤ k ≤ 2.

### Output

For each QUERY instruction, output a integer in a line.

2
6
1 2
2 3
3 4
4 1
4 5
3 6
5
MODIFY 1 1 3
MODIFY 3 1 2
MODIFY 5 2 1
QUERY 3 2
QUERY 4 1
6
1
2 2
3 3
1 1
4 2
5 3
6 5
MODIFY 3 1 5
MODIFY 2 2 2
QUERY 6 1
MODIFY 4 1 -2
QUERY 2 2

21
14
14
28

# E. Dividing Kingdom

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

A country called Flatland is an infinite two-dimensional plane. Flatland has n cities, each of them is a point on the plane.

Flatland is ruled by king Circle IV. Circle IV has 9 sons. He wants to give each of his sons part of Flatland to rule. For that, he wants to draw four distinct straight lines, such that two of them are parallel to the Ox axis, and two others are parallel to the Oy axis. At that, no straight line can go through any city. Thus, Flatland will be divided into 9 parts, and each son will be given exactly one of these parts. Circle IV thought a little, evaluated his sons' obedience and decided that the i-th son should get the part of Flatland that has exactly aicities.

Help Circle find such four straight lines that if we divide Flatland into 9 parts by these lines, the resulting parts can be given to the sons so that son number i got the part of Flatland which contains ai cities.

### Input

The first line contains integer n (9 ≤ n ≤ 105) — the number of cities in Flatland. Next n lines each contain two space-separated integers: xi, yi ( - 109 ≤ xi, yi ≤ 109) — the coordinates of the i-th city. No two cities are located at the same point. The last line contains nine space-separated integers: .

### Output

If there is no solution, print a single integer -1.

Otherwise, print in the first line two distinct real space-separated numbers: x1, x2 — the abscissas of the straight lines that are parallel to the Oy axis. And in the second line print two distinct real space-separated numbers: y1, y2 — the ordinates of the straight lines, parallel to the Ox. If there are multiple solutions, print any of them.

When the answer is being checked, a city is considered to lie on a straight line, if the distance between the city and the line doesn't exceed 10 - 6. Two straight lines are considered the same if the distance between them doesn't exceed 10 - 6.

### Examples

input

output

input

output

input

output

Note

The solution for the first sample test is shown below:

The solution for the second sample test is shown below:

There is no solution for the third sample test.

# E. New Year and Old Subsequence

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

A string t is called nice if a string "2017" occurs in t as a subsequence but a string "2016" doesn't occur in t as a subsequence. For example, strings "203434107" and "9220617" are nice, while strings "20016", "1234" and "20167" aren't nice.

The ugliness of a string is the minimum possible number of characters to remove, in order to obtain a nice string. If it's impossible to make a string nice by removing characters, its ugliness is  - 1.

Limak has a string s of length n, with characters indexed 1 through n. He asks you q queries. In the i-th query you should compute and print the ugliness of a substring (continuous subsequence) of s starting at the index ai and ending at the index bi (inclusive).

### Input

The first line of the input contains two integers n and q (4 ≤ n ≤ 200 000, 1 ≤ q ≤ 200 000) — the length of the string s and the number of queries respectively.

The second line contains a string s of length n. Every character is one of digits '0'–'9'.

The i-th of next q lines contains two integers ai and bi (1 ≤ ai ≤ bi ≤ n), describing a substring in the i-th query.

### Output

For each query print the ugliness of the given substring.

### Note

In the first sample:

• In the first query, ugliness("20166766") = 4 because all four sixes must be removed.
• In the second query, ugliness("2016676") = 3 because all three sixes must be removed.
• In the third query, ugliness("0166766") =  - 1 because it's impossible to remove some digits to get a nice string.

In the second sample:

• In the second query, ugliness("01201666209167") = 2. It's optimal to remove the first digit '2' and the last digit '6', what gives a string "010166620917", which is nice.
• In the third query, ugliness("016662091670") = 1. It's optimal to remove the last digit '6', what gives a nice string "01666209170".