题解 CF708E 【Student's Camp】

2020-05-09 11:52:09


不一定更好的阅读体验


显然营地不连通只能是上下分开,即存在相邻两行剩下的砖块区间没有交。

考虑 DP。设 $f_{i,j,k}$ 表示前 $i$ 行,第 $i$ 行剩下 $[j,k]$ ,且前 $i$ 行连通的概率。容易得到转移 $$ f_{i,j,k}=p_{j,k}\sum_{[j,k]\cap[l,r]\neq\varnothing}f_{i-1,l,r} $$ 这里的 $p_{l,r}$ 表示某一行剩下 $[l,r]$ 的概率,显然等于左边少了 $l-1$ 块、右边少了 $m-r$ 块的概率。

设某一边少了 $i$ 块的概率为 $d_i$ ,则有 $$ \begin{aligned} d_i&={k\choose i}P^i(1-P)^{k-i}\\ p_{l,r}&=d_{l-1}d_{m-r} \end{aligned} $$ 直接转移显然过不去。设 $$ \begin{aligned} fr_{i,r}&=\sum_{l\leq r}f_{i,l,r}\\ sr_{i,j}&=\sum_{l\leq r\leq j}f_{i,l,r}=\sum_{r\leq j}fr_{i,r}\\ fl_{i,l}&=\sum_{l\leq r}f_{i,l,r}\\ sl_{i,j}&=\sum_{j\leq l\leq r}f_{i,l,r}=\sum_{l\geq j}fl_{i,l} \end{aligned} $$ 可以发现 $fr_{i,r}=fl_{i,m-r+1},sr_{i,r}=sl_{i,m-r+1}$ ,且最后答案就为 $sr_{n,m}$ 。

那么我们就可以通过容斥,用 $sr$ 来表示 $f$ 。 $$ \begin{aligned} f_{i,j,k}&=p_{j,k}\sum_{[j,k]\cap[l,r]\neq\varnothing}f_{i-1,l,r}\\ &=p_{j,k}(sr_{i-1,m}-sr_{i-1,j-1}-sl_{i-1,k+1})\\ &=p_{j,k}(sr_{i-1,m}-sr_{i-1,j-1}-sr_{i-1,m-k}) \end{aligned} $$ 而 $sr$ 又可以通过 $fr$ 求出,所以只要考虑如何求 $fr$ 。 $$ \begin{aligned} fr_{i,r}&=\sum_{l\leq r}f_{i,l,r}\\ &=\sum_{l\leq r}p_{l,r}(sr_{i-1,m}-sr_{i-1,l-1}-sr_{i-1,m-r})\\ &=(sr_{i-1,m}-sr_{i-1,m-r})\sum_{l\leq r}p_{l,r}-\sum_{l\leq r}p_{l,r}sr_{i-1,l-1}\\ &=d_{m-r}\left[(sr_{i-1,m}-sr_{i-1,m-r})\sum_{l\leq r}d_{l-1}-\sum_{l\leq r}d_{l-1}sr_{i-1,l-1}\right] \end{aligned} $$ 于是只要求出 $d_{l-1}$ 和 $d_{l-1}sr_{i-1,l-1}$ 的前缀和即可。第一个可以提前预处理出,第二个可以在 DP 时维护。

边界为 $f_{0,1,m}=1$ 即 $fr_{0,m}=sr_{0,m}=1$ 。

总时间复杂度为 $\mathcal{O}(nm)$ 。

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1500+10,K=100000+10;
const int mod=1e9+7;
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

int n,m,a,b,k,p;
int fac[K],ifac[K],d[K],sd[N],fr[N][N],sr[N][N],ss[N][N];

int C(int n,int m) {
    return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}

int main() {
    n=read(),m=read(),a=read(),b=read(),k=read(); p=1ll*a*qpow(b,mod-2)%mod;
    fac[0]=1;
    for (int i=1;i<=k;++i) fac[i]=1ll*fac[i-1]*i%mod;
    ifac[k]=qpow(fac[k],mod-2);
    for (int i=k;i;--i) ifac[i-1]=1ll*ifac[i]*i%mod;
    for (int i=0;i<=k;++i) d[i]=1ll*C(k,i)*qpow(p,i)%mod*qpow(1-p+mod,k-i)%mod;
    for (int i=1;i<=m;++i) sd[i]=(sd[i-1]+d[i-1])%mod;
    fr[0][m]=sr[0][m]=1;
    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j) {
            fr[i][j]=(1ll*(sr[i-1][m]-sr[i-1][m-j]+mod)*sd[j]-ss[i-1][j]+mod)%mod*d[m-j]%mod;
            sr[i][j]=(sr[i][j-1]+fr[i][j])%mod;
            ss[i][j]=(ss[i][j-1]+1ll*d[j-1]*sr[i][j-1])%mod;
        }
    printf("%d\n",sr[n][m]);
    return 0;
}