JZOJ 6474 小 B 的夏令营

据说原题是个集训队作业题。
这题主要侧重于 DP 的优化。

首先考虑设 f(t,l,r) 表示考虑前 t 层，前 t 层都连通且第 t 层剩下的方块为 (l,r] 内的。
（之所以左开右闭是因为式子比较整齐）

那么有个显然的转移 f(t,l,r)=pl⋅pm−r∑(l,r]⋂(i,j]≠∅f(t−1,i,j)

其中 pi 表示同一行上 k 次台风刚好摧毁 i 个连续方块的概率。
有 pi=(ki)pi(1−p)k−i

然而这时会发现状态空间开不下而且转移更吃力……
考虑再设 fL(t,l)=∑l<rf(t,l,r)fR(t,r)=∑l<rf(t,l,r)sL(t,l)=∑l≤afL(t,a)sR(t,r)=∑a≤rfR(t,a)

那么 f(t,l,r) 就应该是 pl⋅pm−r[sR(t−1,m)−sR(t−1,l)−sL(t−1,r)]。
当然这时就应该舍弃一开始的 f 了，而是以 fL,fR,sL,sR 为状态。

两边的处理是类似的，这里以 fR 为例： fR(t,r)=∑l<rpl⋅pm−r[sR(t−1,m)−sR(t−1,l)−sL(t−1,r)]=pm−r⋅sR(t−1,m)∑l<rpl−pm−r∑l<rpl⋅sR(t−1,l)−pm−r⋅sL(t−1,r)∑l<rpl

然后就会发现，维护 pi 的前缀和是不够的，还要维护 pi⋅sR(t−1,i) 的前缀和。
这样就可以做到 O(nm) 了。

代码：

#include <cstdio>
#include <algorithm>
const int N = 1500;
const int K = 1e5;
const int mod = 1e9 + 7;
inline int fpow(int a,int b)
{
    int ret = 1;
    for(;b;b >>= 1)
        (b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
    return ret;
}
int n,m,k;
int pw[2][K + 5];
int p[K + 5],sum[K + 5],fac[K + 5],ifac[K + 5];
int f[2][N + 5][N + 5],s[4][N + 5][N + 5];
inline int C(int n,int m)
{
    return n >= m ? (long long)fac[n] * ifac[m] % mod * ifac[n - m] % mod : 0;
}
int main()
{
    freopen("camp.in","r",stdin),freopen("camp.out","w",stdout);
    int a,b;
    scanf("%d%d%d%d%d",&n,&m,&a,&b,&k),
    fac[0] = pw[0][0] = pw[1][0] = 1,
    pw[1][1] = (1 - (pw[0][1] = (long long)a * fpow(b,mod - 2) % mod) + mod) % mod;
    for(register int i = 1;i <= k;++i)
        fac[i] = (long long)fac[i - 1] * i % mod;
    ifac[k] = fpow(fac[k],mod - 2);
    for(register int i = k;i;--i)
        ifac[i - 1] = (long long)ifac[i] * i % mod;
    for(register int i = 2;i <= k;++i)
        pw[0][i] = (long long)pw[0][i - 1] * pw[0][1] % mod,
        pw[1][i] = (long long)pw[1][i - 1] * pw[1][1] % mod;
    for(register int i = 0;i <= k;++i)
        p[i] = (long long)C(k,i) * pw[0][i] % mod * pw[1][k - i] % mod;
    for(register int i = 1;i <= m;++i)
        sum[i] = (sum[i - 1] + p[i - 1]) % mod;
    f[0][0][0] = s[0][0][0] = f[1][0][m] = s[1][0][m] = 1;
    for(register int i = m - 1;~i;--i)
        s[2][0][i] = (s[2][0][i + 1] + (long long)p[m - i] * s[0][0][i] % mod) % mod;
    for(register int i = 1;i <= m;++i)
        s[3][0][i] = (s[3][0][i - 1] + (long long)p[i] * s[1][0][i] % mod) % mod;
    for(register int t = 1;t <= n;++t)
    {
        for(register int i = 0;i < m;++i)
            f[0][t][i] = p[i] * (
                (long long)s[1][t - 1][m] * sum[m - i] % mod -
                (long long)s[1][t - 1][i] * sum[m - i] % mod + mod -
                s[2][t - 1][i + 1] + mod
            ) % mod;
        for(register int i = 1;i <= m;++i)
            f[1][t][i] = p[m - i] * (
                (long long)s[1][t - 1][m] * sum[i] % mod -
                s[3][t - 1][i - 1] + mod -
                (long long)s[0][t - 1][i] * sum[i] % mod + mod
            ) % mod;
        for(register int i = m - 1;~i;--i)
            s[0][t][i] = (s[0][t][i + 1] + f[0][t][i]) % mod;
        for(register int i = 1;i <= m;++i)
            s[1][t][i] = (s[1][t][i - 1] + f[1][t][i]) % mod;
        for(register int i = m - 1;~i;--i)
            s[2][t][i] = (s[2][t][i + 1] + (long long)p[m - i] * s[0][t][i] % mod) % mod;
        for(register int i = 1;i <= m;++i)
            s[3][t][i] = (s[3][t][i - 1] + (long long)p[i] * s[1][t][i] % mod) % mod;
    }
    printf("%lld\n",s[1][n][m]);
}