CodeForces - 632E Thief in a Shop (FFT+记忆化搜索)

题意：有N种物品，每种物品有价值\(a_i\),每种物品可选任意多个，求拿k件物品，可能损失的价值分别为多少。

分析：相当于求\((a_1+a_2+...+a_n)^k\)中，有哪些项的系数不为0.做k次FFT求卷积求卷积肯定爆炸，考虑用分治的形式计算，因为中间计算的时候会重复计算一些幂次，所以用记忆化搜索的形式，保留计算结果。

因为只要计算出哪些项不为0，所以卷积之后求结果时，系数非0项用1作系数即可，否则分分钟炸精度。

当然也可以用快速幂求解#.

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MAXN = 2e6 + 10;

const double PI = acos(-1.0);

struct Complex{

    double x, y;

    inline Complex operator+(const Complex b) const {

        return (Complex){x +b.x,y + b.y};

    }

    inline Complex operator-(const Complex b) const {

        return (Complex){x -b.x,y - b.y};

    }

    inline Complex operator*(const Complex b) const {

        return (Complex){x *b.x -y * b.y,x * b.y + y * b.x};

    }

} va[MAXN * 2 + MAXN / 2], vb[MAXN * 2 + MAXN / 2];

int lenth = 1, rev[MAXN * 2 + MAXN / 2];

int N, M;   // f 和 g 的数量

    // f g和 的系数

    // 卷积结果

    // 大数乘积

int f[MAXN],g[MAXN];

vector<LL> conv;

vector<LL> multi;

//f g

void init()

{

    int tim = 0;

    lenth = 1;

    conv.clear(), multi.clear();

    memset(va, 0, sizeof va);

    memset(vb, 0, sizeof vb);

    while (lenth <= N + M - 2)

        lenth <<= 1, tim++;

    for (int i = 0; i < lenth; i++)

        rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (tim - 1));

}

void FFT(Complex *A, const int fla)

{

    for (int i = 0; i < lenth; i++){

        if (i < rev[i]){

            swap(A[i], A[rev[i]]);

        }

    }

    for (int i = 1; i < lenth; i <<= 1){

        const Complex w = (Complex){cos(PI / i), fla * sin(PI / i)};

        for (int j = 0; j < lenth; j += (i << 1)){

            Complex K = (Complex){1, 0};

            for (int k = 0; k < i; k++, K = K * w){

                const Complex x = A[j + k], y = K * A[j + k + i];

                A[j + k] = x + y;

                A[j + k + i] = x - y;

            }

        }

    }

}

void getConv(){             //求多项式

    init();

    for (int i = 0; i < N; i++)

        va[i].x = f[i];

    for (int i = 0; i < M; i++)

        vb[i].x = g[i];

    FFT(va, 1), FFT(vb, 1);

    for (int i = 0; i < lenth; i++)

        va[i] = va[i] * vb[i];

    FFT(va, -1);

    for (int i = 0; i <= N + M - 2; i++)

        conv.push_back((LL)(va[i].x / lenth + 0.5)>0?1:0);

}

int base[MAXN];

vector<LL> mi[1005];

int num;

bool make[1005];

vector<LL> dfs(int i,int j,int cc){

    if(i==j){

        vector<LL> res;

        for(int i=0;i<num;++i){

            res.push_back(base[i]);

        }

        make[cc] = true;

        mi[cc] = res;

        return res;

    }

    vector<LL> L,R;

    int m = (i+j)>>1;

    if(make[m-i+1]) L = mi[m-i+1];

    else L = dfs(i,m,m-i+1);

    if(make[j-m]) R = mi[j-m];

    else R = dfs(m+1,j,j-m);

    N = L.size();

    M = R.size();

    for(int i=0;i<N;++i) f[i] = L[i];

    for(int i=0;i<M;++i) g[i] = R[i];

    getConv();

    make[cc] = true;

    mi[cc] = conv;

    return conv;

}

int cnt[MAXN];

int main()

{

    int n,k;

    scanf("%d %d",&n, &k);

    int mx = -1;

    int mn = 100005;

    for(int i=1,tmp;i<=n;++i){

        scanf("%d",&tmp);

        cnt[tmp]++;

        mn = min(mn,tmp);

        mx = max(mx,tmp);

    }

    num = mx+1;

    for(int i=0;i<num;++i){

        base[i] = cnt[i];

    }

    conv = dfs(1,k,k);

    int sz = conv.size();

    for(int i=k*mn;i<sz;++i){

        if(!conv[i]) continue;

        printf("%d%c",i,i==sz-1?'\n':' ');

    }

    return 0;

}