M_sea

洛谷4491 [HAOI2018]染色
LuoguBZOJ分析首先,显然颜色数量不会超过$limit=\min\left\{m,n/s\right\}$考...
扫描右侧二维码阅读全文
28
2019/01

洛谷4491 [HAOI2018]染色

Luogu

BZOJ

分析

首先,显然颜色数量不会超过$limit=\min\left\{m,n/s\right\}$

考虑容斥。

设$f[i]$表示恰好出现$s$次的颜色至少有$i$种的方案数。

根据组合意义可以得到$\large f[i]=C_m^i\cdot\frac{n!}{(s!)^i(n-is)!}\cdot (m-i)^{n-is}$。

然后考虑怎么推答案。设$g[i]$表示恰好出现$s$次的颜色正好有$i$种的方案数。

然后,根据容斥原理,得到$\large g[i]=\sum\limits_{j=i}^{limit}(-1)^{j-i}C_j^i\;f[j]$。(当然也可以二项式反演得到这个东西)

然后这样子直接算答案是$O(n^2)$的。

拆式子,得到$\large g[i]=\sum\limits_{j=i}^{limit}(-1)^{j-i}\cdot\frac{j!}{i!(j-i)!}\cdot f[j]\implies g[i]\cdot i!=\sum\limits_{j=i}^{limit}\frac{(-1)^{j-i}}{(j-i)!}\cdot j!f[j]$。

显然是一个卷积的形式,然后就可以$O(n\log n)$地计算了。

注意模数不是$998244353$。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=10000000+10,M=100000+10;
const int MOD=1004535809;

int n,m,s;
int w[M],fact[N];
int A[300000],B[300000],r[300000];

inline int fastpow(int a,int b,int ans=1) {
    for (;b;b>>=1,a=1ll*a*a%MOD)
        if (b&1) ans=1ll*ans*a%MOD;
    return ans;
}
inline int inv(int x) { return fastpow(x,MOD-2); }
inline int C(int n,int m) {
    if (n<m) return 0;
    return 1ll*fact[n]*inv(fact[n-m])%MOD*inv(fact[m])%MOD;
}
inline int f(int i) {
    return 1ll*C(m,i)*fact[n]%MOD*inv(fastpow(fact[s],i))%MOD*inv(fact[n-i*s])%MOD*fastpow(m-i,n-i*s)%MOD;
}

const int G=3,Gi=inv(G);

inline void NTT(int* a,int n,int type) {
    for (re int i=0;i<n;++i)
        if (i<r[i]) swap(a[i],a[r[i]]);
    for (re int i=1;i<n;i<<=1) {
        int rot=fastpow(type==1?G:Gi,(MOD-1)/(i<<1));
        for (re int j=0;j<n;j+=(i<<1)) {
            int w=1;
            for (re int k=0;k<i;++k,w=1ll*w*rot%MOD) {
                int x=a[j+k],y=1ll*w*a[j+k+i]%MOD;
                a[j+k]=(x+y)%MOD,a[j+k+i]=(x-y+MOD)%MOD;
            }
        }
    }
    if (type==-1) {
        int invn=inv(n);
        for (re int i=0;i<n;++i) a[i]=1ll*a[i]*invn%MOD;
    }
}

int main() {
    n=read(),m=read(),s=read();
    for (re int i=0;i<=m;++i) w[i]=read();
    fact[0]=1;
    for (re int i=1;i<=max(n,m);++i) fact[i]=1ll*fact[i-1]*i%MOD;
    int lim=min(m,n/s);
    for (re int i=0;i<=lim;++i) A[i]=1ll*fact[i]*f(i)%MOD;
    for (re int i=0;i<=lim;++i){
        B[i]=inv(fact[lim-i]);
        if ((lim-i)&1) B[i]=MOD-B[i];
    }
    int len=1,l=0;
    for (;len<((lim+1)<<1);len<<=1,++l);
    for (re int i=0;i<len;++i) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    NTT(A,len,1),NTT(B,len,1);
    for (re int i=0;i<len;++i) A[i]=1ll*A[i]*B[i]%MOD;
    NTT(A,len,-1);
    int ans=0;
    for (re int i=0;i<=lim;++i)
        ans=(ans+1ll*A[lim+i]*inv(fact[i])%MOD*w[i]%MOD)%MOD;
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 06 月 27 日 02 : 35 PM

发表评论