【学习笔记】CF708E Student‘s Camp

一语成戳了。真的是二维容斥。

记$P(i)=\left(\genfrac{}{}{0ex}{}{K}{i}\right)p^i(1-p{)}^{K-i}$，$P(l,r)$表示这一行剩下区间$[l,r]$的概率，显然$P(l,r)=P_{l-1}{P}_{m-r}$。

设而不求。设$h_{i,l,r}$表示到第$i$行还剩区间$[l,r]$的概率，$f_{i,r}$表示右端点为$r$的$h$的和，$g_{i,l}$表示左端点为$l$的$h$的和，$F_{i,r}$表示右端点小于等于$r$的$h$的和，$G_{i,l}$表示左端点大于等于$l$的$h$的和。

有转移式：$h_{i,l,r}=P(l,r){\sum }_{[l^{\prime },r^{\prime }]\cap [l,r]\ne \varnothing }{h}_{i-1,l^{\prime },r^{\prime }}$。容斥有讲究，这里考虑用总方案数减去$r^{\prime }<l$和$l^{\prime }>r$的情况，也就是$h_{i,l,r}=P(l,r)(F_{i-1,m}-F_{i-1,l-1}-G_{i-1,r+1})$。

其实接下来思路非常简单。只要把$f,g$都求出来，$F,G$都可以通过做前缀和求到。把$h$带进去不就变成只包含$f,g,F,G$的式子了吗。

复杂度$O(nm)$。

#include
#define ll long long
#define fi first
#define se second
using namespace std;
const int mod=1e9+7;
const int N=2005;
const int M=1e5+5;
int n,m,K;
ll P[N],fac[M],inv[M],A,B,f[N],g[N],F[N],G[N],sumP[N];
ll tranf[N],trang[N];
ll fpow(ll x,ll y=mod-2){
	ll z(1);
	for(;y;y>>=1){
		if(y&1)z=z*x%mod;
		x=x*x%mod;
	}return z;
}
void init(int n){
	fac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
	inv[n]=fpow(fac[n]);for(int i=n;i>=1;i--)inv[i-1]=inv[i]*i%mod;
}
ll binom(ll x,ll y){
	if(x<0||y<0||x<y)return 0;
	return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
void add(ll &x,ll y){x=(x+y)%mod;}
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>A>>B>>K;init(K);
	for(int i=0;i<=min(K,m);i++){
		P[i]=binom(K,i)*fpow(A,i)%mod*fpow(B-A,K-i)%mod*fpow(fpow(B),K)%mod;
	}
	sumP[0]=P[0];for(int i=1;i<=m;i++)sumP[i]=(sumP[i-1]+P[i])%mod;
	for(int i=1;i<=m;i++){
		for(int j=i;j<=m;j++){
			ll tmp=P[i-1]*P[m-j]%mod;
			add(f[j],tmp),add(g[i],tmp);
		}
	}
	for(int i=1;i<=m;i++)F[i]=(F[i-1]+f[i])%mod;
	for(int i=m;i>=1;i--)G[i]=(G[i+1]+g[i])%mod;
	for(int i=1;i<n;i++){
		for(int j=1;j<=m;j++){
			tranf[j]=(tranf[j-1]+P[j-1]*F[j-1])%mod;
		}
		for(int j=m;j>=1;j--){
			trang[j]=(trang[j+1]+P[m-j]*G[j+1])%mod;
		}
		ll tmp=F[m];
		for(int j=1;j<=m;j++){
			add(f[j]=0,sumP[j-1]*F[m]%mod*P[m-j]);
			add(f[j],-P[m-j]*tranf[j]);
			add(f[j],-P[m-j]*G[j+1]%mod*sumP[j-1]);
		}
		for(int j=m;j>=1;j--){
			add(g[j]=0,sumP[m-j]*F[m]%mod*P[j-1]);
			add(g[j],-P[j-1]*trang[j]);
			add(g[j],-P[j-1]*F[j-1]%mod*sumP[m-j]);
		}
		for(int j=1;j<=m;j++)F[j]=(F[j-1]+f[j])%mod;
		for(int j=m;j>=1;j--)G[j]=(G[j+1]+g[j])%mod;
	}
	cout<<(F[m]+mod)%mod;
}
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