题解 P3824 【[NOI2017]泳池】
CYJian
2020-08-04 08:59:52
~~好像我的转移方法和大家都不同，那就顺便来发个题解吧...~~
直接算最大面积为 $k$ 比较难处理，则考虑差分：先求出最大面积 $\le k$ 的概率，再减去最大面积 $\le k-1$ 的概率，就得到了最大面积 $=k$ 的概率了。
然后考虑设计状态 $f_{h, w}$ 为：
当前保证有一个高为 $h$，宽为 $w$ 的安全区域，且高为 $h+1$ 以上的位置任意且合法面积不超过 $k$ 的概率是多少。
注意到我们可以枚举高度为 $h+1$ 的那一行，左侧第一个危险的点出现的位置，则有转移：
$$ f_{h, w} = p^w \times f_{h+1,w}+\sum_{i=1}^{w} f_{h+1,i-1} \times f_{h,w-i} \times p^{i-1}\times (1-p) $$
然后最后的答案就是 $f_{0, n}$ 了。
乍一看，状态数 $O(n^2)$ 转移数 $O(n)$，复杂度就成了 $O(n^3)$。但是事实上针对最大面积不超过 $k$ 这个限制条件，我们真正有用的状态数是只有 $O(k \log k)$ 个的。则判断 $h \times w \le k$ 之后，实际复杂度是 $O(k^2 \log k)$ 的。
这个 `dp` 我是使用递归实现的，写起来很方便。当然也可以使用递推，但是需要注意循环的顺序（$h$ 从大到小枚举，$w$ 从小到大枚举，这个不能乱顺序）
然后我们就解决了 $n, k \leq 10^3$ 的部分，到这里就可以拿到 $70$ 分了。
然后我们考虑一下 $n$ 很大的时候，$f_{0, n}$ 的转移。注意到对于所有 $x \ge k$，$f_{0, x}$ 都会用到 $f_{1,0}, f_{1,1},\ldots,f_{1,k}$ 进行转移。
注意到，如果我们先算出 $f_{1,0}, f_{1,1},\ldots,f_{1,k}$，那么就可以算出 $f_{0, x}$ 了。
考虑设 $G_i=f_{1,i}\times p^i \times q$，$F_n=f{0,n}$，则我们最后想知道的是 $F_n$，且 $F$ 可以通过 $G$ 互相转移：
$$ F_n = \sum_{i=1}^{k+1} G_{i-1} \times F_{n-i} (n > k)$$
使用矩阵乘法加速转移，结合上面的暴力 `dp` 就可以获得 $90$ 分的好成绩。
然后，如果你还会[常系数齐次线性递推](https://www.luogu.com.cn/problem/P4723)的话，你就会发现写出这个递推式之后就可以套上板子了。如果不会的话，建议在有一定数理基础的情况下再去学习。
由于此题中 $k \leq 10^3$，所以多项式乘法和取模可以暴力实现。
部分代码：
```cpp
typedef long long ll;
const int mod = 998244353;
const ll MOD = 8ll * mod * mod;
inline int Mod(int x) { return x >= mod ? x - mod : x; }
inline void ADD(ll &x, ll y) { x += y, x -= x >= MOD ? MOD : 0; }
inline int fsp(int x, int k = mod - 2) {
int s = 1;
while(k) {
if(k & 1) s = 1LL * s * x % mod;
x = 1LL * x * x % mod, k >>= 1;
} return s;
}
int F[3010], lf;
int Q[3010], lq;
int S[3010], ls;
int G[3010], lg;
ll tmp[3010];
int A[3010];
inline void PolyMul(int a[], int b[], int c[], int &n, int m) {
for(int i = 0; i <= n; i++)
for(int j = 0; j <= m; j++)
ADD(tmp[i + j], 1LL * b[i] * c[j]);
n += m;
for(int i = 0; i <= n; i++) a[i] = tmp[i] % mod, tmp[i] = 0;
}
inline void PolyMod(int a[], int &n) {
for(int i = n; i >= lq; i--) {
if(!a[i]) continue;
int mul = mod - a[i];
for(int j = 0; j <= lq; j++)
a[i - j] = (a[i - j] + 1LL * mul * Q[lq - j]) % mod;
} chkmin(n, lq - 1);
while(n && !a[n]) --n;
}
inline int calc(int n, int k) {
memset(Q, 0, sizeof(Q));
memset(S, 0, sizeof(S));
memset(G, 0, sizeof(G));
Q[k] = 1, lq = k;
for(int i = 0; i < k; i++) Q[k - i - 1] = mod - A[i];
S[0] = 1, ls = 0;
G[1] = 1, lg = 1;
while(n) {
if(n & 1) PolyMul(S, S, G, ls, lg), PolyMod(S, ls);
PolyMul(G, G, G, lg, lg), PolyMod(G, lg), n >>= 1;
}
int res = 0;
for(int i = 0; i < k; i++)
res = (res + 1LL * F[i] * S[i]) % mod;
return res;
}
int p, q;
int pw_p[1100000];
int pw_q[1100000];
int f[1010][1010];
inline int dp(int h, int w, int k) {
if(w == 0) return 1;
if(h * w > k) return 0;
if(~f[h][w]) return f[h][w];
int &F = f[h][w] = 1LL * pw_p[w] * dp(h + 1, w, k) % mod;
for(int i = 1; i <= w; i++)
F = (F + 1LL * dp(h + 1, i - 1, k) * q % mod * pw_p[i - 1] % mod * dp(h, w - i, k)) % mod;
return F;
}
inline int solve(int n, int k) {
memset(f, -1, sizeof(f));
dp(0, k, k);
memset(F, 0, sizeof(F));
memset(A, 0, sizeof(A));
for(int i = 0; i <= k; i++) {
F[i] = i ? f[0][i] : 1;
A[i] = !i ? q : 1LL * f[1][i] * q % mod * pw_p[i] % mod;
} return calc(n, k + 1);
}
int main() {
int n = ri, k = ri, x = ri, y = ri;
p = 1LL * x * fsp(y) % mod, q = mod + 1 - p;
int N = min(1000, max(n, k)) * 1001;
pw_p[0] = pw_q[0] = 1;
for(int i = 1; i <= N; i++) {
pw_p[i] = 1LL * pw_p[i - 1] * p % mod;
pw_q[i] = 1LL * pw_q[i - 1] * q % mod;
}
int r1 = solve(n, k);
int r2 = solve(n, k - 1);
printf("%d\n", Mod(r1 + mod - r2));
return 0;
}
```