Cptraser/ 三月 14, 2019/ 2019.3/ 0 comments

HAOI2018染色

题中的恰好按套路求至少然后容斥。

f(i)表示出现至少i种颜色为S的颜色方案数。

首先指定{m\choose i}种颜色,然后指定{n\choose iS}个位置。

同时乘上可重集的全排列\frac{(iS)!}{(S!)^i},同时剩下(m-i)种颜色,(n-iS)个位置,可以乱放(m-i)^{n-iS}

所以:

    \[f(i)={m\choose i}{n\choose iS}\frac{(iS)!}{(S!)^i}(m-i)^{n-iS}\]

根据广义容斥原理:

    \[Ans(k)=\sum_{i=k}(-1)^{|i-k|}{i\choose k}f(i)\]

那么:

    \[Ans(k)k!=\sum_{i=k}\frac{(-1)^{|i-k|}}{(i-k)!}f(i)i!\]

g(i)=f(im-i)(lim-i)!

    \[Ans(lim-k)(lim-k)!=\sum_{i=0}^{lim-k}\frac{(-1)^{i}}{i!}g(lim-k-i)\]

    \[H(n-k)=F(i)G(j)\ (i+j=n-k)\]

这道题卷积时将f(i)i!x^i的系数翻转,最后再翻回来即可。

#include <cstdio>
#include <algorithm>
using namespace std;

const int Maxn=2e7+5,Mod=1004535809;
int Ksm(int x,int y){int res=1;for(;y;y>>=1,x=(long long)x*x%Mod)if(y&1)res=(long long)res*x%Mod;return res;}
const int g=3,invg=Ksm(g,Mod-2);

namespace Poly{
    int r[Maxn];
    void NTT(int *A,int Opt,int len){
        for(int i=0;i<len;i++)if(i<r[i])swap(A[i],A[r[i]]);
        for(int i=1;i<len;i<<=1){
            long long Wn=Ksm(Opt>0?g:invg,(Mod-1)/(i<<1));
            for(int j=0;j<len;j+=(i<<1)){
                long long w=1;
                for(int k=0;k<i;k++,w=w*Wn%Mod){
                    long long x=A[j+k],y=w*A[i+j+k]%Mod;
                    A[j+k]=(x+y)%Mod,A[i+j+k]=(x-y+Mod)%Mod;
                }
            }
        }
        if(Opt<0)for(int i=0,inv=Ksm(len,Mod-2);i<len;i++)A[i]=(long long)A[i]*inv%Mod;
    }
}
using namespace Poly;

int H[Maxn],F[Maxn],G[Maxn],W[Maxn];
int N,M,S,lim;
long long Fac[Maxn],Inv[Maxn];

void pre(int n){
    Fac[0]=Fac[1]=Inv[0]=Inv[1]=1;
    for(int i=2;i<=n;i++)Fac[i]=Fac[i-1]*i%Mod;
    for(int i=2;i<=n;i++)Inv[i]=1ll*(Mod-Mod/i)*Inv[Mod%i]%Mod;
    for(int i=2;i<=n;i++)Inv[i]=Inv[i]*Inv[i-1]%Mod;
}
long long C(int x,int y){return (x<y)?0:(Fac[x]*Inv[y]%Mod*Inv[x-y]%Mod);}
long long Ans=0;

int main()
{
    scanf("%d%d%d",&N,&M,&S);pre(max(N,M)),lim=min(M,N/S);
    for(int i=0;i<=M;i++)scanf("%d",&W[i]);
    int len=1,L=0;while(len<=lim<<1)len<<=1,L++;
    for(int i=0;i<len;i++)r[i]=(r[i>>1]>>1)|((i&1)<<(L-1));
    for(int i=0;i<=lim;i++)
        F[i]=C(M,i)*C(N,i*S)%Mod*Fac[i*S]%Mod*Ksm(Inv[S],i)%Mod*Ksm(M-i,N-i*S)%Mod*Fac[i]%Mod;
    reverse(F,F+lim+1);
    for(int i=0;i<=lim;i++)G[i]=1ll*((i&1)?(Mod-1):1)*Inv[i]%Mod;
    NTT(F,1,len),NTT(G,1,len);
    for(int i=0;i<len;i++)F[i]=1ll*F[i]*G[i]%Mod;
    NTT(F,-1,len),reverse(F,F+lim+1);
    for(int i=0;i<=lim;i++)Ans=(long long)(Ans+(long long)W[i]*F[i]%Mod*Inv[i]%Mod)%Mod;
    printf("%d\n",Ans);
}
Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*