「HAOI 2018」染色

川长思鸟来 2021-11-23 04:54 245阅读 0赞

### 题目链接 ###

[戳我][Link 1]

### \\(Solution\\) ###

观察题目发现恰好出现了\\(s\\)次的颜色有\\(k\\)种,不太好弄.

所以我们设\\(a\[i\]\\)表示为恰好出现了\\(s\\)次的颜色有至少\\(i\\)种的方案数,然后容斥一下

我们看一看\\(a\[i\]\\)怎么求？

这很明显可以一眼看出来

\\\[a\[i\]=C\_m^i\*C\_n^\{is\}\*(m-i)^\{n-is\}\*\\frac\{(is)!\}\{ \{s!\}^i\}\\\]

在\\(m\\)个颜色中选则\\(i\\)个,在\\(n\\)个位置选择\\(i\*s\\)个,将这\\(i\*s\\)个数全排列(有重复元素)，剩下的位置随便选

算完这个以后可以开始容斥求答案,设答案数组为\\(F\[i\]\\)

\\\[F\[i\]=\\sum\_\{j=i\}^\{limit\}(-1)^\{j-i\}\*C\_j^i\*a\[j\]\\\]

再将组合数拆开:

\\\[F\[i\]=\\sum\_\{j=i\}^\{limit\}(-1)^\{j-i\}\*\\frac\{j!\}\{(j-i)!\*i!\}\*a\[j\]\\\]  
\\\[F\[i\]\*i!=\\sum\_\{j=i\}^\{limit\}\\frac\{(-1)^\{j-i\}\}\{(j-i)!\}\*a\[j\]\*j!\\\]  
令\\(f\[i\]=\\frac\{(-1)^\{i\}\}\{(i)!\},g\[i\]=a\[j\]\*j!\\)  
所以原式为:

\\\[F\[i\]\*i!=\\sum\_\{j=i\}^\{limit\}f\[j-i\]\*g\[i\]\\\]

然后将\\(f\\)数组翻转,原式为:

\\\[F\[i\]\*i!=\\sum\_\{j=i\}^\{limit\}f\[n-j+i\]\*g\[i\]\\\]  
然后发现\\(j\\)从\\(1\\)开始对答案没有影响,这又是个卷积,又因为有\\(\\%\\)数,所以直接\\(ntt\\)求即可

### \\(Code\\) ###

#include<iostream> #include<cstdlib> #include<cstdio> #define int long long #define rg register #define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout); using namespace std; const int mod=1004535809; const int N=10000001+10; int read(){ int x=0,f=1; char c=getchar(); while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar(); while(c>='0'&&c<='9') x=x*10+c-48,c=getchar(); return f*x; } int f[N],g[N],r[N],limit=1,w[N],inv[N],jc[N]; int ksm(int a,int b){ int ans=1; while(b){ if(b&1) ans=ans*a%mod; a=a*a%mod,b>>=1; } return ans; } void fft(int *a,int opt){ for(int i=0;i<=limit;i++) if(i<r[i]) swap(a[i],a[r[i]]); for(int i=1;i<limit;i<<=1){ int w=ksm(3,(mod-1)/(i*2)); if(opt==-1) w=ksm(w,mod-2); for(int j=0;j<limit;j+=i<<1){ int l=1; for(int k=j;k<j+i;k++){ int p=l*a[k+i]%mod; a[k+i]=(a[k]-p+mod)%mod; a[k]=(a[k]+p)%mod; l=l*w%mod; } } } } int C(int n,int m){ return jc[n]*inv[m]%mod*inv[n-m]%mod; } main(){ int n=read(),m=read(),s=read(),l=0,M=min(m,n/s),ans=0; for(int i=0;i<=m;i++) w[i]=read(); while(limit<=M<<1) limit<<=1,l++; jc[0]=1; for(int i=1;i<=max(n,m);i++) jc[i]=jc[i-1]*i%mod; inv[max(n,m)]=ksm(jc[max(n,m)],mod-2); for(int i=max(n,m)-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod; for(int i=0;i<=M;i++) g[i]=C(m,i)*C(n,i*s)%mod*jc[s*i]%mod*ksm(inv[s],i)%mod*ksm(m-i,n-i*s)%mod; for(int i=0;i<=M;i++){ g[i]=g[i]*jc[i]%mod; f[M-i]=(ksm(-1,i)*inv[i]+mod)%mod; } for(int i=0;i<limit;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1)); fft(f,1),fft(g,1); for(int i=0;i<limit;i++) f[i]=f[i]*g[i]%mod; fft(f,-1); for(int i=0;i<=M;i++) ans=(ans+f[i+M]*ksm(limit,mod-2)%mod*inv[i]%mod*w[i]%mod)%mod; printf("%lld",ans); }

转载于:https://www.cnblogs.com/hbxblog/p/11197899.html

[Link 1]: https://www.luogu.org/problemnew/show/P4491