LOJ #2527 Luogu P4491「HAOI2018」染色

好像网上没人....和我推出....同一个式子啊.....

LOJ #2527 Luogu P4491

题意

$ n$个格子中每个格子可以涂$ m$种颜色中的一种

若有$ k$种颜色恰好涂了$ s$格则产生$ w_k$的价值

求所有涂色方案的价值和

$ solution$

按常规套路先容斥

设 $f_x$表示恰好有$ x$种颜色涂了恰好$s$格的方案数，

$ g_x$表示至少有$ x$种颜色涂了恰好$ s$格的方案数

有

$ ans=\sum\limits_{i=0}^mw_if_i$

$ f_x=\sum\limits_{i=x}^m (-1)^{i-x}\binom{i}{x}g_i$

$ g_x=\binom{m}{x}\binom{n}{sx}\frac{(sx)!}{(s!)^x}(m-x)^{n-sx}$

其中$ g_x$的意义即为选出$x$种颜色，选出$ sx$个格子放置这些颜色，

并将其他$ m-x$种颜色在其他格子乱放的方案数

因此有

$ans=\sum\limits_{i=0}^mw_i\sum\limits_{j=i}^m(-1)^{j-i}\binom{j}{i}g_j$

将组合数展开成阶乘得

$ans=\sum\limits_{i=0}^mw_i\sum\limits_{j=i}^m(-1)^{j-i}\frac{j!}{i!(j-i)!}g_j$

设

$F_x=\frac{(-1)^x}{x}$，$G_x=g_xx!$

则有

$ans=\sum\limits_{i=0}^m\frac{w_i}{i!}\sum\limits_{j=i}^mF_{j-i}G_j$

将$ F$或$ G$反转之后后式是一个卷积形式
而$F$和$G$都可以快速计算
$NTT$优化即可

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

$ my \ code$

#include<ctime>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<queue>

#define p 1004535809

#define rt register int

#define ll long long

using namespace std;

inline char __getchar(){

    static const int IN_LEN = ;

    static char buf[IN_LEN], *s, *t;

    return (s == t ? t = (s = buf) + fread(buf, , IN_LEN, stdin), (s == t ? - : *s++) : *s++);

}

#define getchar() __getchar()

inline ll read(){

    ll x = ; char zf = ; char ch = getchar();

    while (ch != '-' && !isdigit(ch)) ch = getchar();

    if (ch == '-') zf = -, ch = getchar();

    while (isdigit(ch)) x = x *  + ch - '', ch = getchar(); return x * zf;

}

void write(ll y){if(y<)putchar('-'),y=-y;if(y>)write(y/);putchar(y%+);}

void writeln(const ll y){write(y);putchar('\n');}

int i,j,k,m,n,x,y,z,cnt;

int ksm(int x,int y){

    int ans=;

    for(rt i=y;i;i>>=,x=1ll*x*x%p)if(i&)ans=1ll*x*ans%p;

    return ans;

}

int njc[],jc[];

void init(int N){

    njc[]=njc[]=jc[]=jc[]=;

    for(rt i=;i<=N;i++)jc[i]=1ll*i*jc[i-]%p;

    njc[N]=ksm(jc[N],p-);

    for(rt i=N-;i>=;i--)njc[i]=1ll*njc[i+]*(i+)%p;

}

inline int C(int x,int y){return 1ll*jc[x]*njc[y]%p*njc[x-y]%p;}

int w[],g[],f[],R[];

void NTT(int n,int *A,int fla){

    for(rt i=;i<n;i++)if(i>R[i])swap(A[i],A[R[i]]);

    for(rt i=;i<n;i<<=){

        int w=ksm(,(p-)//i);

        for(rt j=;j<n;j+=(i<<)){

            int K=;

            for(rt k=;k<i;k++,K=1ll*K*w%p){

                int x=A[j+k],y=1ll*K*A[i+j+k]%p;

                A[j+k]=(x+y)%p;A[i+j+k]=(x-y)%p;

            }

        }

    }

    if(fla==-){

        reverse(A+,A+n);int invn=ksm(n,p-);

        for(rt i=;i<n;i++)A[i]=1ll*invn*A[i]%p;

    }

}

int main(){

    n=read();m=read();int s=read();

    ll ans=;init(max(n,m));

    for(rt i=;i<=m;i++)w[i]=read();

    for(rt j=,invv=;j<=m&&s*j<=n;j++,invv=1ll*invv*njc[s]%p)

    g[j]=1ll*C(m,j)*C(n,s*j)%p*jc[s*j]%p*invv%p*ksm(m-j,n-s*j)%p*jc[j]%p;

    for(rt i=,tag=;i<=m;i++,tag*=-)f[i]=tag*njc[i];

    reverse(f,f+m+);

    int lim=;while(lim<=m+m)lim<<=;

    for(rt i=;i<lim;i++)R[i]=(R[i>>]>>)|(i&)*(lim>>);

    NTT(lim,f,);NTT(lim,g,);

    for(rt i=;i<lim;i++)f[i]=1ll*f[i]*g[i]%p;

    NTT(lim,f,-);

    for(rt i=;i<=m;i++)(ans+=1ll*f[i+m]*w[i]%p*njc[i]%p)%=p;

    cout<<(ans+p)%p;

    return ;

}

巴特西

LOJ #2527 Luogu P4491「HAOI2018」染色

题意

$ solution$

$ my \ code$

最新文章

热门文章