一个长度为(n)的序列，每个位置可以自由填(1-D)，问有多少种情况使得序列中可以找出(m)对相同的数
假设数字(i)出现了(sum_i)次，那么需要满足
[sumlimits_{i=1}^{D}lfloorfrac{sum_i}{2}
floorge m
]
[sumlimits_{i=1}^{D}frac{sum_i-sum_i\%2}{2}ge m
]
[sumlimits_{i=1}^{D}sum_i-sum_i\%2ge 2*m
]
[n-sumlimits_{i=1}^{D}sum_i\%2ge 2*m
]
[sumlimits_{i=1}^{D}sum_i\%2le n-2*m
]
设恰好有(i)个颜色数为奇数的方案数为(g_i),那么(ans=sumlimits_{i=0}^{n-2m}g_i)
设(f_i)为有(i)种颜色数量是奇数，其他颜色数随便的方案数，可以得到
[f_i=sumlimits_{j=i}^{D}dbinom{j}{i}g_j
]
根据二项式反演有
[g_i=sumlimits_{j=i}^{D}(-1)^{j-i}dbinom{j}{i}f_j
]
考虑求一波(f_i)
颜色出现次数为奇数的(EGF{0,1,0,1,0,1,……})为(frac{e^x-e^{-x}}{2})
其他颜色随便排列的(EGF{1,1,1,1,1,……})为(e^x)
根据(EGF)得到
[f_i=dbinom{D}{i}n^i(e^x)^{D-i}
]
[=dbinom{D}{i}frac{n!}{2^i}[x^n](e^x-e^{-x})^i(e^x)^{D-i}
]
将中间二项式展开
[=dbinom{D}{i}frac{n!}{2^i}[x^n]sumlimits_{j=0}^{i}dbinom{i}{j}(e^x)^{j}(-e^{-x})^{i-j}(e^x)^{D-i}
]
[=dbinom{D}{i}frac{n!}{2^i}sumlimits_{j=0}^{i}dbinom{i}{j}(-1)^{i-j}[x^n]e^{(D-2(i-j))x}
]
根据(e^{ax}=sumlimitsfrac{a^n}{n!}),代入得到
[=dbinom{D}{i}frac{n!}{2^i}sumlimits_{j=0}^{i}dbinom{i}{j}(-1)^{i-j}frac{(D-2(i-j))^n}{n!}
]
我们由枚举(j)变为枚举(i-j)得到
[=dbinom{D}{i}frac{n!}{2^i}sumlimits_{j=0}^{i}dbinom{i}{j}(-1)^jfrac{(D-2j)^n}{n!}
]
展开组合数
[=frac{D!}{(D-i)!2^i}sumlimits_{j=0}^{i}frac{(-1)^j(D-2j)^n}{j!}*frac{1}{(i-j)!}
]
显然右边是个卷积，可以(O(DlogD))求(f_i)
再考虑
[g_i=sumlimits_{j=i}^{D}(-1)^{j-i}dbinom{j}{i}f_j
]
将组合数拆开
[g_i=sumlimits_{j=i}^{D}(-1)^{j-i}frac{j!}{i!(j-i)!}f_j
]
[g_i=frac{1}{i!}sumlimits_{j=0}^{D-i}frac{(-1)^j}{j!}(i+j)!f_{i+j}
]
设(a_i=frac{(-1)^i}{i!},b_i=i!f_i)，(a^{'})为(a)的翻转，得到
[c_{D+i}=sumlimits_{j=0}^{D-i}frac{(-1)^j}{j!}(i+j)!f_{i+j}=sumlimits_{j=0}^{D-i}a^{'}_{D-j}b_{i+j}
]
也是一个卷积，可以(O(DlogD))求解
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
inline int read()
{
int x=0;char ch,f=1;
for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
if(ch=='-') f=0,ch=getchar();
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f?x:-x;
}
const int N=4e5+10,p=998244353,inv2=(p+1)>>1;
int D,n,m,ans;
int fac[N],inv[N];
int f[N],g[N];
int limit=1,len;
int pos[N];
inline int fast(int x,int k)
{
int ret=1;
while(k)
{
if(k&1) ret=ret*x%p;
x=x*x%p;
k>>=1;
}
return ret;
}
inline void ntt(int *a,int inv)
{
for(int i=0;i<limit;++i)
if(i<pos[i]) swap(a[i],a[pos[i]]);
for(int mid=1;mid<limit;mid<<=1)
{
int Wn=fast(3,(p-1)/(mid<<1));
for(int r=mid<<1,j=0;j<limit;j+=r)
{
int w=1;
for(int k=0;k<mid;++k,w=w*Wn%p)
{
int x=a[j+k],y=w*a[j+k+mid]%p;
a[j+k]=(x+y)%p;
a[j+k+mid]=(x-y+p)%p;
}
}
}
if(inv) return;
inv=fast(limit,p-2);reverse(a+1,a+limit);
for(int i=0;i<limit;++i) a[i]=a[i]*inv%p;
}
inline void main()
{
D=read(),n=read(),m=read();
if(D<=n-2*m) return(void)(printf("%lld
",fast(D,n)));
if(2*m>n) return(void)puts("0");
for(int i=fac[0]=1;i<=D;++i) fac[i]=fac[i-1]*i%p;
inv[D]=fast(fac[D],p-2);
for(int i=D-1;~i;--i) inv[i]=inv[i+1]*(i+1)%p;
for(int i=0;i<=D;++i) f[i]=fast((D-2*i+p)%p,n)*(i&1?p-inv[i]:inv[i])%p;
for(int i=0;i<=D;++i) g[i]=inv[i];
while(limit<=2*D) limit<<=1,++len;
for(int i=1;i<limit;++i) pos[i]=(pos[i>>1]>>1)|((i&1)<<(len-1));
ntt(f,1);ntt(g,1);
for(int i=0;i<limit;++i) f[i]=f[i]*g[i]%p;
ntt(f,0);
for(int i=0;i<=D;++i) f[i]=f[i]*fac[D]%p*fac[i]%p*inv[D-i]%p*fast(inv2,i)%p;
for(int i=0;i<=D;++i) g[D-i]=(i&1)?p-inv[i]:inv[i];
for(int i=D+1;i<limit;++i) f[i]=g[i]=0;
ntt(f,1);ntt(g,1);
for(int i=0;i<limit;++i) f[i]=f[i]*g[i]%p;
ntt(f,0);
for(int i=0;i<=n-2*m;++i) ans=(ans+f[i+D]*inv[i])%p;
printf("%lld
",ans);
}
}
signed main()
{
red::main();
return 0;
}