自动搬运

查看原文

来自洛谷，原作者为

	command_block 众水皆昂首，饮月唯我一。

搬运于2025-08-24 22:00:43，当前版本为作者最后更新于2019-04-30 11:07:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

广告 : 炫酷反演魔术 & 多项式计数杂谈

二项式反演经典题。

设 $G[k]$ 表示有恰好 $k$ 种颜色出现了 $S$ 次的方案数。

我们需要求出 $W[1...n]$ 即可解决问题,这个 $n=\min(M,N/S)$

一个naive的想法是 : 钦定$k$种颜色,每种强行染上$S$次。

剩下的颜色放任自流,随便怎么染。

得到 $\dbinom{m}{k}*\dfrac{n!}{(S!)^k(n-S*k)!}*(n-S*k)^{m-k}$

组合意义 : "选 $k$ 种颜色$\times$可重排列$\times$放任自流"

那么这个东西肯定不是 $G[k]$ ,也并不是所谓 "至少 $k$ 种颜色出现了 $S$ 次的方案数"

事实上,这是会重复计数的,但是仍然以优美的方式蕴含了 $G[k]$。

我们设其为 $F[k]$。

• 我们先从特殊情况来分析

  假设有三种颜色 $a,b,c$

  按照上式的组合思想:

  1. 钦定 $a,b$ ,然后随便染,不幸的是 $c$ 也出现了 $S$ 次

  2. 钦定 $a,c$ ,然后随便染,不幸的是 $b$ 也出现了 $S$ 次

  很明显会把 $a,b,c$ 都恰好出现 $S$ 次的方案算重复,所以严格来讲这个式子并不能称之为方案数……

  究竟算重多少次呢?

  考虑有 $4$ 种颜色 $a,b,c,d$

  那么 $G[4]$ 与 $F[3]$ 间的贡献关系是什么呢?

  $G[4]$ 在 $F[3]$ 钦定 $\{a,b,c\}$,$\{a,b,d\}$,$\{a,c,d\}$,$\{b,c,d\}$ 的时候各被算重一次,那么算重了 $\dbinom{4}{3}$ 次。

类比至一般情况,得到 $F[k]=\sum\limits_{i=k}^{n}\dbinom{i}{k}*G[i]$

已知 $F$ 要求 $G$ ,不就是二项式反演的经典操作嘛!

反演可得 $G[k]=\sum\limits_{i=k}^n(-1)^{i-k}\dbinom{i}{k}F[i]$

到现在复杂度还是 $O(n^2)$ 的,我们考虑把组合数拆开看看能否卷积:

$G[k]=\sum\limits_{i=k}^n(-1)^{i-k}\dfrac{i!}{k!(i-k)!}F[i]$

$G[k]*k!=\sum\limits_{i=k}^n\dfrac{(-1)^{i-k}}{(i-k)!}i!F[i]$

这可以明显地看到差卷积形式了。

设 $A[i]=i!*F[i],\ B[i]=\dfrac{(-1)^i}{i!}$

则有$G[k]=\frac{1}{k!}\sum\limits_{i=k}^nA[i]B[i-k]$

NTT计算差卷积即可,复杂度$O(N+n\log n)$。

Code:

#include<algorithm>
#include<cstdio>
#define ll long long
using namespace std;
const int _G=3,mod=1004535809,Maxn=135000,MaxNum=10000500;
ll powM(ll a,int t=mod-2){
  ll ans=1;
  while(t){
    if(t&1)ans=ans*a%mod;
    a=a*a%mod;t>>=1;
  }return ans;
}
const int invG=powM(_G);
int tr[Maxn<<1];
void NTT(int *g,bool op,int n)
{
  #define ull unsigned long long
  static ull f[Maxn<<1],w[Maxn]={1};
  for (int i=0;i<n;i++)f[i]=g[tr[i]];
  for(int l=1;l<n;l<<=1){
    ull tG=powM(op?_G:invG,(mod-1)/(l+l));
    for (int i=1;i<l;i++)w[i]=w[i-1]*tG%mod;
    for(int k=0;k<n;k+=l+l)
      for(int p=0;p<l;p++){
        int tt=w[p]*f[k|l|p]%mod;
        f[k|l|p]=f[k|p]+mod-tt;
        f[k|p]+=tt;
      }      
    if (l==(1<<10))
      for (int i=0;i<n;i++)f[i]%=mod;
  }if (!op){
    ull invn=powM(n);
    for(int i=0;i<n;++i)
      g[i]=f[i]%mod*invn%mod;
  }else for(int i=0;i<n;++i)g[i]=f[i]%mod;
}
int n,m,S,lim,limNum;
ll w[Maxn],fac[MaxNum],ifac[MaxNum];
void Init()
{
  limNum=max(n,m);fac[0]=1;
  for (int i=1;i<=limNum;i++)
    fac[i]=fac[i-1]*i%mod;
  ifac[limNum]=powM(fac[limNum]);
  for (int i=limNum;i;i--)
    ifac[i-1]=ifac[i]*i%mod;
}
ll C(int n,int m)
{return fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
inline ll clacF(int x){
  return 
    C(m,x)*fac[n]%mod*
    powM(ifac[S],x)%mod*ifac[n-S*x]%mod*
		powM(m-x,n-S*x)%mod;
}
int A[Maxn<<1],B[Maxn<<1];
int main()
{
  scanf("%d%d%d",&n,&m,&S);
  lim=min(m,n/S);Init();
  for (int i=0;i<=lim;i++){
    A[i]=clacF(i)*fac[i]%mod;
    B[i]=(i&1) ? mod-ifac[i] : ifac[i];
  }reverse(A,A+lim+1);
  for(n=1;n<lim+lim+2;n<<=1);
  for (int i=0;i<n;i++)
    tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
  NTT(A,1,n);NTT(B,1,n);
  for (int i=0;i<n;i++)A[i]=1ll*A[i]*B[i]%mod;
  NTT(A,0,n);reverse(A,A+lim+1);
  ll ans=0;
  for (int i=0,w;i<=lim;i++){
    scanf("%d",&w);
    ans=(ans+A[i]*ifac[i]%mod*w)%mod;
  }printf("%lld",ans);
  return 0;
}