题目
题解
先 % 兔。同为兔子为什么小粉兔辣么强qwq。 本文大体跟随小粉兔的题解的思路，并为像我一样多项式超 poor 的读者作了很详细的解释。如果题解界面公式出现问题，可以尝试“在 Ta 的博客查看”w~
生成函数 + NTT。
首先，转化题意：求长度为 (n)，元素属于 ([1,D]) 且存在至少 (m) 对位置不重复的相同元素的整数序列个数。
不妨把元素的值形象化为颜色，设第 (c) 中颜色在某个序列中出现次数为 (cnt_c)。则该序列合法，当且仅当：
也即是，每种颜色最多组合出 (lfloorfrac{cnt_c}2 floor) 组相同元素对，并将其求和。对 ((1)) 变形：
由 ((2))，产生了一些特判：当 (n<2m)，非负数之和不可能小于 (0)，答案为 (0)；当 (Dle n-2m)，等式恒成立（颜色总数仅 (D)），答案为 (D^n)。
接下来，令 (g_i) 表示恰好有 (i) 个 (cnt_cmod2=1) 的方案数。即 (g_i=sum_{cnt}[sum_{c=1}^Dcnt_cmod2=i])。可以发现最终答案为 (sum_{c=0}^{n-2m}g_c)，即 ((2)) 的等式左边所有满足条件的取值的方案数之和。
然后容斥 (g)：令 (f_i) 为至少有 (i) 个 (cnt_cmod2=1) 的方案数。注意：(f) 考虑了与 (g) 的容斥关系。更细致地阐释，(f_i) 表示先保证有 (i) 个颜色为奇数的前提下，其它颜色任意选的方案总数。如此一来，对于任意 (ige j)， (g_i) 会对 (f_j) 贡献 (ichoose j) 次——在 (i) 中选 (j) 个“保底”，其余 (i-j) 个成为“任意选”方案中的若干种。则：
利用二项式反演，对 ((3)) 变形：
可以发现，在最后一个式子的求和中，点乘号左右两边分别是关于 (j) 和 (i-j) 的函数，那么 (g) 实际上就是一个卷积的形式。只要求出 (f) 即可。
回顾 (f) 的定义，并尝试引入指数型生成函数。考虑到对于序列 (C={1,1,1,dots})，其生成函数为 (G_e(C)=sum_ifrac{x^i}{i!}=e^x)；对于序列 (O={0,1,0,1,dots})，其生成函数为 (G_e(O)=frac{x_1}{1!}+frac{x_3}{3!}+frac{x_5}{5!}+cdots=frac{e^x-e^{-x}}2)。同时，记 ([x^n]f(x)) 表示函数 (f(x)) 的 (n) 次项系数，则有：
先停下来理解：
-
第一项 (Dchoose i)，先钦定 (D) 种颜色中的 (i) 个为必须奇数。别忘了 (f) 定义，其余颜色也可以为奇数，它们是任意的。
-
第二项 (n!)，是约掉指数生成函数第 (n) 项的 (frac{1}{n!})。比如 ([x^3]G_e(C)=frac{1}{3!})，需要乘上 (frac{1}{3!}) 才为 (1)。
-
第三项 ([x^n]left(G_e^i(O)G_e^{D-i}(C) ight))，正如一般的卷积，生成函数的卷积表现了在不同集合中选择的方案。该式中卷积的第 (n) 项就表示选择 (i) 个奇数，再任选 (D-i) 个非负数，使得其和恰为 (n) 的方案数。可以结合最初的题意理解。
理解之后，着手对 ((5)) 变形（注意所有的 (i) 均为下标，而非虚数单位）：
利用二项式定理，展开 ((6)) 中的 ((e^x-e^{-x})^i)，得：
发现 (e^{(D+2j-2i)x}) 是形如 (e^{ax}) 的形式，而 (e^{ax}) 是序列 ({a^0,a^1,a^2,dots}) 的生成函数。所以其 (n) 次项应为 (frac{a^n}{n!})。则 ([x^n]e^{(D+2j-2i)x}=frac{(D+2j-2i)^n}{n!})。将其代入 ((7)) 并整理：
把 ((8)) 朝着卷积的形式靠近，即分开 (i-j) 与 (j)。为了美观，令 (k=i-j)，则 (j=i-k)。推出：
此时，和式已经是卷积的形式。
到此，利用 NTT，通过 ((9)) 求出 (f)，再通过 ((4)) 求出 (g)，最后求得答案为 (sum_{c=0}^{n-2m}g_c)，并记得特判 ((2)) 所引出的两种情况，这道题就解决啦~
代码
#include <cstdio>
const int MOD = 998244353, G = 3, INV2 = ( MOD + 1 ) >> 1, MAXD = 1 << 18;
int D, n, m, inv[MAXD + 5], fac[MAXD + 5], ifac[MAXD + 5];
int A[MAXD + 5], B[MAXD + 5], rev[MAXD + 5];
inline int qkpow ( int a, int b, const int p = MOD ) {
int ret = 1;
for ( ; b; a = 1ll * a * a % p, b >>= 1 ) ret = 1ll * ret * ( b & 1 ? a : 1 ) % p;
return ret;
}
inline void NTT ( const int n, int* a, const int tp ) {
for ( int i = 0; i < n; ++ i ) {
if ( i < rev[i] ) {
a[i] ^= a[rev[i]] ^= a[i] ^= a[rev[i]];
}
}
for ( int i = 2, stp = 1; i <= n; i <<= 1, stp <<= 1 ) {
int w = qkpow ( G, ( MOD - 1 ) / i );
if ( ! ~ tp ) w = qkpow ( w, MOD - 2 );
for ( int j = 0; j < n; j += i ) {
for ( int k = j, r = 1; k < j + stp; ++ k, r = 1ll * r * w % MOD ) {
int ev = a[k], ov = 1ll * a[k + stp] * r % MOD;
a[k] = ( ev + ov ) % MOD, a[k + stp] = ( ev - ov + MOD ) % MOD;
}
}
}
if ( ! ~ tp ) {
int rvn = qkpow ( n, MOD - 2 );
for ( int i = 0; i < n; ++ i ) a[i] = 1ll * a[i] * rvn % MOD;
}
}
inline void polyConv ( int lenA, int lenB, int* A, int* B, int* C ) {
int lenC = lenA + lenB - 1, len = 1, lg = 0;
for ( ; len < lenC; len <<= 1, ++ lg );
for ( int i = 0; i < len; ++ i ) rev[i] = ( rev[i >> 1] >> 1 ) | ( ( i & 1 ) << lg >> 1 );
static int tmpA[MAXD + 5], tmpB[MAXD + 5];
for ( int i = 0; i < len; ++ i ) {
tmpA[i] = i < lenA ? A[i] : 0;
tmpB[i] = i < lenB ? B[i] : 0;
}
NTT ( len, tmpA, 1 ), NTT ( len, tmpB, 1 );
for ( int i = 0; i < len; ++ i ) C[i] = 1ll * tmpA[i] * tmpB[i] % MOD;
NTT ( len, C, -1 );
}
inline void init () {
inv[1] = fac[1] = ifac[1] = fac[0] = ifac[0] = 1;
for ( int i = 2; i <= D; ++ i ) {
fac[i] = 1ll * i * fac[i - 1] % MOD;
inv[i] = 1ll * ( MOD - MOD / i ) * inv[MOD % i] % MOD;
ifac[i] = 1ll * inv[i] * ifac[i - 1] % MOD;
}
}
int main () {
scanf ( "%d %d %d", &D, &n, &m );
if ( m << 1 > n ) return puts ( "0" ), 0;
if ( m << 1 <= n - D ) return printf ( "%d
", qkpow ( D, n ) ), 0;
init ();
for ( int i = 0; i <= D; ++ i ) {
A[i] = 1ll * qkpow ( ( D - 2 * i + MOD ) % MOD, n ) * ( i & 1 ? MOD - ifac[i] : ifac[i] ) % MOD;
B[i] = ifac[i];
}
polyConv ( D + 1, D + 1, A, B, A );
for ( int i = 0; i <= D; ++ i ) {
A[i] = 1ll * A[i] * fac[D] % MOD * fac[i] % MOD * qkpow ( INV2, i ) % MOD * ifac[D - i] % MOD;
B[D - i] = i & 1 ? MOD - ifac[i] : ifac[i];
}
polyConv ( D + 1, D + 1, A, B, A );
int ans = 0;
for ( int i = 0; i <= n - 2 * m; ++ i ) ans = ( ans + 1ll * ifac[i] * A[D + i] ) % MOD;
printf ( "%d
", ans );
return 0;
}