Codeforces 1855E 数学期望 + DP

题意

传送门 Codeforces 1855E Expected Destruction

题解

将 $S_i$ 运动至 $S_{i+1}$ 的情况看作后者消失，则 $S_i$ 在碰到 $S_{i+1}$ 前，$S_{i+1}$ 必然存在。

根据数学期望的线性性质，可以独立地考虑每一个 $S_i$ 在碰到 $S_{i+1}$ 时的期望步数。对于每一对 $S_i,S_{i+1}$，考虑每一步，$S_i$ 与 $S_{i+1}$ 前进的概率都为 $1/2$，则 $DP$ 求解即可。令 $dp[x][y]$ 为 $S_i$ 与 $S_{i+1}$ 距离为 $x$ 且 $S_{i+1}$ 与 $m+1$ 距离为 $y$ 为初始状态情况下 $S_i$ 对答案的贡献，则答案为 $\sum dp[S_{i+1}-S_i][(m+1)-S_{i+1}]$。总时间复杂度 $O(m^2)$。

#include <bits/stdc++.h>
using namespace std;
constexpr int MOD = 1e9 + 7;
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin >> n >> m;vector<int> a(n);for (int i = 0; i < n; ++i) {cin >> a[i];}a.push_back(m + 1);using ll = long long;auto power = [&](int x, int n) {int res = 1;while (n > 0) {if (n & 1) {res = (ll)res * x % MOD;}x = (ll)x * x % MOD, n >>= 1;}return res;};int inv2 = power(2, MOD - 2);vector<vector<int>> dp(m + 1, vector<int>(m + 1));for (int w = 1; w <= m; ++w) {for (int left = w; left > 0; --left) {int right = w - left;if (right > 0) {dp[left][right] = (ll)(1 + dp[left - 1][right] + dp[left + 1][right - 1]) % MOD * inv2 % MOD;} else {dp[left][right] = 1 + dp[left - 1][right];}}}int res = 0;for (int i = 0; i < n; ++i) {(res += dp[a[i + 1] - a[i]][m + 1 - a[i + 1]]) %= MOD;}cout << res << '\n';return 0;
}