CodeForces 708E

动态规划，dp优化

题意

给你一个 n+2n+2，宽 mm 的矩形，其中第 11 行和第 n+1n+1 行是坚不可摧的。有 tt 天，每天对于每行有 pp 的概率消掉最左块，同样的也有 pp 的概率消掉最右块。求 tt 天后所有格子构成一个联通块的概率。

1≤n,m≤1500,0≤t≤1000001\le n,m\le 1500,0\le t\le 100000

题解

能消掉的只有 nn 行 mm 列，对于一行，在 tt 天后留下 [l,r][l,r] 这段的概率为

(tl−1)pl−1(1−p)t−l+1×(tm−r)pm−r(1−p)t−m+r\binom{t}{l-1}p^{l-1} (1-p)^{t-l+1} \times \binom{t}{m-r} p^{m-r}(1-p)^{t-m+r}

记 Gl=(tl−1)pl−1(1−p)t−l+1,Hr=(tm−r)pm−r(1−p)t−m+rG_l=\binom{t}{l-1}p^{l-1} (1-p)^{t-l+1},H_r=\binom{t}{m-r} p^{m-r}(1-p)^{t-m+r} 。

考虑逐行DP，设 Fi,l,rF_{i,l,r} 表示到第 ii 行且当前行剩下 [l,r][l,r] 这段的概率。考虑转移，只要 i,i+1i,i+1 有交即可。有交不好算，相当于算总情况减去无交的。记一下前缀和后缀，令：

prel=∑k=1l−1∑j=1kFi,j,kpre_l=\sum_{k=1}^{l-1}\sum_{j=1}^{k}F_{i,j,k}

sufr=∑j=r+1m∑k=jmFi,j,ksuf_r=\sum_{j=r+1}^m\sum_{k=j}^m F_{i,j,k}

Fi+1,l,r←(prem+1−prel−sufr)GlHrF_{i+1,l,r} \gets (pre_{m+1}-pre_l-suf_r) G_lH_r

这样是 O(nm2)\mathcal{O}(nm^2) 的，考虑优化。发现 FF 的状态就 O(nm2)O(nm^2) 了，而 pre,sufpre,suf 是 O(nm)O(nm) 的。把下面的式子带上去：

prel′=∑k=1l−1∑j=1k(prem+1−prej−sufk)GjHk=∑k=1l−1∑j=1k(prem+1GjHk−prejGjHk−sufkGjHk)=∑k=1l−1(Hk∑j=1k(prem+1−prej)Gj−Hksufk∑j=1kGj)\begin{aligned} pre_l'&=\sum_{k=1}^{l-1}\sum_{j=1}^k (pre_{m+1}-pre_j-suf_k)G_jH_k\\ &=\sum_{k=1}^{l-1}\sum_{j=1}^k \big(pre_{m+1}G_jH_k-pre_jG_jH_k-suf_kG_jH_k\big)\\ &=\sum_{k=1}^{l-1}\left(H_k\sum_{j=1}^k (pre_{m+1}-pre_j)G_j-H_ksuf_k\sum_{j=1}^kG_j\right)\\ \end{aligned}

求 (prem+1−prej)Gj,Gj(pre_{m+1}-pre_j)G_j,G_j 前缀和，上式可以 O(m)O(m) 推出 prel(l∈[1,m+1])pre_l(l\in[1,m+1]) 。同理也可得：

sufr′=∑j=r+1m∑k=jm(prem+1−prej−sufk)GjHk=∑j=r+1m∑k=jm(prem+1GjHk−prejGjHk−sufkGjHk)=∑j=r+1m(Gj∑k=jm(prem+1−sufk)Hk−Gjprej∑k=jmHk)\begin{aligned} suf_r'&=\sum_{j=r+1}^m\sum_{k=j}^m (pre_{m+1}-pre_j-suf_k)G_jH_k\\ &=\sum_{j=r+1}^m\sum_{k=j}^m (pre_{m+1}G_jH_k-pre_jG_jH_k-suf_kG_jH_k)\\ &=\sum_{j=r+1}^m\left(G_j\sum_{k=j}^m(pre_{m+1}-suf_k)H_k-G_jpre_j\sum_{k=j}^m H_k\right)\\ \end{aligned}

答案就是 prem+1pre_{m+1}，复杂度 O(nm)O(nm)。

CODE

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
#include <bits/stdc++.h>
// #include "../debuger.h"
template<typename _Tp>
inline void read(_Tp &x) {
    x=0;bool fg=0;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') fg^=1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(_Tp)(ch^48),ch=getchar();
    if(fg) x=-x;
}
template<typename _Tp,typename... Args>void read(_Tp &t,Args &... args){read(t);read(args...);}
using namespace std;
typedef long long ll;
const int N = 1510;
const int M = 100010;
const int mod = 1e9+7;
int n,m,p,a,b,t;
ll G[N],H[N],inv[M],ifac[M],fac[M];
ll sG[N],sH[N];
ll pre[2][N],suf[2][N],spre[N],ssuf[N];
ll fpow(ll a,ll b) {
    ll r=1;
    for(a%=mod;b;b>>=1,a=a*a%mod) if(b&1) r=r*a%mod;
    return r;
}
ll C(int n,int m) {
    if(n<m) return 0;
    return fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
void init() {
    p=a*fpow(b,mod-2)%mod;
    // seeln(p);
    inv[0]=inv[1]=fac[0]=fac[1]=ifac[0]=ifac[1]=1;
    for(int i=2;i<=t;++i) fac[i]=fac[i-1]*i%mod;
    for(int i=2;i<=t;++i) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    for(int i=2;i<=t;++i) ifac[i]=ifac[i-1]*inv[i]%mod;
    // put("!!\n");
    for(int i=1;i<=m;++i) {
        if(t>=i-1) G[i]=C(t,i-1)*fpow(p,i-1)%mod*fpow(mod+1-p,t-i+1)%mod;
        if(t>=m-i) H[i]=C(t,m-i)*fpow(p,m-i)%mod*fpow(mod+1-p,t-m+i)%mod;
    }
    // outarr(G,1,m);
    // outarr(H,1,m);
    for(int i=1;i<=m;++i) sG[i]=(sG[i-1]+G[i])%mod;
    for(int i=m;i>=1;--i) sH[i]=(sH[i+1]+H[i])%mod;
}
int main() {
    read(n,m,a,b,t);
    init();
    bool V=0;
    pre[0][m+1]=1; suf[0][0]=1;
    for(int i=1;i<=n;++i) {
        for(int k=1;k<=m+1;++k) spre[k]=(spre[k-1]+(pre[V][m+1]-pre[V][k]+mod)%mod*G[k])%mod;
        for(int k=m;k>=0;--k) ssuf[k]=(ssuf[k+1]+(pre[V][m+1]-suf[V][k]+mod)%mod*H[k])%mod;

        for(int l=1;l<=m+1;++l) {
            pre[V^1][l]=(pre[V^1][l-1]+H[l-1]*spre[l-1]%mod-H[l-1]*suf[V][l-1]%mod*sG[l-1]%mod+mod)%mod;
        }
        for(int r=m;r>=0;--r) {
            suf[V^1][r]=(suf[V^1][r+1]+G[r+1]*ssuf[r+1]%mod-G[r+1]*pre[V][r+1]%mod*sH[r+1]%mod+mod)%mod;
        }
        V^=1;
    }
    printf("%lld\n",pre[V][m+1]);
    return 0;
}