当前位置: 首页 > news >正文

Codeforces 1855E 数学期望 + DP

题意

传送门 Codeforces 1855E Expected Destruction

题解

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

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

#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;
}
http://www.lryc.cn/news/215803.html

相关文章:

  • 5-1CComplex运算符重载为友元
  • Vue3.0 watch和watchEffect监听器:VCA
  • 1360. 日期之间隔几天
  • ubuntu配置 Conda 更改默认环境路径
  • 华山编程培训中心——工业相机飞拍
  • linux 释放缓存命令并做成定时任务
  • 求解一个整数中含多少个1
  • js编写一个函数判断所有数据类型
  • Python对于时间相关模块的学习记录(time,datetime等模块)
  • 【C#】获得所有可见窗口信息
  • ffmpeg的基本功能介绍
  • QECon大会亮相产品,支持UI自动化测试?RunnerGo
  • Linux开关机相关的命令解析
  • C++二分查找算法的应用:俄罗斯套娃信封问题
  • redis如何保证和mysql数据的一致性
  • SpringBoot整合Redisson,赶紧整起来!
  • 测试Whisper效果
  • Seata 四种事务模式
  • 超好用的IDEA插件推荐,写完代码直接调试接口
  • 发送post请求、携带cookie、响应对象、高级用法
  • JMeter接口测试性能测试
  • MongoDB——MongoDB删除系统自带的local数据库
  • 【LeetCode刷题-链表】--203.移除链表元素
  • Microsoft Dynamics 365 CE 扩展定制 - 3. SDK企业功能
  • 人工智能基础_机器学习016_BGD批量梯度下降求解多元一次方程_使用SGD随机梯度下降计算一元一次方程---人工智能工作笔记0056
  • 硬件测试(二):波形质量
  • PostgreSQL 数据库日志相关参数
  • delete请求,express获取req.body失败
  • 2023年江西省职业院校技能竞赛“网络安全”赛项样题
  • groovy下载与安装