最后答案直接就是：
$$
n!\sum_{i=0}^{n-2m}f_{D,n,i}
$$
这个东西嘛，珠子显然都是等价的，转移又是个卷积，应该是可以多项式快速幂的。(我当时是这么想得，但是并不会处理后面的那个奇偶)
复杂度$O(D^3n)$。
第二种：
显然状态不需要这么暴力，设$f_{i,j}$表示选了$i$个珠子有$j$种珠子的个数为奇数的方案数。显然有转移：
$$
\begin{cases}f_{i,j} \times (D-j) \to f_{i+1,j+1}&j \le D\\f_{i,j} \times j \to f_{i+1,j-1}&j>0\end{cases}
$$
复杂度$O(Dn)$，矩阵快速幂优化一下就是$O(D^3\log n)$。但我不懂$\text{laofu}$那档$D \le 300$的部分分是什么意思，考怎么卡常吗？
然后第二种$\text{dp}$好像就没什么优化空间了。然后我也就不会了。~~转战题解~~
到处学习了一下姿势发现第一种$\text{dp}$有很大的优化空间。
如果把第一种$\text{dp}$值搞成生成函数，那么转移显然就是卷上$e^x$。但是后面的奇偶的东西要容斥一下。
然后我们先了解一些神奇的$\text{EGF}$：
$$
e^{-x}=\sum_{i=0}^{\infin}(-1)^{i}\frac{x^i}{i!}
$$
$$
\frac{e^{x}-e^{-x}}{2}=\sum_{i=0}^{\infin}\frac{x^{2i+1}}{(2i+1)!}
$$
$$
\frac{e^{x}+e^{-x}}{2}=\sum_{i=0}^{\infin}\frac{x^{2i}}{(2i)!}
$$
设$f_i$表示至少有$i$种珍珠的个数为奇数的$\frac{1}{\prod_{j=1}^icnt[j]}$的和。
设$g_i$表示恰好有$i$种珍珠的个数为奇数的$\frac{1}{\prod_{j=1}^icnt[j]}$的和。
则有：
$$
\begin{aligned}f_i&=\binom{D}{i}[x^n]\left(\frac{e^x-e^{-x}}{2}\right)^ie^{(D-i)x}\\&=\frac{1}{2^i}\binom{D}{i}[x^n](e^x-e^{-x})^ie^{(D-i)x}\\&=\frac{1}{2^i}\binom{D}{i}[x^n]\sum_{j=0}^i\binom{i}{j}(-1)^{i-j}e^{jx}e^{(j-i)x}e^{(D-i)x}\\&=\frac{1}{2^i}\binom{D}{i}[x^n]\sum_{j=0}^i\binom{i}{j}(-1)^{i-j}e^{(D-2(i-j))x}\end{aligned}
$$
然后把里面的$j$设成$i-j$等式不变。
$$
f_i=\frac{1}{2^i}\binom{D}{i}[x^n]\sum_{j=0}^i\binom{i}{j}(-1)^{j}e^{(D-2j)x}
$$
然后现在又有一个神奇的$\text{EGF}$：
$$
e^{cx}=\sum_{i=0}^{\infin}c^i\frac{x^i}{i!}
$$
又因为最后答案要乘上$n$的阶乘，我们现在先乘进去：
$$
\begin{aligned}f_i&=\frac{1}{2^i}\binom{D}{i}\sum_{j=0}^i\binom{i}{j}(-1)^j(D-2j)^n\\\frac{f_i}{i!}&=\frac{1}{2^i}\binom{D}{i}\sum_{j=0}^i\frac{(-1)^j(D-2j)^n}{j!}\frac{1}{(i-j)!}\end{aligned}
$$
显然是个卷积的形式。
最后二项式反演一下有：
$$
\begin{aligned}g_i&=\sum_{j=i}^D(-1)^{j-i}\binom{j}{i}f_j\\g_i \times i!&=\sum_{j=i}^D\frac{(-1)^{j-i}}{(j-i)!}f_j\times j!\end{aligned}
$$
然后我们把$g_i \times i!$和$f_i \times i!$都$\text{reverse}$一下就是一个卷积的形式了。最后答案为：
$$
\sum_{i=0}^{n-2m}g_i
$$
复杂度为$O(D \log D)$。
PS ： 要先判一下$n - 2m < 0$和$n - 2m \ge D$的情况。
代码：
```cpp
/*
* 3120.cpp
* This file is part of 3120
*
* Copyright (C) 2019 - ViXbob
*
* 3120 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* 3120 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with 3120. If not, see <http://www.gnu.org/licenses/>.
*/
/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define inv(x) (ksm(x, P - 2))
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int maxn = 1e5 + 5;
const int P = 998244353;
const int inf = 0x3f3f3f3f;
const int maxm = maxn << 2;
inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}
int D, n, m, ans, fac[maxn], ifac[maxn], f[maxn], g[maxn], ipow2[maxn];
inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }
inline int mul(int x, int y) { return 1ll * x * y % P; }
inline int C(int n, int m) { return 1ll * fac[n] * ifac[m] % P * ifac[n - m] % P; }
inline int ksm(int x, int k, int rnt = 1) {
for(int i = k; i; i >>= 1, x = 1ll * x * x % P) if(i & 1) rnt = 1ll * rnt * x % P;
return rnt;
}
namespace NTT {
const int G = 3, invG = inv(G);
int s, l, rev[maxm], E[maxm], H[maxm], inv;
inline void init(int n) {
s = 2; l = 1;
while(s <= n) s <<= 1, l++; inv = inv(s);
rep(i, 0, s - 1) rev[i] = rev[i >> 1] >> 1 | (i & 1) << l - 1;
memset(E, 0, sizeof(int) * (s + 5));
memset(H, 0, sizeof(int) * (s + 5));
}
inline void dft(int *a, int n, int f) {
rep(i, 0, n - 1) if(i < rev[i]) swap(a[i], a[rev[i]]);
for(int i = 1; i < n; i <<= 1) {
int Wn = ksm(f, (P - 1) / (i << 1));
for(int j = 0; j < n; j += (i << 1)) {
int w = 1;
for(int k = 0; k < i; k++, w = 1ll * w * Wn % P) {
int A1 = a[j + k], A2 = 1ll * w * a[j + k + i] % P;
a[j + k] = pls(A1, A2); a[j + k + i] = dec(A1, A2);
}
}
}
}
inline void conv() {
dft(E, s, G); dft(H, s, G);
rep(i, 0, s - 1) E[i] = 1ll * E[i] * H[i] % P;
dft(E, s, invG);
rep(i, 0, s - 1) E[i] = 1ll * E[i] * inv % P;
}
}
const int inv2 = inv(2);
int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
D = read(); n = read(); m = read();
if(n - 2 * m < 0) { cout << 0 << endl; return 0; }
if(n - 2 * m >= D) { cout << ksm(D, n) << endl; return 0; }
fac[0] = 1; ipow2[0] = 1;
rep(i, 1, D) fac[i] = 1ll * fac[i - 1] * i % P, ipow2[i] = 1ll * ipow2[i - 1] * inv2 % P;
ifac[D] = inv(fac[D]);
dep(i, D - 1, 0) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
NTT :: init(D << 1);
for(int i = 0, ty = 1; i <= D; i++, ty = (ty == 1 ? P - 1 : 1))
NTT :: E[i] = 1ll * ty * ksm(pls(D - 2 * i, P), n) % P * ifac[i] % P, NTT :: H[i] = ifac[i];
NTT :: conv();
rep(i, 0, D) f[i] = 1ll * ipow2[i] * fac[i] % P * C(D, i) % P * NTT :: E[i] % P;
NTT :: init(D << 1);
for(int i = 0, ty = 1; i <= D; i++, ty = (ty == 1 ? P - 1 : 1))
NTT :: E[i] = 1ll * f[D - i] * fac[D - i] % P, NTT :: H[i] = 1ll * ty * ifac[i] % P;
NTT :: conv();
rep(i, 0, D) g[i] = 1ll * NTT :: E[D - i] * ifac[i] % P;
rep(i, 0, n - 2 * m) ans = pls(ans, g[i]);
cout << ans << endl;
return 0;
}
/*
*/
```