题目传送门：洛谷 P4389。
题意简述：
有 (n) 个物品，每个物品都有无限多，第 (i) 个物品的体积为 (v_i)（(v_ile m)）。
问用这些物品恰好装满容量为 (i) 的背包的方案数，两个方案不同当且仅当存在某一个物品的选取数量不同。
你需要对 (iin [1,m]) 回答，答案对 (998,244,353) 取模。
题解：
对于一个体积为 (v) 的物品，它装满容量为 (x) 的背包的方案数序列为 (a_x=[v|x])。
例如 (v=3) 时有序列（从 (0) 开始）：({1,0,0,1,0,0,1,0,0,1,0,cdots})。
它的普通生成函数为 (displaystylefrac{1}{1-x^v})。
记答案的普通生成函数为 (F(x))，则有 (displaystyle F(x)=prod_{i=1}^{n}frac{1}{1-x^{v_i}})。
两边取对数：(displaystyleln F(x)=sum_{i=1}^{n}lnfrac{1}{1-x^{v_i}})。
有一个式子：(displaystylelnfrac{1}{1-x^k}=sum_{i=1}^{infty}frac{1}{i}x^{ik})。
这个式子的证明：
记 (displaystyle F(x)=frac{1}{1-x^k})，设 (G(x)=ln F(x))。
[egin{aligned}G(x)&=ln F(x)\&=int(frac{mathrm{d}}{mathrm{d}x}ln F)(x)mathrm{d}x\&=int(frac{F'(x)}{F(x)})mathrm{d}x\&=int((1-x^k)F'(x))mathrm{d}x\&=int((1-x^k)sum_{i=1}^{infty}kcdot icdot x^{ki-1})mathrm{d}x\&=int(sum_{i=1}^{infty}kcdot icdot x^{ki-1}-sum_{i=1}^{infty}kcdot icdot x^{ki-1}cdot x^k)mathrm{d}x\&=int(sum_{i=1}^{infty}kcdot icdot x^{ki-1}-sum_{i=1}^{infty}kcdot (i-1)cdot x^{ki-1})mathrm{d}x\&=int(sum_{i=1}^{infty}kcdot x^{ki-1})mathrm{d}x\&=sum_{i=1}^{infty}frac{1}{i}x^{ki}end{aligned}
]
建议背一些常用式子。
那么就显而易见了：
[egin{aligned}ln F(x)&=sum_{i=1}^{n}sum_{j=1}^{infty}frac{1}{j}x^{v_{i}j}\&=sum_{k=1}^{m}sum_{j=1}^{infty}frac{displaystylesum_{i=1}^{n}[v_i=k]}{i}x^{kj}end{aligned}
]
记 (b_k) 为体积为 (k) 的物品数量，并且我们只需要次数小于等于 (m) 的项，有 (displaystyleln F(x)equivsum_{k=1}^{m}sum_{j=1}^{lfloorfrac{m}{k} floor}frac{b_k}{i}x^{kj}pmod{x^{m+1}})。
右边可以在 (displaystylesum_{i=1}^{m}frac{m}{i}=O(mln m)) 的时间内得到，左边使用多项式 (mathrm{Exp}) 在 (O(mlog m)) 的时间内得到，总时间复杂度 (O(mlog m))。
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
const int Mod = 998244353;
const int G = 3, iG = 332748118;
const int MS = 1 << 19 | 7;
inline LL qPow(LL b, int e) {
LL a = 1;
for (; e; e >>= 1, b = b * b % Mod)
if (e & 1) a = a * b % Mod;
return a;
}
LL Inv[MS];
inline void Init(int N) {
Inv[1] = 1;
for (int i = 2; i < N; ++i) Inv[i] = -(Mod / i) * Inv[Mod % i] % Mod;
}
int Sz, R[MS]; LL InvSz;
inline void InitFNTT(int N) {
int Bt = 0;
for (; 1 << Bt < N; ++Bt) ;
if (Sz == (1 << Bt)) return ;
Sz = 1 << Bt; InvSz = -(Mod - 1) / Sz;
for (int i = 1; i < Sz; ++i) R[i] = R[i >> 1] >> 1 | (i & 1) << (Bt - 1);
}
inline void FNTT(LL *A, int Ty) {
for (int i = 0; i < Sz; ++i) if (R[i] < i) std::swap(A[R[i]], A[i]);
for (int j = 1, j2 = 2; j < Sz; j <<= 1, j2 <<= 1) {
LL gn = qPow(~Ty ? G : iG, (Mod - 1) / j2), g, X, Y;
for (int i = 0, k; i < Sz; i += j2) {
for (k = 0, g = 1; k < j; ++k, g = g * gn % Mod) {
X = A[i + k], Y = g * A[i + j + k] % Mod;
A[i + k] = (X + Y) % Mod, A[i + j + k] = (X - Y) % Mod;
}
}
}
if (!~Ty) for (int i = 0; i < Sz; ++i) A[i] = A[i] * InvSz % Mod;
}
inline void PolyInv(LL *A, int N, LL *B) {
static LL tA[MS], tB[MS];
B[0] = qPow(A[0], Mod - 2);
for (int L = 1; L < N; L <<= 1) {
int L2 = L << 1, L4 = L << 2;
InitFNTT(L4);
memcpy(tA, A, 8 * L2);
memset(tA + L2, 0, 8 * (Sz - L2));
memcpy(tB, B, 8 * L);
memset(tB + L, 0, 8 * (Sz - L));
FNTT(tA, 1), FNTT(tB, 1);
for (int i = 0; i < Sz; ++i) tB[i] = (2 - tB[i] * tA[i]) % Mod * tB[i] % Mod;
FNTT(tB, -1);
for (int i = 0; i < L2; ++i) B[i] = tB[i];
}
}
inline void PolyLn(LL *A, int N, LL *B) {
static LL tA[MS], tB[MS];
PolyInv(A, N - 1, tB);
InitFNTT(N * 2 - 3);
for (int i = 1; i < N; ++i) tA[i - 1] = i * A[i] % Mod;
memset(tA + N - 1, 0, 8 * (Sz - N + 1));
memset(tB + N - 1, 0, 8 * (Sz - N + 1));
FNTT(tA, 1), FNTT(tB, 1);
for (int i = 0; i < Sz; ++i) tA[i] = tA[i] * tB[i] % Mod;
FNTT(tA, -1);
B[0] = 0;
for (int i = 1; i < N; ++i) B[i] = tA[i - 1] * Inv[i] % Mod;
}
inline void PolyExp(LL *A, int N, LL *B) {
static LL tA[MS], tB[MS];
B[0] = 1;
for (int L = 1; L < N; L <<= 1) {
int L2 = L << 1, L4 = L << 2;
memset(B + L, 0, 8 * (L2 - L));
PolyLn(B, L2, tB);
InitFNTT(L4);
memcpy(tA, B, 8 * L);
memset(tA + L, 0, 8 * (Sz - L));
for (int i = 0; i < L2; ++i) tB[i] = ((!i) - tB[i] + A[i]) % Mod;
memset(tB + L2, 0, 8 * (Sz - L2));
FNTT(tA, 1), FNTT(tB, 1);
for (int i = 0; i < Sz; ++i) tA[i] = tA[i] * tB[i] % Mod;
FNTT(tA, -1);
for (int i = 0; i < L2; ++i) B[i] = tA[i];
}
}
int N, M;
int buk[MS];
LL A[MS], B[MS];
int main() {
scanf("%d%d", &N, &M);
Init(MS);
for (int i = 1, v; i <= N; ++i) scanf("%d", &v), ++buk[v];
for (int i = 1; i <= M; ++i) if (buk[i]) {
for (int j = 1; j <= M / i; ++j) {
A[i * j] = (A[i * j] + buk[i] * Inv[j]) % Mod;
}
}
PolyExp(A, M + 1, B);
for (int i = 1; i <= M; ++i) printf("%lld
", (B[i] + Mod) % Mod);
return 0;
}