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

## HDU6158 The Designer 笛卡尔定理 递推

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

$$(\frac{1}{r_2} + \frac{1}{r_3} + \frac{1}{r_4} - \frac{1}{r_1})^2 = 2(\frac{1}{r^2_1}+\frac{1}{r^2_2}+\frac{1}{r^2_3}+\frac{1}{r^2_4})$$

$r_1 = r_a - r_b$

$$(\frac{1}{r_k}+\frac{1}{r_{k+1}}+\frac{1}{r_b}-\frac{1}{r_a})^2= 2(\frac{1}{r^2_k}+\frac{1}{r^2_{k+1}}+\frac{1}{r^2_b}+\frac{1}{r^2_a})$$

$$(\frac{1}{r_k}+\frac{1}{r_{k-1}}+\frac{1}{r_b}-\frac{1}{r_a})^2= 2(\frac{1}{r^2_k}+\frac{1}{r^2_{k-1}}+\frac{1}{r^2_b}+\frac{1}{r^2_a})$$

$$(\frac{1}{r_{k+1}}-\frac{1}{r_{k-1}})(\frac{2}{r_k}+\frac{1}{r_{k+1}}+\frac{1}{r_{k-1}}+\frac{2}{r_b}-\frac{2}{r_a})= 2(\frac{1}{r^2_{k+1}} - \frac{1}{r^2_{k-1}})$$

$$(\frac{1}{r_{k+1}}-\frac{1}{r_{k-1}})(\frac{2}{r_k}+\frac{1}{r_{k+1}}+\frac{1}{r_{k-1}}+\frac{2}{r_b}-\frac{2}{r_a})= 2(\frac{1}{r_{k+1}}-\frac{1}{r_{k-1}})(\frac{1}{r_{k+1}}+\frac{1}{r_{k-1}})$$

$$\frac{2}{r_k}+\frac{1}{r_{k+1}}+\frac{1}{r_{k-1}}+\frac{2}{r_b}-\frac{2}{r_a}= \frac{2}{r_{k+1}}+\frac{2}{r_{k-1}}$$

$$\frac{2}{r_k}+\frac{2}{r_b}-\frac{2}{r_a}=\frac{1}{r_{k+1}}+\frac{1}{r_{k-1}}$$

$$\frac{1}{r_{k+1}}=\frac{2}{r_k}+\frac{2}{r_b}-\frac{2}{r_a}-\frac{1}{r_{k-1}}$$

$$(\frac{1}{r_1} + \frac{1}{r_2} + \frac{1}{r_b} - \frac{1}{r_a})^2 = 2(\frac{1}{r^2_1}+\frac{1}{r^2_2}+\frac{1}{r^2_b}+\frac{1}{r^2_a})$$

$$\frac{1}{r^2_2} + 2 \times \frac{1}{r_2}(\frac{1}{r_1} + \frac{1}{r_b} - \frac{1}{r_a}) = 2 \times \frac{1}{r^2_2} + 2(\frac{1}{r^2_1}+\frac{1}{r^2_b}+\frac{1}{r^2_a})$$

$$\frac{1}{r^2_2} - 2(\frac{1}{r_1} + \frac{1}{r_b} - \frac{1}{r_a})\frac{1}{r_2} +2(\frac{1}{r^2_1}+\frac{1}{r^2_b}+\frac{1}{r^2_a}) = 0$$

$$\frac{1}{r_2} + \frac{1}{r_2} = 2(\frac{1}{r_1} + \frac{1}{r_b} - \frac{1}{r_a})$$

$$\frac{1}{r_2} = \frac{1}{r_1} + \frac{1}{r_b} - \frac{1}{r_a}$$

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

## SPOJ TSUM FFT求方案数

http://www.spoj.com/problems/TSUM/

## TSUM - Triple Sums

You're given a sequence s of N distinct integers.
Consider all the possible sums of three integers from the sequence at three different indicies.
For each obtainable sum output the number of different triples of indicies that generate it.

Constraints:

N <= 40000, |si| <= 20000

### Input

The first line of input contains a single integer N.
Each of the next N lines contain an element of s.

### Output

Print the solution for each possible sum in the following format:
sum_value : number_of_triples

Smaller sum values should be printed first.

### Example

Explanation:
4 can be obtained using triples ( 0, 1, 2 ) and ( 0, 3, 4 ).
7 can be obtained using triples ( 0, 2, 4 ) and ( 1, 3, 4 ).

Note: a triple is considered the same as any of its permutations.

### 题意

$n$个整数$s_i$，对于所有的$s$，求满足$s_i+s_j+s_k=s$且$i<j<k$的$(i,j,k)$数量。$n \leq 40000$,$|s_i| \leq 20000$。

### 思路

1、用$(\sum x)^3$表示任意取三个数，可以用$A(x)$自乘3次得到。

$$(\sum x)^3 = \sum x^3 + 3 \sum x^2y + 6 \sum xyz$$

2、用$(\sum x^2)(\sum x)$表示至少两个相同，将$A(x)$每一个位置的系数移动到$x^2$的位置即可表示$(\sum x^2)$。

$$(\sum x^2)(\sum x)= \sum x^3+\sum x^2y$$

3、$\sum x^3$即是将$A(x)$的系数移动到$x^3$的位置即可。

$$\sum xyz = \frac{(\sum x)^3 - 3(\sum x^2)(\sum x)+2(\sum x^3)}{6}$$