【HAOI2018】染色

  • 本文为博主原创，未经许可不得转载

枚举每次的$w_k$结合容斥可以得到（其中$N=min(\left \lfloor \frac{n}{S} \right \rfloor,m)$）：

$Ans=\sum_{i=0}^{N}w[i]C_{m}^{i}C_{n}^{is}\frac{(iS)!}{(S!)^i}\sum_{j=0}^{N-i}(-1)^j C_{m-i}^{j}C_{n-iS}^{jS}\frac{(jS)!}{(S!)^j}(m-i-j)^{n-iS-jS}$

$=\sum_{i=0}^{N}w[i]C_{m}^{i}C_{n}^{is}\frac{(iS)!}{(S!)^i}\sum_{j=i}^{N}(-1)^{j-i}C_{m-i}^{j-i}C_{n-iS}^{jS-iS}\frac{(jS-iS)!}{(S!)^{j-i}}(m-j)^{n-jS}$

$=\sum_{i=0}^{N}w[i]\sum_{j=i}{N}(-1)^{j-i}\frac{m!n!(iS)!}{i!(m-i)!(iS)!(n-iS)!}\times \frac{(m-i)!(n-iS)!(jS-iS)!}{(j-i)!(m-j)!(jS-iS)!(n-jS)!}\times \frac{1}{(S!)^(j-i)(S!)^i}(m-j)^{n-jS}$

$=\sum_{i=0}^{N}\frac{w[i]}{i!}\sum_{j=i}^{N}(-1)^{j-i}\frac{m!n!}{(j-i)!(m-j)!(n-jS)!}\times\frac{1}{(S!)^j}(m-j)^{n-jS}$

$=\sum_{j=0}^{N}\frac{m!n!(m-j)^{n-jS}}{(m-j)!(n-jS)!(S!)^j}\sum_{i=0}^{j}\frac{w[i]}{i!}\times \frac{(-1)^{j-i}}{(j-i)!}$

注意到右边的和式是一个卷积，可以NTT预处理出来

辣鸡bzoj卡常，还是洛谷吼啊

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 300010
#define MAXM 10000010
#define cadd(a,b) a=add(a,b)
#define csub(a,b) a=sub(a,b)
#define cmul(a,b) a=mul(a,b)
using namespace std;
const int mod=1004535809;
int n,m,S,N,ans,G(3),w[MAXN],W[MAXN],R[MAXN],A[MAXN],B[MAXN],fac[MAXM],inv[MAXM],wn[2][20];
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(ch>'9'||ch<'0')  {if(ch=='-')  f=-1;  ch=getchar();}
	while(ch>='0'&&ch<='9')  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
inline int add(int a,int b){return (a+=b)>=mod?a-mod:a;}
inline int sub(int a,int b){return (a-=b)<0?a+mod:a;}
inline int mul(int a,int b){return 1LL*a*b%mod;}
inline int power(int a,int b){
	int ret(1);
	while(b){
		if(b&1)  cmul(ret,a);
		cmul(a,a);  b>>=1;
	}return ret;
}
void NTT(int *a,int H,int f=0){
	int L=(1<<H);
	for(int i=0;i<L;++i)  if(i<(R[i]=(R[i>>1]>>1)|((i&1)<<(H-1))))  swap(a[i],a[R[i]]);
	for(int e=1;e<=H;++e){
		int len=(1<<e),l=(len>>1);
		for(int i=1;i<l;++i)  w[i]=mul(w[i-1],wn[f][e]);
		for(int st=0;st<L;st+=len) for(int k=0;k<l;++k){
			int x=a[st+k],y=mul(w[k],a[st+k+l]);
			a[st+k]=add(x,y);  a[st+k+l]=sub(x,y);
		}
	}
	if(f)  for(int i=0;i<L;++i)  cmul(a[i],power(L,mod-2));
}
void Init(){
	wn[0][18]=power(G,(mod-1)/(1<<18));
	wn[1][18]=power(wn[0][18],mod-2);
	for(int i=17;i>=0;--i){
		wn[0][i]=mul(wn[0][i+1],wn[0][i+1]);
		wn[1][i]=mul(wn[1][i+1],wn[1][i+1]);
	}w[0]=1;  fac[0]=1;
	for(int i=1;i<=MAXM-10;++i)  fac[i]=mul(fac[i-1],i); 
	inv[MAXM-10]=power(fac[MAXM-10],mod-2);
	for(int i=MAXM-11;i>=0;--i)  inv[i]=mul(inv[i+1],i+1);
	for(int i=0;i<=N;++i)  A[i]=mul(W[i],inv[i]);
	for(int i=0;i<=N;++i)  B[i]=(i&1?sub(0,inv[i]):inv[i]);
}
void solve(){
	int L=1,H=0;  while(L<(N<<1)+1)  L<<=1,++H;
	NTT(A,H);  NTT(B,H);
	for(int i=0;i<L;++i)  A[i]=mul(A[i],B[i]);
	NTT(A,H,1);
	for(int i=0;i<=N;++i)
		cadd(ans,mul(mul(fac[m],mul(fac[n],mul(inv[m-i],mul(inv[n-i*S],mul(power(inv[S],i),power(m-i,n-i*S)))))),A[i]));
	printf("%d\n",ans);
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read();  m=read();  S=read();  N=min((n/S),m);
	for(int i=0;i<=m;++i)  W[i]=read();  
	Init();
	solve();
	return 0;
}

本文标题:【HAOI2018】染色

文章作者:chty

发布时间:2018年05月07日 - 21时04分

最后更新:2018年05月10日 - 21时13分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,