[Luogu 4491] [HAOI2018]染色

Posted on | Edited on | In , | Views:

题目链接

Luogu 4491

做法

做反演题已经做到看到恰好就非常敏感了。

令$g_i$表示出现恰好$S$次的颜色至少$i$种的方案数，$f_i$表示出现恰好$S$次的颜色恰好$i$种的方案数。
先计算$g_i$,我们就钦定这些颜色是哪些颜色，哪些位置，其他随便放就行了。

而显然

二项式反演就可以得到

而现在我们要求的就是$f_{0..m}$，如果直接算的话复杂度为$m^2$。
可以把$f$数组看成一个多项式，由$g$这个多项式乘上另一个多项式得到。
考虑如何构造多项式。
先把枚举$j$改为枚举$j-i$，从0开始比较方便多项式乘法。
组合数也不好处理，用阶乘暴力展开，那么原式可以化为

发现$(i+j)!$和$g_{i+j}$都与$i+j$有关，那么把它们合并，再转个头即$g’_i=g_{m-i}*(m-i)!$
而$\frac{1}{i!}$至于i有关，那么我们算出f后再乘上就行了，暂时不用管。
经过上面两步的变换后，式子变成了这样

发现还是对不上，我们把$f$也转个头，即$f’_{m-i}=f_i$，那么

就是一个标准的卷积形式了。
我们$NTT$做完后，把上面那些操作都做逆操作就可以了。
最后注意一下$1004535809$这个模数的原根也是$3$

代码

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
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define N (10000005)
using namespace std;
int n,m,s,ans,d,size=1e7,lim,G=3;
int f[N],jc[N],inv[N],A[N],w[N],g[N],R[N];
const int P=1004535809; 
template <typename T> void read(T&t) {
    t=0;
    bool fl=true;
    char p=getchar();
    while (!isdigit(p)) {
        if (p=='-') fl=false;
        p=getchar();
    }
    do {
        (t*=10)+=p-48;p=getchar();
    }while (isdigit(p));
    if (!fl) t=-t;
}
inline int Inc(int a,int b){
    return (a+b>=P)?(a+b-P):(a+b);
}
inline int ksm(int a,int b){
    int ret=1;
    for (;b;b>>=1,a=1ll*a*a%P) if (b&1) ret=1ll*ret*a%P;
    return ret;
}
inline int C(int a,int b){
    return 1ll*jc[a]*inv[b]%P*inv[a-b]%P;
}
inline void NTT(int *f,int G){
    for (int i=0;i<lim;i++){
        if (i>R[i]) swap(f[i],f[R[i]]);
    }
    for (int i=1;i<lim;i<<=1){
        int w0=ksm(G,(P-1)/(i<<1));
        for (int j=0;j<lim;j+=i<<1){
            int w=1;
            for (int k=j;k<j+i;k++){
                int t=1ll*f[k+i]*w%P;
                f[k+i]=Inc(f[k]-t,P);
                f[k]=Inc(f[k],t);
                w=1ll*w*w0%P;
            }
        }
    }
    if (G!=3){
        int invl=ksm(lim,P-2);
        for (int i=0;i<lim;i++) f[i]=1ll*f[i]*invl%P;
    }
}
int main(){
    read(n),read(m),read(s);
    d=1;
    jc[0]=1;
    for (int i=1;i<=size;i++) jc[i]=1ll*jc[i-1]*i%P;
    A[0]=A[1]=1;
    for (int i=2;i<=size;i++) A[i]=Inc(-1ll*P/i*A[P%i]%P,P);
    inv[0]=1;
    for (int i=1;i<=size;i++) inv[i]=1ll*inv[i-1]*A[i]%P;
    for (int i=0;i*s<=n&&i<=m;i++){
        g[i]=1ll*C(m,i)*C(n,i*s)%P*jc[i*s]%P*ksm(m-i,n-i*s)%P*ksm(ksm(jc[s],i),P-2)%P;
        g[i]=1ll*g[i]*jc[i]%P;
    }
    for (int i=0;i<=m/2;i++) swap(g[i],g[m-i]);
    for (int i=0;i<=m;i++){
        if (i&1) f[i]=P-inv[i];
        else f[i]=inv[i];
    }
    for (lim=1;lim<2*(m+2);lim<<=1);
    for (int i=0;i<lim;i++) R[i]=(R[i>>1]>>1)|((i&1)*lim>>1);    
    NTT(f,G),NTT(g,G);
    for (int i=0;i<lim;i++) f[i]=1ll*f[i]*g[i]%P;
    NTT(f,ksm(G,P-2));
    for (int i=0;i<=m;i++){
        read(w[i]);
        ans=Inc(ans,1ll*w[i]*f[m-i]%P*inv[i]%P);
    }
    printf("%d",ans);
    return 0;
}