題解 P4491 【[HAOI2018]染色】

題解 - P 4491 \mathrm{P4491} P4491

題目意思

題目傳送門

S o l \mathrm{Sol} Sol

• 二項式反演題

我們按套路設

f i f_{i} fi​ 表示欽定有 i i i 個顔色數為 S S S 的方案數。 g i g_i gi​ 表示恰好有 i i i 個顔色數為 S S S。

那麼 a n s = ∑ i = 0 m g i × w i ans=\sum_{i=0}^{m} g_i\times w_i ans=∑i=0m​gi​×wi​

g i = ∑ j = i min ⁡ ( m , n s ) f j × C j i × ( − 1 ) j − i g_i=\sum_{j=i}^{\min(m,\frac{n}{s})} f_j\times C_{j}^{i}\times (-1)^{j-i} gi​=∑j=imin(m,sn​)​fj​×Cji​×(−1)j−i

關鍵怎麼求這個 f j f_j fj​

f j = C m j × C n j × s × ( j × s ) ! ( s ! ) j × ( m − j ) n − j × s f_j=C_{m}^{j}\times C_n^{j\times s}\times \frac{(j\times s)!}{(s!)^j}\times (m-j)^{n-j\times s} fj​=Cmj​×Cnj×s​×(s!)j(j×s)!​×(m−j)n−j×s

中間那一項可以這樣子了解：你先要在 n n n 個位置中至少選出 j × s j\times s j×s 個位置的方案數為 C n j × s C_n^{j\times s} Cnj×s​ ，對于具體地填入可以了解為先按照全排列的方式填再去掉相同顔色的那些多餘情況，即 ( j × s ) ! ( s ! ) j \frac{(j\times s)!}{(s!)^j} (s!)j(j×s)!​。其他都很好了解。

時間複雜度： O ( m 2 ) O(m^2) O(m2) 由于跑不滿可以過 m ≤ 5 × 1 0 4 m\leq 5\times 10^4 m≤5×104 的點

然後我們考慮優化是這個式子：

原式： g i × i ! = ∑ j = i n ( − 1 ) j − i ( i − j ) ! j ! f j g_i\times i!=\sum_{j=i}^{n}\frac{(-1)^{j-i}}{(i-j)!}j!f_j gi​×i!=∑j=in​(i−j)!(−1)j−i​j!fj​

這就是道很經典的題目了,可以看看 Z J O I 2014 ZJOI2014 ZJOI2014 力那道題目

我們設 F i = i ! f i F_i=i!f_i Fi​=i!fi​， G i = ( − 1 ) i i ! G_i=\frac{(-1)^i}{i!} Gi​=i!(−1)i​

那麼原式可以寫成： g i = 1 i ! ∑ j = i n F j × G j − i g_i=\frac{1}{i!}\sum_{j=i}^{n} F_j\times G_{j-i} gi​=i!1​∑j=in​Fj​×Gj−i​

直接 N T T NTT NTT 一下就好了。

C o d e \mathrm{Code} Code

#include <bits/stdc++.h>
#define For(i,a,b) for ( int i=(a);i<=(b);i++ )
#define Dow(i,b,a) for ( int i=(b);i>=(a);i-- )
#define GO(i,x) for ( int i=head[x];i;i=e[i].nex )
#define mem(x,s) memset(x,s,sizeof(x))
#define cpy(x,s) memcpy(x,s,sizeof(x))
#define YES return puts("YES"),0
#define NO return puts("NO"),0
#define GG return puts("-1"),0
#define pb push_back
#define int long long
using namespace std;

inline int read()
{
	int sum=0,ff=1; char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-') ff=-1;
		ch=getchar();
	}
	while(isdigit(ch))
		sum=sum*10+(ch^48),ch=getchar();
	return sum*ff;
}

const int mod=1e9+7;
const int mo=1004535809;
const int N=1e7+5;
const int G=3ll;

int n,m,fac[N],inv[N],F[N],f[N],g[N];
int w[N],ans,l,r[N],mx,INV,lim,s;

inline int ksm(int a,int b)
{
	int ans=1;
	while(b)
	{
		if(b&1ll) ans=ans*a%mo;
		a=a*a%mo;
		b>>=1ll;
	}
	return ans%mo;
}

const int InvG=ksm(G,mo-2);
 
inline int C(int n,int m)
{
	return fac[n]*inv[m]%mo*inv[n-m]%mo;
}

inline void NTT(int *f,int op)
{
	For(i,0,lim-1) if(i<r[i]) swap(f[i],f[r[i]]);
	for ( int mid=1;mid<lim;mid<<=1ll)
	{
		int tmp=ksm(G,(mo-1)/(mid*2ll));
		if(op) tmp=ksm(tmp,mo-2);
		for ( int i=0;i<lim;i+=mid*2ll )
		{
			int w=1ll;
			for ( int j=0;j<mid;j++,w=w*tmp%mo )
			{
				int x=f[i+j];
				int y=w*f[i+j+mid]%mo;
				f[i+j]=(x+y)%mo;
				f[i+j+mid]=(x-y+mo)%mo;
			}
		}
	}
	if(op) For(i,0,lim-1) f[i]=f[i]*INV%mo;
}

signed main()
{
	n=read(),m=read(),s=read();
	For(i,0,m) w[i]=read();
	int M=max(n,m);
	fac[0]=1;
	For(i,1,M) fac[i]=fac[i-1]*i%mo;
	inv[M]=ksm(fac[M],mo-2)%mo;
	Dow(i,M-1,0) inv[i]=inv[i+1]*(i+1)%mo;
	mx=min(m,n/s);
	Dow(i,mx,0) F[i]=C(m,i)*fac[n]%mo*inv[n-i*s]%mo*ksm(ksm(fac[s],i),mo-2)%mo*ksm(m-i,n-i*s)%mo;
	For(i,0,mx) f[i]=F[i]*fac[i]%mo;
	For(i,0,mx) g[i]=((i&1ll)?mo-inv[i]:inv[i]);
	reverse(f,f+mx+1);
	lim=1ll;
	while(lim<=(mx+1)<<1ll) lim<<=1ll,l++;
	INV=ksm(lim,mo-2)%mo;
	For(i,0,lim-1) r[i]=r[i>>1ll]>>1ll|((i&1ll)<<(l-1));
	NTT(f,0),NTT(g,0);
	For(i,0,lim-1) f[i]=f[i]*g[i]%mo;
	NTT(f,1);
	int ans=0;
	For(i,0,mx) ans=(ans+1ll*f[mx-i]*w[i]%mo*inv[i]%mo)%mo;
	printf("%lld\n",ans);
	return 0;
}