题意
有(D)种颜色。对于一个长度为(n)，取值(in[1,D])的序列，至少有(m)组相同的方案数
题解
记颜色(c)有(cnt_c)个，一种方案合法当且仅当：
[sum_{i=1}^Dcnt_imod 2le m
]
简单推导得到：
[sum_{i=1}^Dcnt_imod 2le n-2m
]
先把(n-2m<0)与(n-2m≥D)特判掉。
记恰好有(k)个为奇数方案为(g_k)，至少有(k)个为奇数的方案为(f_k)。容斥一波。
[f_i=sum_{j} binom{i}{j}g_j
]
反演。
[egin{aligned}
g_i=&sum_{j}(-1)^{j-i} binom{j}{i}f_j\
=&sum_{j}(-1)^{j-i}frac{j!}{i!(j-i)!}f_j\
=&frac{1}{i!}sum_{j}frac{(-1)^{j-i}}{(j-i)!} imes j!f_j\
end{aligned}]
如果我们记(a_{D-i}=frac{(-1)^i}{i!},b_i=i!f_i,c_{D+i}=i!g_i)，有：
[c_{D+i}=sum_{j}a_{D-j+i} imes b_{j}
]
卷积形式十分明显。
( ext{方案数=选k个} imes ext{强制奇数} imes{放任自流})
[egin{aligned}
f_k=& binom{D}{k}n(e^x)^{D-k}\
=& binom{D}{k}frac{n!}{2^k}[x^n](e^x-e^{-x})^k(e^x)^{D-k}\
=& binom{D}{k}frac{n!}{2^k}[x^n]sum_{j=0}^k
binom{k}{j}e^{xj}(-e^x)^{-(j-k)}(e^x)^{D-k}\
=& binom{D}{k}frac{n!}{2^k}[x^n]sum_{j=0}^k
binom{k}{j}e^{xj}(-e^{-x})^{-(j-k)}(e^x)^{D-k}\
=& binom{D}{k}frac{n!}{2^k}[x^n]sum_{j=0}^k
binom{k}{j}(-1)^{k-j}e^{x(D-2(k-j))}
end{aligned}]
(e^x=1+frac{x}{1!}+frac{x^2}{2!}+frac{x^3}{3!}+ldots)
(e^{ax}=1+frac{ax}{1!}+frac{a^2x^2}{2!}+frac{a^3x^3}{3!}+ldots)
即(e^{ax})为(mathbb{EGF}<1,a,a^2,a^3,dots>)，([x^n]e^{ax}=frac{a^n}{n!})
那就带回去：
[egin{aligned}
=& binom{D}{k}frac{1}{2^k}sum_{j=0}^k
binom{k}{j}(-1)^{k-j}(D-2(k-j))^n\
=&frac{D!}{k!(D-k)!}frac{1}{2^k}sum_{j=0}^k
frac{k!}{j!(k-j)!}(-1)^{k-j}(D-2(k-j))^n\
=&frac{D!}{(D-k)!2^k}sum_{j=0}^k
frac{1}{(k-j)!j!}(-1)^j(D-2j)^n\
=&frac{D!}{(D-k)!2^k}sum_{j=0}^k
frac{(-1)^j(D-2j)^n}{j!} imesfrac{1}{(k-j)!}\
end{aligned}]
代码
#include<bits/stdc++.h>
namespace in{
#ifdef slow
inline int getc(){return getchar();}
#else
char buf[1<<21],*p1=buf,*p2=buf;
inline int getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
#endif
template <typename T>inline void read(T& t){
t=0;int f=0;char ch=getc();while (!isdigit(ch)){if(ch=='-')f = 1;ch=getc();}
while(isdigit(ch)){t=t*10+(ch-48);ch = getc();}if(f)t=-t;
}
template <typename T,typename... Args> inline void read(T& t, Args&... args){read(t);read(args...);}
}
namespace out{
char buffer[1<<21];int p1=-1;const int p2 = (1<<21)-1;
inline void flush(){fwrite(buffer,1,p1+1,stdout),p1=-1;}
inline void putc(const char &x) {if(p1==p2)flush();buffer[++p1]=x;}
template <typename T>void write(T x) {
static char buf[15];static int len=-1;if(x>=0){do{buf[++len]=x%10+48,x/=10;}while (x);}else{putc('-');do {buf[++len]=-(x%10)+48,x/=10;}while(x);}
while (len>=0)putc(buf[len]),--len;
}
}
using namespace std;
template<const int mod>
struct modint{
int x;
modint<mod>(int o=0){x=o;}
modint<mod> &operator = (int o){return x=o,*this;}
modint<mod> &operator +=(modint<mod> o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
modint<mod> &operator -=(modint<mod> o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
modint<mod> &operator *=(modint<mod> o){return x=1ll*x*o.x%mod,*this;}
modint<mod> &operator ^=(int b){
modint<mod> a=*this,c=1;
for(;b;b>>=1,a*=a)if(b&1)c*=a;
return x=c.x,*this;
}
modint<mod> &operator /=(modint<mod> o){return *this *=o^=mod-2;}
modint<mod> &operator +=(int o){return x=x+o>=mod?x+o-mod:x+o,*this;}
modint<mod> &operator -=(int o){return x=x-o<0?x-o+mod:x-o,*this;}
modint<mod> &operator *=(int o){return x=1ll*x*o%mod,*this;}
modint<mod> &operator /=(int o){return *this *= ((modint<mod>(o))^=mod-2);}
template<class I>friend modint<mod> operator +(modint<mod> a,I b){return a+=b;}
template<class I>friend modint<mod> operator -(modint<mod> a,I b){return a-=b;}
template<class I>friend modint<mod> operator *(modint<mod> a,I b){return a*=b;}
template<class I>friend modint<mod> operator /(modint<mod> a,I b){return a/=b;}
friend modint<mod> operator ^(modint<mod> a,int b){return a^=b;}
friend bool operator ==(modint<mod> a,int b){return a.x==b;}
friend bool operator !=(modint<mod> a,int b){return a.x!=b;}
bool operator ! () {return !x;}
modint<mod> operator - () {return x?mod-x:0;}
modint<mod> &operator++(int){return *this+=1;}
};
const int N=4e6+5;
const int mod=998244353;
const modint<mod> GG=3,Ginv=modint<mod>(1)/3,I=86583718;
struct poly{
vector<modint<mod>>a;
modint<mod>&operator[](int i){return a[i];}
int size(){return a.size();}
void resize(int n){a.resize(n);}
};
int rev[N];
inline int ext(int n){int k=0;while((1<<k)<n)k++;return k;}
inline void init(int k){int n=1<<k;for(int i=0;i<n;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1));}
inline void ntt(poly&a,int k,int typ){
int n=1<<k;
for(int i=0;i<n;i++)if(i<rev[i])swap(a[i],a[rev[i]]);
for(int mid=1;mid<n;mid<<=1){
modint<mod> wn=(typ>0?GG:Ginv)^((mod-1)/(mid<<1));
for(int r=mid<<1,j=0;j<n;j+=r){
modint<mod> w=1;
for(int k=0;k<mid;k++,w=w*wn){
modint<mod> x=a[j+k],y=w*a[j+k+mid];
a[j+k]=x+y,a[j+k+mid]=x-y;
}
}
}
if(typ<0){
modint<mod> inv=modint<mod>(1)/n;
for(int i=0;i<n;i++)a[i]*=inv;
}
}
inline poly operator*(poly a,poly b){
int n=a.size()+b.size()-1,k=ext(n);
a.resize(1<<k),b.resize(1<<k),init(k);
ntt(a,k,1);ntt(b,k,1);for(int i=0;i<(1<<k);i++)a[i]*=b[i];
ntt(a,k,-1),a.resize(n);return a;
}
poly a,b;
int d,n,m;
modint<mod>fac[N],ans;
signed main(){
fac[0]=1;for(int i=1;i<N;i++)fac[i]=fac[i-1]*i;
in::read(d,n,m);
if(n-2*m<0)cout<<0,exit(0);
if(n-2*m>=d)cout<<(modint<mod>(d)^n).x,exit(0);
a.resize(d+1);b.resize(d+1);
for(int i=0;i<=d;i++)a[i]=(modint<mod>(d-2*i+mod)^n)/fac[i],(i&1)&&(a[i]=-a[i]).x;
for(int i=0;i<=d;i++)b[i]=modint<mod>(1)/fac[i];
a=a*b;a.resize(d+1);
for(int i=0;i<=d;i++)a[i]=a[i]*fac[d]/(fac[d-i]*(modint<mod>(2)^i))*fac[i];
for(int i=0;i<=d;i++)b[d-i]=modint<mod>(1)/fac[i],(i&1)&&(b[d-i]=-b[d-i]).x;
a=a*b;for(int i=0;i<=n-2*m;i++)ans+=a[d+i]/fac[i];
out::write(ans.x);out::flush();
}