题目大意：有$n(n\leqslant10^5)$种物品，第$i$个物品体积为$v_i$，都有$10^5$件。给定$m(m\leqslant10^5)$，对于$s\in [1,m]$，请你回答用这些商品恰好装$s$体积的方案数
题解：(by Weng_weijie)
背包问题模板(误)
对每个物品构造生成函数$F(x)=\displaystyle\sum_{i=0}^{\infty}x^{vi}=\dfrac{1}{1-x^v}$
然后所有相乘就得到答案（不会乘）
对每个多项式求$\ln$加起来再求$\exp$，但是一个个求也不行（复杂度$O(nm)$），可以记录一下每个$v_i$的出现次数，一次性加起来，这样处理出原式子的复杂度是$O(m\log_2m)$
于是：
$$
\begin{align*}
\ln F(x)&=\int \frac{F'(x)}{F(x)} dx \\\\
&=\int \sum_{i=1}^{\infty}vix^{vi-1}(1-x^v) dx \\\\
&=\int \sum_{i=1}^{\infty}vx^{vi-1} dx\\\\
&=\sum_{i=1}^{\infty}\frac{1}{i}x^{vi}
\end{align*}
$$
然后加起来求$\exp$
卡点：数组开小
C++ Code：
#include <cstdio>
#include <algorithm>
#define maxn 100010
#define N (262144 | 3)
const int mod = 998244353, G = 3;
int n, m;
int inv[N], a[N], b[N];
int num[maxn], maxvi;
namespace Poly {
inline int pw(int base, int p) {
int res = 1;
for (; p; p >>= 1, base = 1ll * base * base % mod) if (p & 1) res = 1ll * res * base % mod;
return res;
}
inline int Inv(int x){return pw(x, mod - 2);}
int lim, ilim, s, rev[N];
int Wn[N];
inline void init(int n) {
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 t = pw(G, (mod - 1) / lim);
Wn[0] = 1; for (int i = 1; i <= lim; i++) Wn[i] = 1ll * Wn[i - 1] * t % mod;
}
inline void up(int &a, int b) {if ((a += b) >= mod) a -= mod;}
inline void NTT(int *A, int op = 1) {
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 DER(int *A, int *B, int n) {
B[n - 1] = 0; for (int i = 1; i < n; i++) B[i - 1] = 1ll * A[i] * i % mod;
}
inline void INT(int *A, int *B, int n) {
B[0] = 0; for (int i = 1; i < n; i++) B[i] = 1ll * A[i - 1] * inv[i] % mod;
}
int C[N];
void INV(int *A, int *B, int n) {
if (n == 1) {B[0] = Inv(A[0]); return ;}
INV(A, B, n + 1 >> 1), init(n << 1);
for (int i = 0; i < n; i++) C[i] = A[i];
for (int i = n; i < lim; i++) C[i] = B[i] = 0;
NTT(B), NTT(C);
for (int i = 0; i < lim; i++) B[i] = (2 + mod - 1ll * B[i] * C[i] % mod) * B[i] % mod;
NTT(B, 0);
for (int i = n; i < lim; i++) B[i] = 0;
}
int D[N];
inline void LN(int *A, int *B, int n) {
DER(A, D, n), INV(A, B, n);
init(n << 1);
NTT(B), NTT(D);
for (int i = 0; i < lim; i++) D[i] = 1ll * B[i] * D[i] % mod;
NTT(D, 0), INT(D, B, n);
for (int i = n; i < lim; i++) B[i] = 0;
}
int E[N], F[N];
void EXP(int *A, int *B, int n) {
if (n == 1) {B[0] = 1; return ;}
EXP(A, B, n + 1 >> 1);
for (int i = 0; i < n << 1; i++) E[i] = F[i] = 0;
LN(B, E, n);
for (int i = 0; i < n; i++) F[i] = A[i];
NTT(B), NTT(E), NTT(F);
for (int i = 0; i < lim; i++) B[i] = (1ll + mod - E[i] + F[i]) * B[i] % mod;
NTT(B, 0);
for (int i = n; i < lim; i++) B[i] = 0;
}
}
int main() {
scanf("%d%d", &n, &m); m++;
for (int i = 0, x; i < n; i++) scanf("%d", &x), num[x]++, maxvi = std::max(maxvi, x);
inv[1] = 1; for (int i = 2; i < N; i++) inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;
for (int i = 1; i <= maxvi; i++) {
int tmp = num[i];
if (tmp) {
for (int j = i, x = 1; j < m; j += i, x++) a[j] = (a[j] + 1ll * tmp * inv[x]) % mod;
}
}
Poly::EXP(a, b, m);
for (int i = 1; i < m; i++) printf("%d\n", b[i]);
return 0;
}