题目大意：有一个小偷，拿$k$个东西，有$n$种产品，每种产品都有无限多个。对于每个第$i$ 种产品，它的价值是$A_i$。可能偷走的物品价值之和。
题解：对于所有的物品构造生成函数$F(x)=\sum\limits_{i\in A}x^i$，取$k$个物品相当于取其中的$k$项相乘，输出$F^k(x)$中不为零的项就行了。（这道题模数$998244353$和$1004535809$都被$hack$了，看$Weng\_weijie\;dalao$的题解得双模数没被卡，于是就$A$了）（这道题似乎可以用$DP$，但我不怎么会）
卡点：无
C++ Code：
#include#include #define maxn 1 << 20 | 3const int G = 3;int mod, ans;int lim, ilim, s, rev[maxn], Wn[maxn];inline int pw(int base, long long p) { base %= mod, p %= mod - 1; int ans = 1; for (; p; p >>= 1, base = 1ll * base * base % mod) if (p & 1) ans = 1ll * ans * base % mod; return ans;}inline int Inv(int x) { return pw(x, mod - 2);}inline void up(int &a, int b) {if ((a += b) >= mod) a -= mod;}inline void NTT(int *A, int op) { for (int i = 0; i < lim; i++) if (i < rev[i]) std::swap(A[i], A[rev[i]]); for (int mid = 1; mid < lim; mid <<= 1) { int t = lim / mid >> 1; for (int i = 0; i < lim; i += mid << 1) { for (int j = 0; j < mid; j++) { int W = op ? Wn[t * j] : Wn[lim - t * j]; int X = A[i + j], Y = 1ll * A[i + j + mid] * W % mod; up(A[i + j], Y), up(A[i + j + mid] = X, mod - Y); } } } if (!op) for (int i = 0; i < lim; i++) A[i] = 1ll * A[i] * ilim % mod;}inline void init(int n, int mod) { ::mod = mod; lim = 1, s = -1; while (lim < n) lim <<= 1, s++; ilim = Inv(lim); for (int i = 0; i < lim; i++) rev[i] = rev[i >> 1] >> 1 | (i & 1) << s; int W = pw(G, (mod - 1) / lim); Wn[0] = 1; for (int i = 1; i <= lim; i++) Wn[i] = 1ll * Wn[i - 1] * W % mod;}int n, k;int a[maxn], b[maxn];int main() { scanf("%d%d", &n, &k); for (int i = 0, tmp; i < n; i++) scanf("%d", &tmp), a[tmp] = b[tmp] = 1; init(1 << 20, 998244353); NTT(a, 1); for (int i = 0; i < lim; i++) a[i] = pw(a[i], k); NTT(a, 0); init(1 << 20, 1004535809); NTT(b, 1); for (int i = 0; i < lim; i++) b[i] = pw(b[i], k); NTT(b, 0); for (int i = 0; i < lim; i++) if (a[i] | b[i]) printf("%d ", i); return 0;}