珍珠[CTS2019]

题目链接

链接

题解

设第 $i$ 个颜色出现了 $a_i$ 次，那么当且仅当 $\sum_{i=1}^d\left \lfloor \frac{a_i}{2}\right \rfloor\leq m$ 时满足条件。

原式经转换得：$\sum a_i-a_i\bmod 2\leq 2m$。

因为有 $\sum_{i=1}^da_i=n$，那么有 $\sum_{i=1}^da_i\bmod 2\leq n-2m$。

那么设 $g_j$ 表示 $\sum_{i=1}^da_i\bmod 2=j$ 的方案数，最后 $\sum_{j=0}^{n-2m}g_j$ 就是答案。

这个 $g_j$ 很不好求，可以容斥一下，变成求至少为 $j$ 的方案数，设为 $f_i$。

那么有：$f_i=\sum_{j=i}^d\binom{j}{i}g_j$。

二项式反演得到：$g_i=\sum_{j=i}^d(-1)^{j-i}\binom{j}{i}f_j$，即：

$$g_i=\frac{1}{i!}\sum_{j=i}^d\frac{(-1)^{j-i}}{(j-i)!}\times j!f_j$$

显然是一个卷积形式，ntt即可，转换为求所有的 $f_i$。

那么就是在 $d$ 个颜色中钦定 $i$ 个，使得这 $i$ 个颜色都选了奇数个，其他任意的方案数。这里有 $\binom{d}{i}$ 种情况。

如果只要出现这 $i$ 个颜色当中出现了一个选了偶数，则这个方案贡献为 $0$，否则为 $1$。

如果颜色的出现次数为 $a_1,a_2\cdots,a_d$，则一共有 $\frac{n!}{\prod_{i=1}^da_i!}$ 种情况。这启发我们可以使用EGF来进行计数。

考虑那 $i$ 个颜色的EGF对应的序列是这样的：${0,1,0,1,0\cdots}$，也就是 $\frac{e^x-e^{-x}}{2}$。

其他颜色的EGF对应的序列是这样的：${1,1,1,1\cdots}$，为 $e^x$。

那么这一部分的答案为 $n! \left [ x ^ n \right ] (\frac{e^x-e^{-x}}{2})^i(e^x)^{d-i}$。

那么有：

$$f_i=\binom{d}{i}n^i(e^x)^{d-i}\=\frac{d!}{2^ii!(d-i)!}n^ie^{(d-i)x}\=\frac{d!}{2^ii!(d-i)!}n![x^n]\sum_{j=0}^i(-1)^{i-j}\binom{i}{j}e^{jx}e^{-(i-j)x}e^{(d-i)x}\=\frac{d!}{2^ii!(d-i)!}n![x^n]\sum_{j=0}^i(-1)^{i-j}\binom{i}{j}e^{(d-2(i-j))x}\=\frac{d!}{2^ii!(d-i)!}n!\sum_{j=0}^i(-1)^{i-j}\binom{i}{j}\frac{(d-2(i-j))^n}{n!}\=\frac{d!}{2^ii!(d-i)!}\sum_{j=0}^i(-1)^{i-j}\binom{i}{j}(d-2(i-j))^n\=\frac{d!}{2^i(d-i)!}\sum_{j=0}^i\frac{1}{j!}\times \frac{(-1)^{i-j}(d-2(i-j))^n}{(i-j)!}$$

这一部分也是一个卷积形式，ntt计算出 $f_i$ 即可。

时间复杂度 $O(n\log n)$。

程序

#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","W",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
    int x=0; char ch=getchar(); bool f=0;
    for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
    for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
    return f?-x:x;
}
#define CASET fo(___,1,read())
const ll mod=998244353;
const ll g=3;
inline ll Add(ll x,ll y){x+=y; return (x<mod)?x:x-mod;}
inline ll Dec(ll x,ll y){x-=y; return (x<0)?x+mod:x;}
inline ll Mul(ll x,ll y){return x*y%mod;}
inline ll Pow(ll x,ll y){y%=(mod-1);ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1) ans=ans*x%mod;return ans;}
const int N=270000;
namespace Poly{
    const int M=1<<18;
    int R[M]; ll W[M];
    inline void PolyInit()
    {
        ll wn;
        for(int i=1;i<M;i<<=1)
        {
            W[i]=1; wn=Pow(g,(mod-1)/2/i);
            fo(j,1,i-1) W[i+j]=W[i+j-1]*wn%mod;
        }
    }
    inline void ntt(ll *a,int n,int t)
    {
        fo(i,0,n-1)
        {
            R[i]=(R[i>>1]>>1)|((i&1)*(n/2));
            if(i<R[i]) swap(a[i],a[R[i]]);
        }
        ll w;
        for(int i=1;i<n;i<<=1)
            for(int j=0;j<n;j+=(i<<1))
                for(int k=0;k<i;k++)
                {
                    w=W[i+k]*a[i+j+k]%mod;
                    a[i+j+k]=Dec(a[j+k],w);
                    a[j+k]=Add(a[j+k],w);
                }
        if(t==1) return;
        reverse(a+1,a+n);
        w=Pow(n,mod-2);
        fo(i,0,n-1) a[i]=Mul(a[i],w);
    }
}
using namespace Poly;
int d,n,m;
ll A[N],B[N],fac[N],inv[N],f[N],C[N],ans;
int main()
{
    PolyInit();
    d=read(); n=read(); m=read();
    if(n-2*m<0) return printf("0")&0;
    if(n-2*m>=d) return printf("%lld",Pow(d,n))&0;
    int len=1;
    for(;len<=d+d+2;len<<=1);
    fac[0]=1;
    fo(i,1,d) fac[i]=fac[i-1]*i%mod;
    inv[d]=Pow(fac[d],mod-2);
    fd(i,d,1) inv[i-1]=inv[i]*i%mod;
    fo(i,0,d) A[i]=inv[i],B[i]=Mul(Pow(mod-1,i),Mul(inv[i],Pow(Dec(d,2*i),n)));
    ntt(A,len,1); ntt(B,len,1);
    fo(i,0,len) A[i]=A[i]*B[i]%mod;
    ntt(A,len,-1);
    fo(i,0,d) f[i]=Mul(fac[d],inv[d-i])*Mul(A[i],Pow(Pow(2,i),mod-2))%mod*fac[i]%mod;
    
    fo(i,0,d) C[d-i]=Mul(Pow(mod-1,i),inv[i]);
    ntt(f,len,1); ntt(C,len,1);
    fo(i,0,len) f[i]=f[i]*C[i]%mod;
    ntt(f,len,-1);
    fo(i,d,d+n-2*m) ans=Add(ans,Mul(f[i],inv[i-d]));
    printf("%lld",ans);
    return 0;
}