[HAOI 2018]染色

怼烎@ 2021-12-22 00:17 207阅读 0赞

## [ 传送门 ][Link 1] ##

## **Description**  ##

> 一个长度为\\(N\\)的序列, 每个位置都可以被染成 \\(M\\)种颜色中的某一种.
> 
> 出现次数恰好为 \\(S\\)的颜色种数有\\(i\\)种, 会产生\\(w\_i\\)的愉悦度.
> 
> 对于所有染色方案, 能获得的愉悦度的和对\\(1004535809\\)取模的结果.

## **Solution**  ##

> \\\[ ans=\\sum\_\{i=0\}^\{lim\} w\_i\\cdot num\_i \\\]
> 
> how to get \\(num\_i\\)?
> 
> \\(f\_i\\) : the number of occurrences of at least i colors is exactly the number of S
> 
> so \\(f\_i=\\binom\{m\}\{i\}\\cdot \\frac\{n!\}\{(s!)^i(n-iS)!\}\\cdot(m-i)^\{n-iS\}\\)
> 
> According to the binomial inversion, we can know that:  
> \\\[ num\_i=\\sum\_\{j=i\}^\{lim\}(-1)^\{j-i\}\\binom\{j\}\{i\}f\[j\] \\\]  
> so  
> \\\[ num\_i=\\frac\{1\}\{i!\}\\sum\_\{j=i\}^\{lim\} \\frac\{(-1)^\{j-i\}\}\{(j-i)!\}\\cdot(f\[j\]\\cdot j!) \\\]  
> we can use NTT.

## **Code**  ##

#include<bits/stdc++.h>
    #define reg register
    #define ll long long
    #define db double
    using namespace std;
    inline int read()
    {
        int x=0,f=1;char ch=getchar();
        while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
        return x*f;
    }
    const int P=1004535809,G[2]={3,334845270},NN=5e5+5;
    int Mul(int x,int y){return 1ll*x*y%P;}
    int Add(int x,int y){return (x+y)%P;}
    const int MN=1e7+5,MM=1e5+5,MS=155;
    int N,M,S,W[MM],f[MM],fac[MN],inv[MN];
    int fpow(int x,int y){int r=1;for(;y;y>>=1,x=Mul(x,x))if(y&1)r=Mul(r,x);return r;}
    int C(int x,int y){if(x<0||y<0||x<y)return 0;return Mul(fac[x],Mul(inv[y],inv[x-y]));}
    int a[NN],b[NN],pos[NN];
    void NTT(int *a,bool ty,int L)
    {
        reg int i,j,k,w,wn,x,y;
        for(i=0;i<L;++i) if(pos[i]<i) swap(a[i],a[pos[i]]);
        for(i=1;i<L;i<<=1)
        {
            wn=fpow(G[ty],(P-1)/(i<<1));
            for(j=0;j<L;j+=(i<<1))
                for(w=1,k=0;k<i;++k,w=Mul(w,wn))
                {
                    x=a[j+k],y=Mul(a[j+i+k],w);
                    a[j+k]=Add(x,y);a[j+i+k]=Add(x,P-y);
                }
        }
        if(ty)for(j=fpow(L,P-2),i=0;i<L;++i)a[i]=Mul(a[i],j);
    }
    int ans;
    int main()
    {
        N=read(),M=read(),S=read();
        reg int i,lim;
        for(i=0;i<=M;++i) W[i]=read();
        lim=max(N,M);
        for(fac[0]=i=1;i<=lim;++i) fac[i]=Mul(fac[i-1],i);
        for(inv[0]=inv[1]=1,i=2;i<=lim;++i) inv[i]=Mul(inv[P%i],(P-P/i));
        for(i=1;i<=lim;++i) inv[i]=Mul(inv[i],inv[i-1]);
        lim=min(M,N/S);
        for(i=0;i<=lim;++i)
            f[i]=Mul(Mul(C(M,i),Mul(fac[N],fpow(inv[S],i))),Mul(inv[N-i*S],fpow(M-i,N-i*S)));
        for(i=0;i<=lim;++i) b[lim-i+1]=Mul(f[i],fac[i]);
        for(i=0;i<=lim;++i) a[i]=(i&1)?(P-inv[i]):inv[i];
        int MA;
        for(MA=1;MA<=(lim<<1);MA<<=1);
        for(i=0;i<MA;++i) pos[i]=(pos[i>>1]>>1)|((i&1)*(MA>>1));
        NTT(a,0,MA);NTT(b,0,MA);
        for(i=0;i<MA;++i) a[i]=Mul(a[i],b[i]);
        NTT(a,1,MA);
        for(i=0;i<=lim;++i) ans=Add(ans,Mul(W[i],Mul(a[lim-i+1],inv[i])));
        return 0*printf("%d\n",ans);
    }

--------------------

Blog来自**PaperCloud**，未经允许，请勿转载，TKS！

转载于:https://www.cnblogs.com/PaperCloud/p/10925578.html

[Link 1]: https://loj.ac/problem/2527