Thief in a Shop

题意：

问n个物品选出K个可以拼成的体积有哪些。

解法：

多项式裸题，注意到本题中 $A(x)^K$ 的系数会非常大，采用NTT优于FFT。

NTT 采用两个 $2^t+1$ 质数，求原根 $g_n$ 后用 $g_n^1 $~$ g_n^{P-1}$ 的循环代替复数向量的旋转。

注意逆的 $w_n$ 是 $g_n ^ { - \frac{P-1}{len} }$，并且要用两个质数保证正确即可，$O(nlogn)$。

#include <bits/stdc++.h>

#define PI acos(-1)

#define P1 998244353LL

#define P2 469762049LL

#define LL long long

#define gn 3

const int N = ;

using namespace std;

int R[N<<];

LL qpow(LL x,int n,LL P)

{

    LL ans = ;

    for(;n;n>>=,x = x*x % P) if(n&) ans = ans*x % P;

    return ans;

}

void DFT(LL a[],int n,int tp_k,LL P)

{

    for(int i=;i<n;i++) if(i<R[i]) swap(a[i],a[R[i]]);

    for(int d=;d<n;d<<=)

    {

        LL wn = qpow(gn, (P-)/(d<<),P);

        if(tp_k == -) wn = qpow(wn, P-,P);

        for(int i=;i<n;i += (d<<))

        {

            LL wt = ;

            for(int k=;k<d;k++, wt = wt*wn % P)

            {

                LL A0 = a[i+k], A1 = wt * a[i+k+d] % P;

                a[i+k] = A0+A1;

                a[i+k+d] = A0+P-A1;

                if(a[i+k] >= P) a[i+k] -= P;

                if(a[i+k+d] >= P) a[i+k+d] -= P;

            }

        }

    }

    LL inv = qpow(n, P-,P);

    if(tp_k==-)

        for(int i=;i<n;i++) a[i] = a[i] * inv % P;

}

LL A[N<<],B[N<<];

int main()

{

    //freopen("test.txt","w",stdout);

    int n,K;

    cin>>n>>K;

    int L = ,tot;

    while((<<L)<*K) L++;

    tot = (<<L);

    for(int i=;i<tot;i++) R[i]=(R[i>>]>>)|((i&)<<(L-));

    for(int i=,x;i<=n;i++) scanf("%d",&x), A[x] = , B[x] = ;

    DFT(A,tot,,P1);

    for(int i=;i<tot;i++) A[i] = qpow(A[i], K, P1);

    DFT(A,tot,-,P1);

    DFT(B,tot,,P2);

    for(int i=;i<tot;i++) B[i] = qpow(B[i], K, P2);

    DFT(B,tot,-,P2);

    for(int i=;i<tot;i++) if(A[i] || B[i]) printf("%d ",i);

    printf("\n");

    return ;

}

巴特西

Thief in a Shop

最新文章

热门文章