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

## HDU 5730 Shell Necklace FFT+cdq分治优化DP

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

# Shell Necklace

Time Limit: 16000/8000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Problem Description

Perhaps the sea‘s definition of a shell is the pearl. However, in my view, a shell necklace with n beautiful shells contains the most sincere feeling for my best lover Arrietty, but even that is not enough.
Suppose the shell necklace is a sequence of shells (not a chain end to end). Considering i continuous shells in the shell necklace, I know that there exist different schemes to decorate the i shells together with one declaration of love.
I want to decorate all the shells with some declarations of love and decorate each shell just one time. As a problem, I want to know the total number of schemes.
Input
There are multiple test cases(no more than 20 cases and no more than 1 in extreme case), ended by 0.
For each test cases, the first line contains an integer n , meaning the number of shells in this shell necklace, where 1n105 . Following line is a sequence with n non-negative integer a1,a2,,an, and ai107 meaning the number of schemes to decorate i continuous shells together with a declaration of love.
Output
For each test case, print one line containing the total number of schemes module 313 (Three hundred and thirteen implies the march 13th, a special and purposeful day).
Sample Input
3
1 3 7
4
2 2 2 2
0
Sample Output

14 54

Hint For the first test case in Sample Input, the Figure 1 provides all schemes about it. The total number of schemes is 1 + 3 + 3 + 7 = 14.

Author
HIT
Source
题意：装饰一条链上的n个珠子，装饰任意连续i个珠子的方案数是a[i]，每个珠子只能被装饰一次，求装饰这n个珠子的方案数的总数。