codeforces 632E（FFT+分治）

题意：给你n个数 ，从中任意取k个求和，将所有可能的和从小到达输出
其中n,k,ai<=1000
分析： 当k=2时，我们可以考虑母函数来做
令f(x)=(xa1+?+xan)?(xa1+?+xan)
那么 f(x)所有的系数大于0的项的次数就是答案
计算 f(x)可以考虑快速傅里叶变换进行优化 时间复杂度是O(n?log(n))
而原题是K，考虑分治倍增的思想，我们可以优化到O(n?1000?log(n?1000)?log(k))
然而我们需要在每次FFT后将系数大于1的置为系数为1的以防止爆精度
下附代码

#include
using namespace std;


typedef long long LL;
const LL kMaxn = 3000;
typedef long double ld;
const double kPi = acos(-1.0);
int len, n,a[kMaxn];


struct Complex {
    double r, i;
    Complex(double r = 0, double i = 0):r(r), i(i) {};
    Complex operator + (const Complex & rhs) {
        return Complex(r + rhs.r, i + rhs.i);
    }
    Complex operator - (const Complex & rhs) {
        return Complex(r - rhs.r, i - rhs.i);
    }
    Complex operator * (const Complex &rhs) {
        return Complex(r * rhs.r - i * rhs.i, i * rhs.r + r * rhs.i);
    }
};

void Rader(Complex F[], int len) {
    int j = len >> 1;
    for(int i = 1; i < len - 1; i++) {
        if(i < j) swap(F[i], F[j]);
        int k = len >> 1;
        while(j >= k) {
            j -= k;
            k >>= 1;
        }
        if(j < k) j += k;
    }
}

void FFT(Complex F[], int len, int t) { //时域转频域
    Rader(F, len);
    for(int h = 2; h <= len; h <<= 1) {
        Complex wn(cos(-t*2*kPi/h), sin(-t*2*kPi/h));
        for(int j = 0; j < len; j += h) {
            Complex E(1, 0);
            for(int k = j; k < j + h / 2; k++) {
                Complex u = F[k];
                Complex v = E*F[k+h/2];
                F[k] = u + v;
                F[k+h/2] = u - v;
                E = E * wn;
            }
        }
    }
    if(t == -1) {
        for(int i = 0; i < len; i++) {
            F[i].r /= len;
        }
    }
}
Complex x1[kMaxn*kMaxn], x2[kMaxn*kMaxn], x3[kMaxn*kMaxn];

void solve(int m) {  //倍增的思想
    if (m == 1)
        return;
         while (len <= 1000*m)
        len <<= 1;
    solve(m/2);
    FFT(x1, len, 1);
    FFT(x2, len, 1);
    for (int i = 0; i < len; i++) {
        x1[i] = x1[i] * x2[i];
    }
    FFT(x1, len, -1);
    for (int i = 0; i < len; i++)
        if (x1[i].r > 0.5) x1[i] = x2[i] = Complex(1, 0);//如果系数大于1 就设置成1
        else  x1[i] = x2[i] = Complex(0, 0);

    if (m&1) {
        FFT(x1, len, 1);
        FFT(x3, len, 1);
        for (int i = 0; i < len; i++) {
            x1[i] = x1[i] * x3[i];
        }
        FFT(x1, len, -1);
        FFT(x3, len, -1);
        for (int i = 0; i < len; i++)
            if (x1[i].r > 0.5)
                x1[i] = x2[i] = Complex(1, 0);
            else
                x1[i] = x2[i] = Complex(0, 0);
        for (int i = 0; i < len; i++)
            if (x3[i].r > 0.5)
                x3[i] = Complex(1, 0);
            else
                x3[i] = Complex(0, 0);
    }
}
int main()
{
    int k;
    scanf("%d%d", &n, &k);
    len = 1024;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        x1[a[i]] = x2[a[i]] = x3[a[i]] = Complex(1, 0);
    }
    solve(k);
    for (int i = 0; i <= 1000*k; i++) {
        if (x1[i].r >= 0.5)
            printf("%d ", i);
    }
    return 0;

}