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

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