题目链接：洛谷
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$个奇数的方案数。
因为这是数的排列问题，所以考虑使用指数型生成函数。
$$egin{align*}f_k&=[x^n]n!inom{D}{k}(frac{e^x-e^{-x}}{2})^k(e^x)^{D-k} \&=[x^n]frac{n!}{2^k}inom{D}{k}(e^x-e^{-x})^ke^{(D-k)x}end{align*}$$
前面系数的部分可以不用管它，直接看后面多项式的部分。
$$egin{align*}&(e^x-e^{-x})^ke^{(D-k)x}[x^n] \=&sum_{i=0}^kinom{k}{i}e^{ix}e^{-(k-i)x}(-1)^{k-i}e^{(D-k)x}[x^n] \=&sum_{i=0}^kinom{k}{i}e^{(2i+D-2k)x}(-1)^{k-i}[x^n] \=&sum_{i=0}^kinom{k}{i}e^{(D-2i)x}(-1)^{k-i}[x^n] \=&frac{1}{n!}sum_{i=0}^kinom{k}{i}(-1)^i(D-2i)^nend{align*}$$
$$f_k=frac{D!}{2^k(D-k)!}sum_{i=0}^kfrac{(-1)^i(D-2i)^n}{i!}*frac{1}{(k-i)!}$$
可以通过卷积$O(Dlog D)$计算。
计算$g_k$可以使用二项式反演，熟悉二项式反演的同学可以知道，二项式反演其实就是指数型生成函数的应用。
$$f_i=sum_{j=i}^ninom{j}{i}g_jRightarrow g_i=frac{1}{i!}sum_{j=k}^nfrac{(-1)^{j-i}}{(j-i)!}*(f_j*j!)$$
$$ans=sum_{i=0}^{n-2m}g_i$$
时间复杂度$O(Dlog D)$
1 #include<bits/stdc++.h> 2 #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 }