题目传送门：LOJ #3120。
题意简述：
称一个长度为 (n)，元素取值为 ([1,D]) 的整数序列是合法的，当且仅当其中能够选出至少 (m) 对相同元素（不能重复选出元素）。
问合法序列个数。
题解：
设颜色为 (c) 的珍珠的个数为 (mathrm{cnt}_c)，则一个方案合法当且仅当：
[egin{aligned}sum_{c=1}^{D}leftlfloorfrac{mathrm{cnt}_c}{2}
ight
floor&ge m\sum_{c=1}^{D}frac{mathrm{cnt}_c-mathrm{cnt}_cmod 2}{2}&ge m\sum_{c=1}^{D}(mathrm{cnt}_c-mathrm{cnt}_cmod 2)&ge 2m\n-sum_{c=1}^{D}mathrm{cnt}_cmod 2&ge 2m\sum_{c=1}^{D}mathrm{cnt}_cmod 2&le n-2mend{aligned}
]
先特判 (2mle n-D) 和 (2m>n) 的情况，答案分别为 (D^n) 和 (0)。
那么假设 (mathrm{odd}_k) 为恰好有 (k) 个 (mathrm{cnt}_c) 为奇数的方案数，则最终答案为 (displaystylesum_{i=0}^{n-2m}mathrm{odd}_i)。
考虑容斥，设 (f_k) 为至少有 (k) 个 (mathrm{cnt}_c) 为奇数的方案数，若恰好有 (j) 个奇数，会被相应地统计 (displaystyleinom{j}{k}) 次。
则有：(displaystyle f_i=sum_{j}inom{j}{i}mathrm{odd}_j)。
根据二项式反演，有：
[egin{aligned}mathrm{odd}_i&=sum_{j}(-1)^{j-i}inom{j}{i}f_j\&=sum_{j}(-1)^{i-j}frac{j!}{i!(j-i)!}f_j\&=frac{1}{i!}sum_{j}frac{(-1)^{i-j}}{[-(i-j)]!}cdot j!f_jend{aligned}
]
上式是卷积形式，问题转化为求出每一个 (f_i)。
考虑出现次数为奇数的颜色的排列方案数的指数型生成函数：(mathbf{EGF}{[0,1,0,1,ldots]})，即 (displaystylefrac{e^x-e^{-x}}{2})，故有：
[egin{aligned}f_k&=inom{D}{k}n![x^n]left(frac{e^x-e^{-x}}{2}
ight)^k(e^x)^{D-k}\&=inom{D}{k}frac{n!}{2^k}[x^n]left(e^x-e^{-x}
ight)^k(e^x)^{D-k}\&=inom{D}{k}frac{n!}{2^k}[x^n]sum_{j=0}^{k}inom{k}{j}e^{jx}(-e^{-x})^{k-j}e^{(D-k)x}\&=inom{D}{k}frac{n!}{2^k}sum_{j=0}^{k}inom{k}{j}(-1)^{k-j}[x^n]e^{(D-2(k-j))x}end{aligned}
]
考虑 (e^{ax}=mathbf{EGF}{[1,a,a^2,a^3,ldots]})，故有 (displaystyle[x^n]e^{ax}=frac{a^n}{n!})，带入上式可得：
[egin{aligned}f_k&=inom{D}{k}frac{n!}{2^k}sum_{j=0}^{k}inom{k}{j}(-1)^{k-j}frac{(D-2(k-j))^n}{n!}\&=frac{D!}{2^k(D-k)!}sum_{j=0}^{k}frac{(-1)^{j}(D-2j)^n}{j!}cdotfrac{1}{(k-j)!}end{aligned}
]
显然右边是卷积形式，直接计算即可。计算完 (f) 再使用卷积计算 (mathrm{odd}) 即可。
代码如下：
#include <cstdio>
#include <algorithm>
typedef long long LL;
const int Mod = 998244353, Inv2 = (Mod + 1) / 2;
const int G = 3, iG = 332748118;
const int MS = 1 << 18;
inline int qPow(int b, int e) {
int a = 1;
for (; e; e >>= 1, b = (LL)b * b % Mod)
if (e & 1) a = (LL)a * b % Mod;
return a;
}
inline int gInv(int b) { return qPow(b, Mod - 2); }
int Inv[MS], Fac[MS], iFac[MS];
inline void Init(int N) {
Fac[0] = 1;
for (int i = 1; i < N; ++i) Fac[i] = (LL)Fac[i - 1] * i % Mod;
iFac[N - 1] = gInv(Fac[N - 1]);
for (int i = N - 1; i >= 1; --i) iFac[i - 1] = (LL)iFac[i] * i % Mod;
for (int i = 1; i < N; ++i) Inv[i] = (LL)Fac[i - 1] * iFac[i] % Mod;
}
int Sz, InvSz, R[MS];
inline int getB(int N) { int Bt = 0; while (1 << Bt < N) ++Bt; return Bt; }
inline void InitFNTT(int N) {
int Bt = getB(N);
if (Sz == (1 << Bt)) return ;
Sz = 1 << Bt, InvSz = Mod - (Mod - 1) / Sz;
for (int i = 1; i < Sz; ++i) R[i] = R[i >> 1] >> 1 | (i & 1) << (Bt - 1);
}
inline void FNTT(int *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) {
int wn = qPow(~Ty ? G : iG, (Mod - 1) / j2), w, X, Y;
for (int i = 0, k; i < Sz; i += j2) {
for (k = 0, w = 1; k < j; ++k, w = (LL)w * wn % Mod) {
X = A[i + k], Y = (LL)w * A[i + j + k] % Mod;
A[i + k] -= (A[i + k] = X + Y) >= Mod ? Mod : 0;
A[i + j + k] += (A[i + j + k] = X - Y) < 0 ? Mod : 0;
}
}
}
if (!~Ty) for (int i = 0; i < Sz; ++i) A[i] = (LL)A[i] * InvSz % Mod;
}
inline void PolyConv(int *_A, int N, int *_B, int M, int *_C) {
static int A[MS], B[MS];
InitFNTT(N + M - 1);
for (int i = 0; i < N; ++i) A[i] = _A[i];
for (int i = N; i < Sz; ++i) A[i] = 0;
for (int i = 0; i < M; ++i) B[i] = _B[i];
for (int i = M; i < Sz; ++i) B[i] = 0;
FNTT(A, 1), FNTT(B, 1);
for (int i = 0; i < Sz; ++i) A[i] = (LL)A[i] * B[i] % Mod;
FNTT(A, -1);
for (int i = 0; i < N + M - 1; ++i) _C[i] = A[i];
}
int D, N, M;
int A[MS], B[MS], Ans;
int main() {
scanf("%d%d%d", &D, &N, &M);
if (M + M <= N - D) return printf("%d
", qPow(D, N)), 0;
if (M + M > N) return puts("0"), 0;
Init(D + 1);
for (int i = 0; i <= D; ++i) A[i] = (LL)qPow((D - i - i + Mod) % Mod, N) * (i & 1 ? Mod - iFac[i] : iFac[i]) % Mod;
for (int i = 0; i <= D; ++i) B[i] = iFac[i];
PolyConv(A, D + 1, B, D + 1, A);
for (int i = 0; i <= D; ++i) A[i] = (LL)A[i] * Fac[D] % Mod * Fac[i] % Mod * iFac[D - i] % Mod * qPow(Inv2, i) % Mod;
for (int i = 0; i <= D; ++i) B[D - i] = i & 1 ? Mod - iFac[i] : iFac[i];
PolyConv(A, D + 1, B, D + 1, A);
for (int i = 0; i <= N - M - M; ++i) Ans = (Ans + (LL)A[D + i] * iFac[i]) % Mod;
printf("%d
", Ans);
return 0;
}