正題

題目鏈接:https://www.luogu.com.cn/problem/CF708E

---

題目大意

有$n?m$的矩形網格，然后每次每行最左邊和最右邊的格子各有$p=\frac{c}{d}$的概率會消失，進行$k$次。

求最后所有格子依舊四聯通的概率，在$\%(10^9+7)$的情況下進行

$1\le n,m\le 1500,1\le k\le 10^5$

---

解題思路

$n,m$很小，感覺上不是一個暴力計數的題目。

可以考慮一個比較慢的方法先，先考慮一個方向腐蝕了$i$次的概率設為$E_i$那么顯然地有
$$E_i=\left(\genfrac{}{}{0ex}{}{k}{i}\right)p^i(1?p{)}^{k?i}$$
然后設$f_{i,l,r}$表示到第$i$層時，剩下了$l～r$且上面的層都聯通的概率。
那么一個簡單的$dp$有
$$f_{i,l,r}=E_{l?1}{E}_{m?r}\times \sum _{[l^{\prime },r^{\prime }]\cap [l,r]=?}{f}_{i?1,l^{\prime },r^{\prime }}$$
先把這個方程優化到$O(n{m}^2)$，設$L_{i,j}={\sum }_{l\le r<j}{f}_{i,l,r},R_{i,j}={\sum }_{r>l\ge j}{f}_{i,l,r},S_i=\sum f_{i,l,r}$
那么有
$$f_{i,l,r}=E_{l?1}{E}_{m?r}(S_{i?1}?L_{i?1,l}?R_{i?1,r})$$
嗯然后我們要把$f$的狀態數轉到$O(nm)$的，其實不難發現的一點是這些東西都具有對稱性，也就是$f_{i,l,r}=f_{i,n?r+1,n?l+1}$。所有我們可以設$F_{i,j}={\sum }_{k=1}^j{f}_{i,k,j}$
那么有$L_{i,j}={\sum }_{k=1}^j{F}_{i,k}$因為對稱性又有$R_{i,j}=L_{i,n?j+1}$所以此時我們已經可以表示出所有的$F,L,R$了。考慮這個$F$如何轉移
$$F_{x,y}=\sum _{i=1}^y{f}_{x,i,y}=\sum _{i=1}^y{E}_{i?1}{E}_{m?y}(S_{x?1}?L_{x?1,i}?R_{x?1,y})$$
$$?F_{x,y}=E_{m?y}((S_{x?1}?R_{x?1,y})\sum _{i\le y}{E}_{i?1}?\sum _{i\le y}{E}_{i?1}{L}_{x?1,i})$$

這樣就是$O(nm)$的了，可以通過本題

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=1510,P=1e9+7,K=1e5+10; ll n,m,p,q,k,fac[K],inv[K],E[N],S[N]; ll f[N][N],s[N][N],t[N][N]; ll power(ll x,ll b){ll ans=1;while(b){if(b&1)ans=ans*x%P;x=x*x%P;b>>=1;}return ans; } ll C(ll n,ll m) {return fac[n]*inv[m]%P*inv[n-m]%P;} signed main() {scanf("%lld%lld",&n,&m);scanf("%lld%lld",&p,&q);p=p*power(q,P-2)%P;scanf("%lld",&k);q=P+1-p;inv[1]=1;for(ll i=2;i<K;i++)inv[i]=P-inv[P%i]*(P/i)%P;fac[0]=inv[0]=1;for(ll i=1;i<K;i++)fac[i]=fac[i-1]*i%P,inv[i]=inv[i-1]*inv[i]%P;for(ll i=0;i<=min(k,m);i++)E[i]=C(k,i)*power(p,i)%P*power(q,k-i)%P;S[0]=E[0];for(ll i=1;i<=m;i++)S[i]=(S[i-1]+E[i])%P;s[0][m]=f[0][m]=1;for(ll i=1;i<=n;i++){for(ll j=1;j<=m;j++){f[i][j]=E[m-j]*((s[i-1][m]-s[i-1][m-j])*S[j-1]%P-t[i-1][j])%P;s[i][j]=(s[i][j-1]+f[i][j])%P;t[i][j]=(t[i][j-1]+s[i][j-1]*E[j-1]%P)%P;}}printf("%lld\n",(s[n][m]+P)%P);return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的CF708E-Student‘s Camp【数学期望,dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。