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就行优化即可。

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

代码

 

 

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个珠子的方案数的总数。
思路:很容易得出,装饰前i个珠子的方案数为dp[i]=sigma(dp[j]*a[i-j])  (0<=j<i)。很显然是一个卷积,但是dp同时出现在等号前后,需要用CDQ分治加上FFT优化。对于一个区间[l,r],我们先求出[l,mid]的答案,在求出[l,mid[对[mid+1,r]的影响。对于l端点,如果要影响到r端点,就需要卷积a[i]的长度r-mid+1。用dp[l~id]和a[1~r-mid+1]进行卷积(FFT)后取出对应位置加到dp上即可。