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.

Examples

input

output

input

output

input

output

题意

有$n$种物品,每种物品有无限多个,每种物品的单个价值分别为$a_i$,问取$k$个物品能取到那些价值。$1\leq a_i,n \leq 1000$

思路

构造多项式$A(x) = \sum x^{a_i}$,其中 $x^{a_i}$的系数为0或者1,表示是否存在价值为$a_i$的物品。领$B(x) = (A(x))^k$,$B(x)$的各项系数是否为大于0即是否有得到对应价值的方案。考虑乘法满足结合律,可以采用二分幂的方式进行多次多项式乘法。每次多项式乘法后,把不为零的系数赋为1,可避免精度丢失(毕竟只是问有无方案,不是求方案数)。多项式乘法用FFT优化。

代码

 

 

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$。

思路

构造多项式$A(x) = \sum_{1\leq i \leq n}x^{s_i}$,$x^{s_i}$的系数表示$s_i$这个数出现的次数。则$A^3(x)$中$x^s$的系数即为所求结果。

考虑容斥原理:

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

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

其中$\sum x^3$表示取到三个相同的,$\sum x^2y$表示最多两个相同,$\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}$$

根据公式,构造数值进行多项式乘法,用FFT就行优化即可。

考虑到负数的存在,可以加偏移量进行偏移,最后输出答案的时候,减去三倍偏移量即可。

代码