## CodeForces 632E FFT 二分优化多次卷积

http://codeforces.com/problemset/problem/632/E

## E. Thief in a Shop

time limit per test 5 seconds
memory limit per test 512 megabytes

A thief made his way to a shop.

As usual he has his lucky knapsack with him. The knapsack can contain k objects. There are n kinds of products in the shop and an infinite number of products of each kind. The cost of one product of kind i is ai.

The thief is greedy, so he will take exactly k products (it's possible for some kinds to take several products of that kind).

Find all the possible total costs of products the thief can nick into his knapsack.

### Input

The first line contains two integers n and k (1 ≤ n, k ≤ 1000) — the number of kinds of products and the number of products the thief will take.

The second line contains n integers ai (1 ≤ ai ≤ 1000) — the costs of products for kinds from 1 to n.

### Output

Print the only line with all the possible total costs of stolen products, separated by a space. The numbers should be printed in the ascending order.

input

output

input

output

input

output

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