P4491 [HAOI2018] 染色

传送门:洛谷

解题思路:

写本题需要知道一个前置知识:

假设恰好选$k$个条件的方案数为$f(k)$;先钦定选$k$个条件,其他条件无所谓的方案数为$g(k)$
那么存在这样的一个关系:$g(k)={\sum }_{i=k}^n{C}_i^{k}f(i)$
上述式子的含义是可以枚举实际上选了几个,然后再这$i$个中选择$k$个作为钦定的计算方案数.因为钦定这种方式是存在重复方案的
然后使用二项式反演可以实现钦定和恰好之间的转化.
经过二项式反演可以得到:$f(k)={\sum }_{i=k}^n{C}_i^k\ast (-1{)}^{i-k}\ast g(i)$.

对于本题来说,我们的$g(i)$其实很容易写出.设$g(i)$为恰好出现$i$个的出现次数为$s$的颜色的方案数.不难写出$$g(i)=C_m^i\frac{A_n^{s\ast i}}{(s\ast i)!}\ast (m-i{)}^{n-s\ast i}$$
然后我们反演一下就得到了:$$f(k)=\sum _{i=k}^n{C}_i^k(-1{)}^{i-k}g(i)$$
稍微化解一下就能得到:
$$f(k)\ast k!=\sum _{i=k}^{n}g(i)\ast i!\ast \frac{(-1{)}^{i-k}}{(i-k)!}$$
然后我们设$G(i)=g(i)\ast i!,H(i)=\frac{(-1{)}^{i-k}}{(i-k)!}$就能得到$$F(k)=\sum _{i=k}^{n}G(i)\ast H(i-k)$$
我们使用经典套路将$G$数组$reverse$一下,就得到了$$F(K)=\sum _{i=k}^{n}G(n-i)\ast H(i-k)$$
PS:需要注意的是此时翻转的n可以不为n,不熟悉的人可能会搞不清楚
然后这是一道很显然的卷积式子.此时我们使用$NTT$卷一下即可.此时我们的的$f(k)$就是卷积完之后第$n-k$项的系数.

---

下面是具体的代码部分:

#include 
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
inline void print(__int128 x){
	if(x<0) {putchar('-');x=-x;}
	if(x>9) print(x/10);
	putchar(x%10+'0');
}
#define maxn 10001000
#define int long long
const int mod=1004535809;
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int qpow(int a,int b) {
	int ans=1;
	while(b) {
		if(b&1) ans=ans*a%mod;
		b>>=1;
		a=a*a%mod;
	}
	return ans;
}
int rev[maxn];
void NTT(int *a,int n,int inv) {
	for(int i=0;i<=n;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);
	for(int len=1;len<=(n>>1);len<<=1) {
		int gn=qpow(inv==1?3:qpow(3,mod-2),(mod-1)/(len<<1));
		for(int i=0;i<=n;i+=(len<<1)) {
			int g0=1;
			for(int j=0;j<=len-1;j++) {
				int x=a[i+j],y=a[i+j+len]*g0%mod;
				a[i+j]=(x+y)%mod;a[i+j+len]=((x-y)%mod+mod)%mod;
				g0=g0*gn%mod;
			}
		}
	}
}
int fac[maxn],in_fac[maxn];
void init(int limit) {
	fac[0]=1;
	for(int i=1;i<=limit;i++) {
		fac[i]=fac[i-1]*i%mod;
	}
	in_fac[limit]=qpow(fac[limit],mod-2);
	for(int i=limit-1;i>=0;i--) {
		in_fac[i]=in_fac[i+1]*(i+1)%mod;
	}
}
int C(int a,int b) {
	return fac[a]*in_fac[b]%mod*in_fac[a-b]%mod;
}
int A(int a,int b) {
	return fac[a]*in_fac[a-b]%mod;
}
int w[maxn];int g[maxn];int G[maxn],H[maxn];int F[maxn];
signed main() {
	int n=read();int m=read();int s=read();
	init(max(n,m));
	for(int i=0;i<=m;i++) {
		w[i]=read();
	}
	int k=min(m,n/s);
	for(int i=0;i<=k;i++) {
		g[i]=C(m,i)*A(n,s*i)%mod*qpow(in_fac[s],i)%mod*qpow(m-i,n-s*i)%mod;
	}
	for(int i=0;i<=k;i++) {
		G[i]=g[i]*fac[i]%mod;
		H[i]=((i&1?-1:1)*in_fac[i]%mod+mod)%mod;
	}
	reverse(G,G+k+1);
	int limit=1,len=0;
	while(limit<=k+k) limit<<=1,len++;
	for(int i=0;i<=limit;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(len-1));
	NTT(G,limit,1);NTT(H,limit,1);
	for(int i=0;i<=limit;i++) F[i]=G[i]*H[i]%mod;
	NTT(F,limit,-1);
	int inv=qpow(limit,mod-2);
	for(int i=0;i<=limit;i++) {
		F[i]=F[i]*inv%mod;
	}
	int ans=0;
	for(int i=0;i<=k;i++) {
		ans=(ans+F[k-i]*in_fac[i]%mod*w[i]%mod)%mod;
	}
	cout<<ans<<endl;
	return 0;
}
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99