题目链接：
pb大佬说这是sb题感觉好像有点过fan。。。（我还是太弱了）
首先，设$i$这个数在序列中出现$a_i$次，要求$\sum_{i=1}^D[a_i \ mod \ 2]\leq n-2m$
如果要直接计算$\leq n-2m$的数量会非常麻烦，所以考虑设$g_i$表示恰好出现$i$个奇数的方案之和。
这样也还是太麻烦，我们考虑使用反演或容斥通过$\geq i$的数量推算出恰好等于$i$的数量，假设$f_i$表示出现$i$个奇数的方案数。
因为这是数的排列问题，所以考虑使用指数型生成函数。
$$\begin{align*}f_k&=[x^n]n!\binom{D}{k}(\frac{e^x-e^{-x}}{2})^k(e^x)^{D-k} \\&=[x^n]\frac{n!}{2^k}\binom{D}{k}(e^x-e^{-x})^ke^{(D-k)x}\end{align*}$$
前面系数的部分可以不用管它，直接看后面多项式的部分。
$$\begin{align*}&(e^x-e^{-x})^ke^{(D-k)x}[x^n] \\=&\sum_{i=0}^k\binom{k}{i}e^{ix}e^{-(k-i)x}(-1)^{k-i}e^{(D-k)x}[x^n] \\=&\sum_{i=0}^k\binom{k}{i}e^{(2i+D-2k)x}(-1)^{k-i}[x^n] \\=&\sum_{i=0}^k\binom{k}{i}e^{(D-2i)x}(-1)^{k-i}[x^n] \\=&\frac{1}{n!}\sum_{i=0}^k\binom{k}{i}(-1)^i(D-2i)^n\end{align*}$$
$$f_k=\frac{D!}{2^k(D-k)!}\sum_{i=0}^k\frac{(-1)^i(D-2i)^n}{i!}*\frac{1}{(k-i)!}$$
可以通过卷积$O(D\log D)$计算。
计算$g_k$可以使用二项式反演，熟悉二项式反演的同学可以知道，二项式反演其实就是指数型生成函数的应用。
$$f_i=\sum_{j=i}^n\binom{j}{i}g_j\Rightarrow g_i=\frac{1}{i!}\sum_{j=k}^n\frac{(-1)^{j-i}}{(j-i)!}*(f_j*j!)$$$$ans=\sum_{i=0}^{n-2m}g_i$$
时间复杂度$O(D\log D)$
1 #include2 #define Rint register int 3 using namespace std; 4 typedef long long LL; 5 const int N = 800003, mod = 998244353, g = 3, gi = 332748118; 6 inline int kasumi(int a, int b){ 7 int res = 1; 8 while(b){ 9 if(b & 1) res = (LL) res * a % mod;10 a = (LL) a * a % mod;11 b >>= 1;12 }13 return res;14 }15 int fac[N], inv[N], invfac[N], ans;16 inline void init(int n){17 fac[0] = 1;18 for(Rint i = 1;i <= n;i ++) fac[i] = (LL) fac[i - 1] * i % mod;19 invfac[n] = kasumi(fac[n], mod - 2);20 for(Rint i = n;i;i --){21 invfac[i - 1] = (LL) i * invfac[i] % mod;22 inv[i] = (LL) invfac[i] * fac[i - 1] % mod;23 }24 }25 int rev[N];26 inline int calrev(int n){27 int limit = 1, L = -1;28 while(limit <= n){limit <<= 1; L ++;}29 for(Rint i = 0;i < limit;i ++)30 rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << L);31 return limit;32 }33 inline void NTT(int *A, int limit, int type){34 for(Rint i = 0;i < limit;i ++)35 if(i < rev[i]) swap(A[i], A[rev[i]]);36 for(Rint mid = 1;mid < limit;mid <<= 1){37 int Wn = kasumi(type == 1 ? g : gi, (mod - 1) / (mid << 1));38 for(Rint j = 0;j < limit;j += (mid << 1)){39 int w = 1;40 for(Rint k = 0;k < mid;k ++, w = (LL) w * Wn % mod){41 int x = A[j + k], y = (LL) w * A[j + k + mid] % mod;42 A[j + k] = (x + y) % mod;43 A[j + k + mid] = (x - y + mod) % mod;44 }45 }46 }47 if(type == -1){48 int inv = kasumi(limit, mod - 2);49 for(Rint i = 0;i < limit;i ++) A[i] = (LL) A[i] * inv % mod;50 }51 }52 int D, n, m, F[N], G[N];53 int main(){54 scanf("%d%d%d", &D, &n, &m);55 if(n < 2 * m){56 printf("0");57 return 0;58 }59 if(D <= n - 2 * m){60 printf("%d", kasumi(D, n));61 return 0;62 }63 init(D);64 for(Rint i = 0;i <= D;i ++){65 F[i] = (LL) kasumi((D - 2 * i + mod) % mod, n) * invfac[i] % mod;66 if(i & 1) F[i] = mod - F[i];67 G[i] = invfac[i];68 }69 int limit = calrev(D << 1);70 NTT(F, limit, 1); NTT(G, limit, 1);71 for(Rint i = 0;i < limit;i ++) F[i] = (LL) F[i] * G[i] % mod;72 NTT(F, limit, -1);73 for(Rint i = 0;i < limit;i ++) G[i] = 0;74 for(Rint i = D + 1;i < limit;i ++) F[i] = 0;75 for(Rint i = 0;i <= D;i ++){76 F[i] = (LL) F[i] * fac[i] % mod * fac[D] % mod * kasumi(2, mod - 1 - i) % mod * invfac[D - i] % mod;77 G[D - i] = (i & 1) ? (mod - invfac[i]) : invfac[i];78 }79 NTT(F, limit, 1); NTT(G, limit, 1);80 for(Rint i = 0;i < limit;i ++) F[i] = (LL) F[i] * G[i] % mod;81 NTT(F, limit, -1);82 for(Rint i = 0;i <= n - 2 * m;i ++) ans = (ans + (LL) F[i + D] * invfac[i] % mod) % mod;83 printf("%d", ans);84 }