Luogu

LOJ

分析

首先题目要求的其实就是方案数。

设 $cnt_i$ 表示颜色为 $i$ 的珍珠的数量，那么如果一组方案合法的话会有
$$
\begin{aligned}
&\sum_{i=1}^D\left\lfloor\frac{cnt_i}{2}\right\rfloor\geq m\\
\Longrightarrow&\sum_{i=1}^D\frac{cnt_i-cnt_i\bmod 2}{2}\geq m\\
\Longrightarrow&\sum_{i=1}^D cnt_i-cnt_i\bmod 2\geq 2m\\
\Longrightarrow&n-\sum_{i=1}^Dcnt_i\bmod 2\geq 2m\\
\Longrightarrow&\sum_{i=1}^Dcnt_i\bmod 2\leq n-2m
\end{aligned}
$$
设 $g_i$ 表示恰好有 $i$ 个 $cnt_i$ 为奇数的方案数，那么答案就是 $\sum_{i=0}^{n-2m}g_i$ 。

考虑容斥。设 $f_i$ 表示至少有 $i$ 个 $cnt_i$ 为奇数的方案数。

那么有
$$
f_i=\sum_{j=i}^D{j\choose i}g_j
$$
二项式反演得到
$$
g_i=\sum_{j=i}^D(-1)^{j-i}{j\choose i}f_j
$$
拆掉组合数可以得到
$$
\begin{aligned}
g_i&=\sum_{j=i}^D(-1)^{j-i}\frac{j!}{i!(j-i)!}f_j\\
&=\frac{1}{i!}\sum_{j=i}^Dj!f_j\cdot\frac{(-1)^{j-i}}{(j-i)!}\\
&=\frac{1}{i!}\sum_{j=i}^Dj!f_j\cdot\frac{(-1)^{i-j}}{[-(i-j)]!}
\end{aligned}
$$
显然是卷积的形式。

考虑怎么求 $f_i$ 。

考虑出现次数为奇数的 EGF ，可以发现是 $\frac{e^x-e^{-x}}{2}$ 。

那么有
$$
\begin{aligned}
f_i&={D\choose i}n![x^n]\left(\frac{e^x-e^{-x}}{2}\right)^i(e^x)^{D-i}\\
&={D\choose i}\frac{n!}{2^i}[x^n](e^x-e^{-x})^i(e^x)^{D-i}\\
\end{aligned}
$$
用二项式定理展开 $(e^x-e^{-x})^i$ ，得到
$$
\begin{aligned}
f_i&={D\choose i}\frac{n!}{2^i}[x^n]\sum_{j=0}^i{i\choose j}e^{xj}(-e^x)^{i-j}(e^x)^{D-i}\\
&={D\choose i}\frac{n!}{2^i}\sum_{j=0}^i{i\choose j}(-1)^{i-j}[x^n]e^{(D-2(i-j))x}
\end{aligned}
$$
注意到 $ e^{ax}=\frac{1}{1}+\frac{a^1}{1}+\frac{a^2}{2}+\cdots$ ，那么有
$$
[x^n]e^{(D-2(i-j))x}=\frac{(D-2(i-j))^n}{n!}
$$
代回去得到
$$
\begin{aligned}
f_i&={D\choose i}\frac{n!}{2^i}\sum_{j=0}^i{i\choose j}(-1)^{i-j}\frac{(D-2(i-j))^n}{n!}\\
&=\frac{D!n!}{i!(D-i)!2^i}\sum_{j=0}^i\frac{i!}{j!(i-j)!}(-1)^{i-j}\frac{(D-2(i-j))^n}{n!}\\
&=\frac{D!}{2^i(D-i)!}\sum_{j=0}^i\frac{(-1)^j(D-2j)^n}{j!}\cdot\frac{1}{(i-j)!}
\end{aligned}
$$
显然也是一个卷积的形式。

于是只需要构造多项式求出 $f_i$ ，再构造多项式求出 $g_i$ ，再求答案即可。

另外注意特判 $2m<n-D$ 和 $2m>n$ 的情况，答案分别为 $D^n$ 和 $0$ 。

总结：这是一道好题，可是我什么都不会。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=400000+10;
const int mod=998244353;

inline int qpow(int a,int b) {
    int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod)
        if (b&1) c=1ll*c*a%mod;
    return c;
}

int r[N];
inline void NTT(int* A,int n,int op) {
    for (re int i=0;i<n;++i) if (i<r[i]) swap(A[i],A[r[i]]);
    for (re int i=1;i<n;i<<=1) {
        int rot=qpow(op==1?3:(mod+1)/3,(mod-1)/(i<<1));
        for (re int j=0;j<n;j+=(i<<1)) {
            int w=1;
            for (re int k=0;k<i;++k,w=1ll*w*rot%mod) {
                int x=A[j+k],y=1ll*w*A[j+k+i]%mod;
                A[j+k]=(x+y)%mod,A[j+k+i]=(x-y+mod)%mod;
            }
        }
    }
    if (op==-1) {
        int inv=qpow(n,mod-2);
        for (re int i=0;i<n;++i) A[i]=1ll*A[i]*inv%mod;
    }
}
inline void Mul(int* F,int n,int* G,int m,int* ans) {
    int lim=1,l=0;
    for (;lim<=n+m;lim<<=1,++l);
    for (re int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    static int A[N],B[N];
    for (re int i=0;i<n;++i) A[i]=F[i];
    for (re int i=n;i<lim;++i) A[i]=0;
    for (re int i=0;i<m;++i)  B[i]=G[i];
    for (re int i=m;i<lim;++i) B[i]=0;
    NTT(A,lim,1),NTT(B,lim,1);
    for (re int i=0;i<lim;++i) A[i]=1ll*A[i]*B[i]%mod;
    NTT(A,lim,-1);
    for (re int i=0;i<n+m-1;++i) ans[i]=A[i];
}

int D,n,m;
int fac[N],ifac[N];
int A[N],B[N],F[N],G[N];
int main() {
    D=read(),n=read(),m=read();

    if (2*m<n-D) { printf("%d\n",qpow(D,n)); return 0; }
    if (2*m>n) { puts("0"); return 0; }

    fac[0]=1;
    for (re int i=1;i<=D;++i) fac[i]=1ll*fac[i-1]*i%mod;
    ifac[D]=qpow(fac[D],mod-2);
    for (re int i=D;i;--i) ifac[i-1]=1ll*ifac[i]*i%mod;

    for (re int i=0;i<=D;++i) {
        int tmp=(i&1)?mod-ifac[i]:ifac[i];
        A[i]=1ll*qpow((D-2*i+mod)%mod,n)*tmp%mod;
    }
    for (re int i=0;i<=D;++i) B[i]=ifac[i];
    Mul(A,D+1,B,D+1,F);
    for (re int i=0;i<=D;++i) {
        F[i]=1ll*F[i]*fac[D]%mod;
        F[i]=1ll*F[i]*qpow((mod+1)/2,i)%mod;
        F[i]=1ll*F[i]*ifac[D-i]%mod;
    }

    for (re int i=0;i<=D;++i) A[i]=1ll*fac[i]*F[i]%mod;
    for (re int i=0;i<=D;++i) B[i]=(D-i)&1?mod-ifac[D-i]:ifac[D-i];
    Mul(A,D+1,B,D+1,G);

    int ans=0;
    for (re int i=0;i<=n-2*m;++i) ans=(ans+1ll*G[i+D]*ifac[i])%mod;
    printf("%d\n",ans);
    return 0;
}