P10141
题解
- 正难则反
- 正着，设 \(dp(l, r)\) 为合并出 \([l, r]\)的概率，枚举大区间两端点合并（区间DP）
- 复杂度 \(O(n^4)\)
- 反着，设 \(dp(l, r)\) 表示由 \([1, n]\) 分裂出 \([l, r]\) 的概率
- 设大区间为 \([i, j]\)，中间点为 \(k\)
- 若 \([i, k] > [k + 1, j]\)，\(dp(i, k) = \frac{dp(i, j)}{i - j}\) （一共有 \(i - j\) 个空隙，选择其中一个的概率是 \(\frac{1}{i - j}\)）
- 反之，\(dp(k + 1, j) = \frac{dp(i, j)}{i - j}\)
- 这里 \([i, k] > [k + 1, j]\) 的比较规则见题意
- 如果 \(i\) 固定，使得 \([k + 1, j] < [i, k]\) 的 \(j\) 单点递减
- 同样，如果 \(j\) 固定，使得 \([i, k] < [k + 1, j]\) 的 \(i\) 单调递增
- 所以可以采用双指针的方法，维护前/后缀和，把复杂度降到 \(O(n^2)\)
- 此时 \(dp(i, k) = \sum_{p = k + 1}^{j} \frac{dp(i, p)}{p - i}\)
代码
-
小细节
-
为什么不是 \(\le\)
- 因为此时 \([l, r]\) 的编号本身就 \(> [ll[r], l]\)，所以只要值 \(\ge [ll[r],l]\) 就可以
- 而上面 \([l, r]\) 的编号 $ < [r, rr[l]]$ ，如果值相等，那就会取后者而不是 \([l, r]\)
-
前后缀和的 \(l, r\) 具体是谁
-
# include <bits/stdc++.h>
# define int long long
using namespace std;
const int MOD = 1e9 + 7;
const int N = (int)5e3 + 10;
int n;
int s[N];
int dp[N][N], pre[N][N], suf[N][N];
int inv[N], ll[N], rr[N];
int Q_pow(int a, int b){
int ans = 1, p = a;
while(b){
if(b & 1){
ans = (ans * p) % MOD;
}
p = (p * p) % MOD;
b >>= 1;
}
return ans;
}
signed main(){
cin >> n;
inv[0] = 1;
for(int i = 1; i <= n; i++){
cin >> s[i];
s[i] += s[i - 1];
inv[i] = Q_pow(i, MOD - 2);
ll[i] = 1, rr[i] = n;
}
dp[1][n] = pre[1][n] = suf[1][n] = inv[n - 1];
for(int i = n - 1; i >= 1; i--){
for(int l = 1, r = i; r <= n; l++, r++){
while(s[r] - s[l - 1] <= s[rr[l]] - s[r]){
rr[l]--;
}
// l, r + 1
(dp[l][r] += (suf[l][r + 1] - suf[l][rr[l] + 1] + MOD) % MOD) %= MOD;
while(s[r] - s[l - 1] < s[l - 1] - s[ll[r] - 1]){ // 为什么不是 <= !
ll[r]++;
}
// l - 1, r
(dp[l][r] += (pre[l - 1][r] - pre[ll[r] - 1][r] + MOD) % MOD) %= MOD;
(dp[l][r] *= inv[r - l]) %= MOD;
suf[l][r] = suf[l][r + 1];
(suf[l][r] += dp[l][r]) %= MOD;
pre[l][r] = pre[l - 1][r];
(pre[l][r] += dp[l][r]) %= MOD;
}
}
for(int i = 1; i <= n; i++){
cout << dp[i][i] << "\n";
}
cout << "\n";
}