【概率dp】Student's Camp

动态规划DP, 概率

传送门：Codeforces708E

思路：

  • 先预处理$pr_i$表示若干天以后某边停在第i块砖上的概率，要用大力组合技巧；
  • 然后用$f_{i,l,r}$表示前i层，第i层为$[l,r]$时不倒的概率，则$f_{i,l,r}=f{i-1,ll,rr}$其中$[l,r],[ll,rr]$有交集，时间复杂度$O(n^5)$；
  • 实际上只要拿到第i层的总概率减去到第i层后倒了的概率（即$[l,r],[ll,rr]$没交集的概率）；
  • 然后再大力前缀和一发即可。

注意：

  • 预处理$pr_i$时不要算错。

代码如下：

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
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 2000
#define M 120000
#define LL long long
const int mod=1000000007;
int n,m,fz,fm,p,P,pr[M],g[N][N],h[N][N],pow1[M],pow2[M],fac[M],ifac[M],prepr[M],pre[M];
void exgcd(int a,int b,int &x,int &y){
	if (b==0){x=1; y=0; return;}
	exgcd(b,a%b,y,x); y=((y-(LL)a/b*x)%mod+mod)%mod;
}
int inv(int x){
	int ret,tmp; exgcd(x,mod,ret,tmp);
	return ret;
}
int main(){
	scanf("%d%d%d%d%d",&n,&m,&fz,&fm,&p);
	P=((LL)fz*inv(fm)%mod+mod)%mod;
	/**pr[1]=1;
	for (int i=1;i<=p;i++)
		for (int j=m;j>=1;j--)
			pr[j]=(((LL)pr[j]*(1-P)+pr[j-1]*P)%mod+mod)%mod;*/
	pow1[0]=pow2[0]=fac[0]=1; int mx=max(m,p+1);
	for (int i=1;i<=mx;i++){
		pow1[i]=(LL)pow1[i-1]*P%mod;
		pow2[i]=((LL)pow2[i-1]*(1-P)%mod+mod)%mod;
		fac[i]=(LL)fac[i-1]*i%mod;
	}
	ifac[mx]=inv(fac[mx]);
	for (int i=mx-1;i>=0;i--) ifac[i]=(LL)ifac[i+1]*(i+1)%mod;
	for (int i=1;i<=mx;i++){
		pr[i]=(LL)fac[p]*ifac[i-1]%mod*ifac[p-i+1]%mod*pow1[i-1]%mod*pow2[p-i+1]%mod;
		prepr[i]=(prepr[i-1]+pr[i])%mod;
	}
	g[0][m]=h[0][m]=1;
	for (int i=1;i<=m;i++) pre[i]=(pre[i-1]+(LL)pr[i]*h[0][i-1])%mod;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++) g[i][j]=((((LL)h[i-1][m]-h[i-1][m-j])*prepr[j]-pre[j])%mod*pr[m-j+1]%mod+mod)%mod;
		for (int j=1;j<=m;j++) h[i][j]=(h[i][j-1]+g[i][j])%mod;
		for (int j=1;j<=m;j++) pre[j]=(pre[j-1]+(LL)pr[j]*h[i][j-1])%mod;
	}
	printf("%d\n",h[n][m]);
	
	return 0;
}