题意：
问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 3const int N = 500010;using namespace std;int R[N<<2];LL qpow(LL x,int n,LL P) {LL ans = 1;for(;n;n>>=1,x = x*x % P) if(n&1) ans = ans*x % P;return ans; }void DFT(LL a[],int n,int tp_k,LL P) {for(int i=0;i<n;i++) if(i<R[i]) swap(a[i],a[R[i]]);for(int d=1;d<n;d<<=1){LL wn = qpow(gn, (P-1)/(d<<1),P);if(tp_k == -1) wn = qpow(wn, P-2,P);for(int i=0;i<n;i += (d<<1)){LL wt = 1;for(int k=0;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-2,P);if(tp_k==-1)for(int i=0;i<n;i++) a[i] = a[i] * inv % P; }LL A[N<<2],B[N<<2];int main() {//freopen("test.txt","w",stdout);int n,K;cin>>n>>K;int L = 0,tot;while((1<<L)<1000*K) L++;tot = (1<<L);for(int i=1;i<tot;i++) R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));for(int i=1,x;i<=n;i++) scanf("%d",&x), A[x] = 1, B[x] = 1;DFT(A,tot,1,P1);for(int i=0;i<tot;i++) A[i] = qpow(A[i], K, P1);DFT(A,tot,-1,P1);DFT(B,tot,1,P2);for(int i=0;i<tot;i++) B[i] = qpow(B[i], K, P2);DFT(B,tot,-1,P2);for(int i=0;i<tot;i++) if(A[i] || B[i]) printf("%d ",i);printf("\n");return 0; }
