「CTS2019 | CTSC2019」珍珠

发表于 分类于

题目链接：https://loj.ac/problem/3120

神仙题。。感觉我生成函数还是不过关啊。

首先假设当前方案有$x$种颜色出现次数为奇数，那么这种方案就可以装$(n-x)/2$个瓶子，也就是说题目可以转化为求至多有$n-m*2$种颜色出现次数为奇数的方案数。

到这里如果我们使用$dp$求解应该可以拿五十多分。

设$l=n-2m$。有一个这样的式子：

就是说一个位置填奇数的$\rm EGF$为$\dfrac{e^x-e^{-x}}{2}$。

同理填偶数为$\dfrac{e^x+e^{-x}}{2}$。

我们枚举当前有$k$种颜色出现次数为奇数，那么这个方案数的生成函数为：

就是说每个位置可以填奇数或偶数，要求奇数填了$k$个。

所以总答案就是：

前面乘$n!$是为了把指数型生成函数的阶乘去掉。

稍微化简一下可以得到：

把后半部分拉出来：

我们现在是要求前面的多项式前$l$项的系数之和，有一个这样的操作：

那么当$d=i$的时候暴力算一下，否则式子就变成了：

暴力二项式展开可以得到最后的答案长这样（其实还挺难算的）：

显然这是个卷积形式，用$\rm NTT$优化一下就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<bits/stdc++.h>
using namespace std;

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)

const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 998244353;

int n,m,d,a[maxn],b[maxn],fac[maxn],ifac[maxn],w[maxn],mxn,pos[maxn],bit;

int add(int x,int y) {x+=y;return x>=mod?x-mod:x;}
int del(int x,int y) {x-=y;x+=x>>31&mod;return x;}
int mul(int x,int y) {return 1ll*x*y-1ll*x*y/mod*mod;}

int qpow(int a,int x) {
    int res=1;
    for(;x;x>>=1,a=mul(a,a)) if(x&1) res=mul(res,a);
    return res;
}

void prepare() {
    for(mxn=1,bit=-1;mxn<=d<<1;mxn<<=1,bit++);
    for(int i=0;i<mxn;i++) pos[i]=pos[i>>1]>>1|((i&1)<<bit);
    w[0]=1,w[1]=qpow(3,(mod-1)/mxn);
    for(int i=2;i<=mxn;i++) w[i]=mul(w[i-1],w[1]);
    fac[0]=ifac[0]=1;
    for(int i=1;i<=mxn;i++) fac[i]=mul(fac[i-1],i);
    ifac[mxn]=qpow(fac[mxn],mod-2);
    for(int i=mxn-1;i;i--) ifac[i]=mul(ifac[i+1],i+1);
}

void ntt(int *r,int op) {
    for(int i=0;i<mxn;i++) if(pos[i]>i) swap(r[i],r[pos[i]]);
    for(int i=1,dd=mxn>>1;i<mxn;i<<=1,dd>>=1)
        for(int j=0;j<mxn;j+=i<<1)
            for(int k=0;k<i;k++) {
                int x=r[j+k],y=mul(w[k*dd],r[i+j+k]);
                r[j+k]=add(x,y),r[i+j+k]=del(x,y);
            }
    if(op==-1) {
        int dd=qpow(mxn,mod-2);reverse(r+1,r+mxn);
        for(int i=0;i<mxn;i++) r[i]=mul(r[i],dd);
    }
}

int c(int x,int y) {return mul(fac[x],mul(ifac[y],ifac[x-y]));}

int main() {
    read(d),read(n),read(m);int l=n-2*m;
    if(d<=l) return write(qpow(d,n)),0;
    prepare();
    for(int i=0;i<=l;i++) if(l-i<=d) a[i]=mul(ifac[i],ifac[l-i]),(l-i)&1?a[i]=del(0,a[i]),0:0;
    for(int i=0;i<=d-l-1;i++) b[i]=mul(ifac[i],ifac[d-l-1-i]);
    ntt(a,1),ntt(b,1);
    for(int i=0;i<mxn;i++) a[i]=mul(a[i],b[i]);
    ntt(a,-1);int ans=0;
    for(int i=0;i<d;i++) {
        int r=mul(mul(a[i],fac[i]),fac[d-i-1]);
        r=mul(r,qpow(del(2*i-d,0),n));
        r=mul(r,c(d,i));
        ans=add(ans,r);
    }
    for(int i=0;i<=min(d,l);i++) ans=add(ans,mul(qpow(d,n),c(d,i)));
    write(mul(ans,qpow(qpow(2,d),mod-2)));
    return 0;
}