[HAOI2018]染色 - A-Failure的博客

题目

题目描述

为了报答小 C 的苹果, 小 G 打算送给热爱美术的小 C 一块画布, 这块画布可以抽象为一个长度为 $N$ 的序列, 每个位置都可以被染成 $M$ 种颜色中的某一种.

然而小 C 只关心序列的 $N$ 个位置中出现次数恰好为 $S$ 的颜色种数, 如果恰好出现了 $S$ 次的颜色有 $K$ 种, 则小C会产生 $W_k$ 的愉悦度.

小 C 希望知道对于所有可能的染色方案, 他能获得的愉悦度的和对 $1004535809$ 取模的结果是多少.

输入格式

第一行三个整数 $N,M,S$.

接下来一行 $M+1$ 个整数, 第 $i$ 个数表示 $W_{i-1}$.

输出格式

输出一行一个整数表示答案．

样例

样例输入

8 8 3
3999 8477 9694 8454 3308 8961 3018 2255 4910

样例输出

524070430

数据范围与提示

对于 $10\%$ 的数据，$N \le 10, M \le 5$；

对于 $30\%$ 的数据，$N \le 100, M \le 100$；

对于另外 $10\%$ 的数据，$M \le 1000$；

对于另外 $10\%$ 的数据，$\forall 1 \le i \le M, W_i = 0$；

对于 $100\%$ 的数据，$N \le 10^7, M \le 10^5, S \le 150, 0 \le W_i < 1004535809$。

题解

发现一个序列可以出现的颜色最多$M’=min(\left\lfloor\frac{N}{S}\right\rfloor,M)$种，如果要直接求正好$K$种有多少合法序列，似乎非常难求

考虑容斥，$f_k$表示序列中至少有$k$种出现恰好$S$次的颜色的合法情况数

首先从$M$中选择$k$种是$C_{M}^{k}$种情况，从$N$中选择$kS$个位置是$C_{N}^{kS}$种情况

但是由于颜色块是没有编号的，所以应该是$\prod_{i=0}^{k-1}C_{N-iS}^{S}$种情况，化简得$\frac{N!}{(S!)^k(n-kS)!}$

然后剩下的$M-k$种颜色在剩下的$N-kS$个位置随便填，一共$(M-k)^{N-kS}$种情况

所以$f_k=C_{M}^{i}\times \frac{N!}{(S!)^k(n-kS)!}\times (M-k)^{N-kS}$，这个玩意可以$O(M’logA)$处理出来

设$g_k$为序列中正好有$k$种出现恰好$S$次的颜色的合法情况数

容斥有$g_k=\sum_{i=k}^{M’}(-1)^{i-k}C_{i}^{k}f_i=\sum_{i=k}^{M’}(-1)^{i-k}\frac{i!}{k!(i-k)!}f_i$

现在问题就是这个式子怎么快速计算

发现如果把$i$和$i-k$看成下标的话非常像一个卷积……

于是把$f$翻转，$G_i=\frac{(-1)^i}{i!},F_i=i!\times f_i,T_i=i!\times g_i$

有$T_i=\sum_{j=0}^{i}G_{i-j}F_j$

直接$NTT$搞就好了

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=4e5+5,N=1e7+5,mod=1004535809;
int n,m,S,M,lim=1,L,ans;
int w[MAX],fac[N],a[MAX],b[MAX],R[MAX];
int read()
{
	int x(0);
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar());
	for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
	return x;
}
int Pow(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;
}
void NTT(int *A,int tt=1)
{
	for(int i=0;i<lim;++i)
	  if(i<R[i]) swap(A[i],A[R[i]]);
	for(int i=1,w1;i<lim;i<<=1)
	  {
	  	w1=Pow(3,(mod-1)/(i<<1));
	  	for(int l=i<<1,j=0,w;j<lim;j+=l)
	  	  {
	  	  	w=1;
	  	  	for(int k=0,x,y;k<i;++k,w=1ll*w*w1%mod)
	  	  	  {
	  	  	  	x=A[j+k],y=1ll*w*A[i+j+k]%mod,A[j+k]=x+y,A[i+j+k]=x-y+mod;
	  	  	  	if(A[j+k]>=mod) A[j+k]-=mod;
	  	  	  	if(A[i+j+k]>=mod) A[i+j+k]-=mod;
			  }
		  }
	  }
	if(tt==-1)
	{
		reverse(A+1,A+lim);
		for(int i=0,G=Pow(lim,mod-2);i<lim;++i)
		  A[i]=1ll*A[i]*G%mod;
	}
}
int C(int x) {return 1ll*fac[m]*Pow(1ll*fac[x]*fac[m-x]%mod,mod-2)%mod;}
int main()
{
	n=read(),m=read(),S=read(),M=min(m,n/S),fac[0]=1;
	while(lim<=(M<<1)) lim<<=1,++L;
	for(int i=0;i<=lim;++i)
	  R[i]=(R[i>>1]>>1)|((i&1)<<L-1);
	for(int i=0;i<=m;++i)
	  w[i]=read();
	for(int i=1,_N=max(max(n,m),S);i<=_N;++i)
	  fac[i]=1ll*fac[i-1]*i%mod;
	for(int i=0;i<=M;++i)
	  a[i]=(((i&1)?-1:1)*Pow(fac[i],mod-2)+mod)%mod;
	for(int i=0,tt=1;i<=M;++i)
	  b[M-i]=1ll*C(i)*fac[n]%mod*Pow(1ll*tt*fac[n-i*S]%mod,mod-2)%mod*Pow(m-i,n-i*S)%mod*fac[i]%mod,tt=1ll*tt*fac[S]%mod;
	NTT(a),NTT(b);
	for(int i=0;i<=lim;++i)
	  a[i]=(1ll*a[i]*b[i]%mod+mod)%mod;
	NTT(a,-1);
	for(int i=0;i<=M;++i)
	  {
	  	ans+=1ll*a[M-i]*Pow(fac[i],mod-2)%mod*w[i]%mod;
	  	if(ans>=mod) ans-=mod;
	  }
	return printf("%d",ans),0;
}

题目