JZOJ 6474 小 B 的夏令营

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

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

那么有个显然的转移

$$f(t,l,r)=p_l\cdot p_{m-r}\sum _{(l,r]\bigcap (i,j]\ne \varnothing }f(t-1,i,j)$$

其中 $p_i$ 表示同一行上 $k$ 次台风刚好摧毁 $i$ 个连续方块的概率。
有 $p_i=(\genfrac{}{}{0ex}{}{k}{i})p^i(1-p{)}^{k-i}$

然而这时会发现状态空间开不下而且转移更吃力……
考虑再设

$$\begin{gathered} f_L(t,l)=\sum _{l<r}f(t,l,r) \\ {f}_R(t,r)=\sum _{l<r}f(t,l,r) \\ {s}_L(t,l)=\sum _{l\le a}{f}_L(t,a) \\ {s}_R(t,r)=\sum _{a\le r}{f}_R(t,a) \end{gathered}$$

那么 $f(t,l,r)$ 就应该是 $p_l\cdot p_{m-r}[s_R(t-1,m)-s_R(t-1,l)-s_L(t-1,r)]$。
当然这时就应该舍弃一开始的 $f$ 了，而是以 $f_L,f_R,s_L,s_R$ 为状态。

两边的处理是类似的，这里以 $f_R$ 为例：

$$\begin{array}{rl}{f}_R(t,r)& =\sum _{l<r}{p}_l\cdot p_{m-r}[s_R(t-1,m)-s_R(t-1,l)-s_L(t-1,r)]\\ & =p_{m-r}\cdot s_R(t-1,m)\sum _{l<r}{p}_l\\ & -p_{m-r}\sum _{l<r}{p}_l\cdot s_R(t-1,l)\\ & -p_{m-r}\cdot s_L(t-1,r)\sum _{l<r}{p}_l\end{array}$$

然后就会发现，维护 $p_i$ 的前缀和是不够的，还要维护 $p_i\cdot s_R(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]);
}