CF708E Student's Camp 题解
chen_03
·
·
题解
看了看题解区，竟然没有一篇题解是我的思路，所以我来分享一下。
我们把行编号为 0\sim n+1，对于一个连通的状态，必然存在一条从第 0 行到第 n+1 行的只往左、右、下三个方向走的路径，途中只经过未被摧毁的方块。为了让每个连通的状态对应唯一一条路径，我们强制这条路径：
- 能往下走时，直接往下走；
- 否则，往左或往右走到最近的能往下走的方块，然后往下走。
考虑 DP，设 f_{i,j} 表示从第 i-1 行进入第 i 行时在第 j 列，且在第 i-1 行有往右走时，第 1\sim i-1 行的摧毁状态对应的概率；g_{i,j} 的定义是将上面的 “往右走” 改成 “往左走”；h_{i,j} 的定义是将 “往右走” 改成 “没有左右移动”。
转移可以前缀和优化，时间复杂度 $\mathcal{O}(nm)$。
根据这种 “路径” 的思想，应该有更简单的 DP 方法，请读者自行思考。具体地，我们可以调整 “强制每个连通的状态对应唯一一条路径” 的方式。我只是遵循刚想到这种思路时得到的 DP 方法罢了。
```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int p=1000000007;
int n,m,x,y,q,K,a[1505],s[1505],*f,*F,*g,*G,*h,*H,sum,ans;
int f1[1505],f2[1505],g1[1505],g2[1505],h1[1505],h2[1505];
inline int qpow(int a,int b){
int res=1;
while(b){
if(b&1)res=(ll)res*a%p;
b>>=1,a=(ll)a*a%p;
}
return res;
}
int main(){
scanf("%d%d%d%d%d",&n,&m,&x,&y,&K);
q=(ll)x*qpow(y,p-2)%p;
for(int i=0,C=1;i<=m;++i){
if(i<=K)a[i]=(ll)C*qpow(q,i)%p*qpow(p+1-q,K-i)%p;
else a[i]=0;
s[i]=((i?s[i-1]:0)+a[i])%p;
C=(ll)C*(K-i)%p*qpow(i+1,p-2)%p;
}
f=f1,F=f2,g=g1,G=g2,h=h1,H=h2;
for(int j=1;j<=m;++j)f[j]=1;
for(int i=2;i<=n;++i){
sum=0;
for(int j=1;j<=m;++j){
F[j]=(ll)sum*s[m-j]%p;
sum=(sum+(ll)f[j]*a[j-1]+(ll)h[j]*s[j-1])%p;
H[j]=((ll)f[j]*a[j-1]%p*s[m-j]+(ll)g[j]*a[m-j]%p*s[j-1]+(ll)h[j]*s[j-1]%p*s[m-j])%p;
}
sum=0;
for(int j=m;j>=1;--j){
G[j]=(ll)sum*s[j-1]%p;
sum=(sum+(ll)g[j]*a[m-j]+(ll)h[j]*s[m-j])%p;
}
swap(f,F),swap(g,G),swap(h,H);
}
for(int j=1;j<=m;++j)
ans=(ans+(ll)f[j]*a[j-1]%p*s[m-j]+(ll)g[j]*a[m-j]%p*s[j-1]+(ll)h[j]*s[j-1]%p*s[m-j])%p;
printf("%d\n",ans);
return 0;
}
```