据说原题是个集训队作业题。
这题主要侧重于 DP 的优化。
首先考虑设 \(f(t,l,r)\) 表示考虑前 \(t\) 层，前 \(t\) 层都连通且第 \(t\) 层剩下的方块为 \((l,r]\) 内的。
（之所以左开右闭是因为式子比较整齐）
那么有个显然的转移 \[ f(t,l,r) = p_l \cdot p_{m-r} \sum\limits_{(l,r]\bigcap(i,j]\ne \varnothing} f(t-1,i,j) \]
其中 \(p_i\) 表示同一行上 \(k\) 次台风刚好摧毁 \(i\) 个连续方块的概率。
有 \(p_i = \binom ki p^i (1-p)^{k-i}\)
然而这时会发现状态空间开不下而且转移更吃力……
考虑再设 \[
f_L(t,l) = \sum\limits_{l < r} f(t,l,r) \\
f_R(t,r) = \sum\limits_{l < r} f(t,l,r) \\
s_L(t,l) = \sum\limits_{l \le a} f_L(t,a) \\
s_R(t,r) = \sum\limits_{a \le r} f_R(t,a)
\]
那么 \(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{aligned} f_R(t,r) &= \sum\limits_{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\limits_{l < r} p_l\\ &- p_{m-r} \sum\limits_{l < r} p_l \cdot s_R(t-1,l) \\ &- p_{m-r} \cdot s_L(t-1,r)\sum\limits_{l < r} p_l \end{aligned} \]
然后就会发现，维护 \(p_i\) 的前缀和是不够的，还要维护 \(p_i \cdot s_R(t-1,i)\) 的前缀和。
这样就可以做到 \(O(nm)\) 了。
代码： 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
66
67
68
69
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]);
}