Codeforces 1855E 数学期望 + DP-Toy模板网

这篇具有很好参考价值的文章主要介绍了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$ ，则 $D P$ 求解即可。令 $d p [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)$ 。文章来源地址https://www.toymoban.com/news/detail-740266.html

#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;
}