P4491

[HAOI2018]染色

考虑钦定法。

令 $f_k$ 表示钦定 $k$ 种颜色恰好染上 $s$ 次的情况数。

根据组合意义，我们有：

$$f_k=\binom{m}{k}\dfrac{n!}{(n-sk)!(s!)^k}(m-k)^{n-sk}$$

预处理出阶乘及其逆元之后我们计算这一部分的复杂度就是 $O(n+m\log m)$ 的。

我们定义 $g_k$ 表示恰好 $k$ 种颜色恰好出现了 $s$ 次的情况数，于是我们就有：

$$f_k=\sum_{i=k}^{m}\binom{i}{k}g_i$$

接下来我们进行二项式反演：

$$g_k=\sum_{i=k}^{m}(-1)^{i-k}\binom{i}{k}f_i$$

考虑使用卷积优化：

$$g_k=\dfrac{1}{k!}\sum_{i=k}^{m}\dfrac{(-1)^{i-k}}{(i-k)!}i!f_i$$

我们设 $a_i=(-1)^{i}/i!$，$b_i=i!f_i$，于是我们就有：

$$g_k=\dfrac{1}{k!}\sum_{i=k}^{m}a_{i-k}b_i$$

然后我们通过翻转序列将这里的差卷积转化为一般的和卷积，先将下标调整为从 0 开始：

$$g_k=\dfrac{1}{k!}\sum_{i=0}^{m-k}a_{i}b_{i+k}$$

设 $b ^ {\prime} _ i= b _ {m-i}$，则 $ b _ i = b ^ { \prime} _ {m-i} $，就有：

$$g_k=\dfrac{1}{k!}\sum_{i=0}^{m-k}a_ib^{\prime}_{(m-k)-i}$$

这显然就是一个和卷积的形式了。

于是我们正常 NTT 之后再翻转序列，每项乘上 $k!$ 的逆元之后就能得到 $g_k$ 的具体值了，最后乘上我们的权值即可得到答案。

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

代码：

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;

const ll N=4e5,M=1e7,mo=1004535809,G=3;

inline ll Pow(ll b,ll p) {
  ll r=1;while(p) {if(p&1) r=r*b%mo;b=b*b%mo;p>>=1;}return r;
}

const ll invG=Pow(G,mo-2);

ll n,m,s,ans;
ll a[N+5],b[N+5],f[N+5],g[N+5],rev[N+5],w[N+5];
ll fac[M+5],invfac[M+5];

inline void NTT_Init(ll n) {
  for(ll i=0;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)?(n>>1):0);
}

inline void NTT(ll *f,ll n,bool op) {
  NTT_Init(n);ll invn=Pow(n,mo-2);
  for(ll i=0;i<n;i++) if(i<rev[i]) swap(f[i],f[rev[i]]);
  for(ll p=2;p<=n;p<<=1) {
    ll len=p>>1,tG=Pow(op?invG:G,(mo-1)/p);
    for(ll k=0;k<n;k+=p) {
      for(ll l=k,buf=1;l<k+len;l++,buf=buf*tG%mo) {
        ll t=buf*f[l+len]%mo;
        f[l+len]=f[l]-t;if(f[l+len]<0) f[l+len]+=mo;
        f[l]=f[l]+t;if(f[l]>=mo) f[l]-=mo;
      }
    }
  }
  if(op) {
    for(ll i=0;i<n;i++) f[i]=f[i]*invn%mo;
  }
}

inline void Times(ll *f,ll *a,ll *b,ll lena,ll lenb,ll &lenf) {
  ll tmplen=lena+lenb;lenf=1;for(;lenf<=tmplen;lenf<<=1);
  NTT(a,lenf,0);NTT(b,lenf,0);
  for(ll i=0;i<lenf;i++) f[i]=a[i]*b[i]%mo;
  NTT(a,lenf,1);NTT(b,lenf,1);NTT(f,lenf,1);
}

inline void Init() {
  fac[0]=1;for(ll i=1;i<=M;i++) fac[i]=fac[i-1]*i%mo;
  invfac[0]=1;invfac[M]=Pow(fac[M],mo-2);
  for(ll i=M-1;i>=1;i--) invfac[i]=invfac[i+1]*(i+1)%mo;
}

inline void Reverse(ll *f,ll n) {for(ll i=0;i<n-i;i++) swap(f[i],f[n-i]);}

int main() {

  n=read();m=read();s=read();
  for(ll i=0;i<=m;i++) {w[i]=read();}
  Init();

  for(ll i=0;i<=m;i++) {
    if(s*i>n) break;
    f[i]=fac[m]*invfac[i]%mo;
    f[i]=f[i]*invfac[m-i]%mo;
    f[i]=f[i]*fac[n]%mo;
    f[i]=f[i]*invfac[n-s*i]%mo;
    f[i]=f[i]*Pow(invfac[s],i)%mo;
    f[i]=f[i]*Pow(m-i,n-s*i)%mo;
  }

  for(ll i=0;i<=m;i++) {
    a[i]=(i&1)?(-invfac[i]+mo)%mo:invfac[i];
    b[i]=fac[i]*f[i]%mo;
  }

  Reverse(b,m);ll len=0;Times(g,a,b,m,m,len);

  for(ll i=0;i<=m;i++) {
    ans=(ans+(invfac[i]*g[m-i]%mo)*w[i]%mo)%mo;
  }

  write(ans);

  return 0;
}