C++计算特定随机操作后序列元素乘积的期望
有一个长度为 n n n的序列 a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1,a2,...,an。初始序列的所有元素均为 0 0 0。再给定正整数 m m m、 c c c和 ( n − m + 1 ) (n-m+1) (n−m+1)个正整数 b 1 , b 2 , . . . , b n − m + 1 b_1,b_2,...,b_{n-m+1} b1,b2,...,bn−m+1。
对序列 a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1,a2,...,an进行 c c c次操作,每次操作为:
随机选择整数 1 ≤ x ≤ n − m + 1 1\leq x\leq n-m+1 1≤x≤n−m+1,其中选到 y ( 1 ≤ y ≤ n − m + 1 ) y(1\leq y\leq n-m+1) y(1≤y≤n−m+1)的概率为 b y ∑ i = 1 n − m + 1 b i \frac{b_y}{\sum_{i=1}^{n-m+1}b_i} ∑i=1n−m+1biby。将 a x , a x + 1 , . . . , a x + m − 1 a_x,a_{x+1},...,a_{x+m-1} ax,ax+1,...,ax+m−1增加 1 1 1。
c c c次操作中对 x x x的随机是独立的。
写一个C++程序求操作完成后序列中所有元素的乘积的期望。为了避免浮点数输出,你需要将答案对 998244353 998244353 998244353取模。
输入格式说明:
从标准输入读入数据。
第一行三个整数 n n n、 m m m、 c c c,分别表示序列长度、操作区间长度和操作次数。
第二行 n − m + 1 n-m+1 n−m+1个整数 b 1 , . . . , b n − m + 1 b_1,...,b_{n-m+1} b1,...,bn−m+1,描述随机的权重。
输出格式说明:
输出到标准输出。
输出一行一个整数,表示 c c c次操作后序列中所有数的乘积的期望。
样例1输入为:
3 2 2
1 1
样例1输出为:
1
样例1解释为:当两次操作选择的x不同时,最终序列为1 2 1,序列元素乘积为2;否则序列为2 2 0或0 2 2,序列元素乘积均为0。两次操作选择的 x x x不同的概率为 1 2 \frac{1}{2} 21,因此输出 2 × 1 2 = 1 2\times\frac{1}{2} =1 2×21=1。
样例 2 输入
10 3 10
1 2 3 4 5 6 7 8
样例 2 输出
721023399
样例 3 输入
20 12 98765
9 8 7 6 5 4 3 2 1
样例 3 输出
560770686
子任务
对于所有测试数据,2 ≤ m ≤ n ≤ 50,1 ≤ c < 998244353,对于 1 ≤ i ≤ n - m + 1,1 ≤ bi ≤ 105。
Subtask 1 (10%): m ≤ 8。
Subtask 2 (20%): m ≤ 16。
Subtask 3 (15%): n ≤ 20, c ≤ n。
Subtask 4 (15%): n ≤ 30, c ≤ n。
Subtask 5 (15%): n ≤ 40, c ≤ n。
Subtask 6 (15%): c ≤ n。
Subtask 7 (10%): 无特殊限制。
为了求解这个问题,我们需要计算操作完成后序列中所有元素的乘积的期望。由于每次操作会影响连续的区间元素,我们需要考虑这些操作之间的依赖关系,并使用生成函数和动态规划的方法来处理。
该方法通过动态规划和生成函数的高效结合,解决了元素乘积期望的计算问题,确保了在合理的时间复杂度内处理较大的输入规模。
方法思路
- 问题分析:每次操作随机选择一个区间并增加该区间内的元素值。最终需要计算所有元素乘积的期望。由于元素之间的依赖关系,直接计算所有可能的组合是不现实的。
- 生成函数:使用生成函数来表示每个操作对覆盖次数的影响,通过生成函数的导数来计算期望。
- 动态规划:利用动态规划来高效计算生成函数的导数,并结合快速幂来优化计算过程。
解决代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 998244353;ll mod_pow(ll a, ll b) {ll res = 1;while (b) {if (b & 1) res = res * a % MOD;a = a * a % MOD;b >>= 1;}return res;
}ll inv(ll x) {return mod_pow(x, MOD - 2);
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m, c;cin >> n >> m >> c;int k = n - m + 1;vector<int> b(k);ll sum_b = 0;for (auto& x : b) {cin >> x;sum_b += x;}sum_b %= MOD;vector<vector<int>> covers(n + 1);for (int x = 1; x <= k; ++x) {for (int i = x; i <= x + m - 1; ++i) {covers[i].push_back(x);}}vector<ll> prob(n + 1);for (int i = 1; i <= n; ++i) {for (int x : covers[i]) {prob[i] += b[x - 1];}prob[i] %= MOD;prob[i] = prob[i] * inv(sum_b % MOD) % MOD;}if (c < n) {cout << 0 << '\n';return 0;}vector<ll> dp(n + 1, 0);dp[0] = 1;for (int i = 1; i <= n; ++i) {for (int j = n; j >= 1; --j) {dp[j] = (dp[j] + dp[j - 1] * prob[i]) % MOD;}}ll fact = 1;for (int i = 0; i < n; ++i) {fact = fact * (c - i) % MOD;}ll ans = dp[n] * fact % MOD;cout << ans << '\n';return 0;
}
代码解释
- 输入处理:读取输入的序列长度、区间长度和操作次数,以及每个区间的权重。
- 生成覆盖概率:计算每个位置被覆盖的概率,并将权重转换为概率。
- 动态规划计算:使用动态规划来计算覆盖所有位置的组合概率,并结合快速幂计算最终结果。
- 结果输出:输出最终的期望值,对结果取模处理。
相关文章:
C++计算特定随机操作后序列元素乘积的期望
有一个长度为 n n n的序列 a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1,a2,...,an。初始序列的所有元素均为 0 0 0。再给定正整数 m m m、 c c c和 ( n − m 1 ) (n-m1) (n−m1)个正整数 b 1 , b 2 , . . . , b n − m 1 b_1,b_2,...,b_{n-m1} b1,b2,...,bn−m1…...
c++字母大小写转换
可以通过标准库中的 <algorithm> 和 <cctype> 头文件来实现大小写转换。以下是常用的方法: 1. 使用 std::transform 和 std::toupper/std::tolower 1.1 转换为大写 #include <iostream> #include <string> #include <algorithm> //…...
MySQL知识点总结(十六)
请说明在复制拓扑中,中继日志集和从属服务器状态日志的作用。 中继日志用来保存从主服务器接受的二进制日志,与二进制日志相同的格式存储,由服务器自动管理,在其全部内容重放后会自动删除。 从属服务器状态日志存储关于如何连接…...
Windows程序设计10:文件指针及目录的创建与删除
文章目录 前言一、文件指针是什么?二、设置文件指针的位置:随机读写,SetFilePointer函数1.函数说明2.函数实例 三、 目录的创建CreateDirectory四、目录的删除RemoveDirectory总结 前言 Windows程序设计10:文件指针及目录的创建与…...
geolocator包的功能和用法
文章目录 1 概念介绍2 使用方法3 示例代码4 体验分享 我们在上一章回中介绍了如何实现滑动菜单相关的内容,本章回中将介绍如何获取位置信息.闲话休提,让我们一起Talk Flutter吧。 1 概念介绍 我们在这里说的获取位置信息本质上是获取当前手机所在位置的…...
Node.js——body-parser、防盗链、路由模块化、express-generator应用生成器
个人简介 👀个人主页: 前端杂货铺 🙋♂️学习方向: 主攻前端方向,正逐渐往全干发展 📃个人状态: 研发工程师,现效力于中国工业软件事业 🚀人生格言: 积跬步…...
22.Word:小张-经费联审核结算单❗【16】
目录 NO1.2 NO3.4 NO5.6.7 NO8邮件合并 MS搜狗输入法 NO1.2 用ms打开文件,而不是wps❗不然后面都没分布局→页面设置→页面大小→页面方向→上下左右:页边距→页码范围:多页:拼页光标处于→布局→分隔符:分节符…...
Agent 高频知识汇总:查漏补缺参考大全
Agent 高频问题汇总 一、基础概念类 (一)请解释 Agent 的概念及其主要特点 Agent 是一种能够感知所处环境,并基于感知信息做出决策、采取行动以实现特定目标的实体。它既可以是简单的规则基系统,也能是复杂的智能体,…...
本地化部署DeepSeek-R1
本文环境搭建均基于免费工具,感谢开源。 一、下载工具并安装 1. Ollama:最新版本 0.5.7 官网在这里 https://ollama.com/download 但是下载太慢,得换个思路 https://sourceforge.net/projects/ollama.mirror/ 2.Chatbox https://cha…...
验证二叉搜索数(98)
98. 验证二叉搜索树 - 力扣(LeetCode) 解法: /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* …...
StarRocks BE源码编译、CLion高亮跳转方法
阅读SR BE源码时,很多类的引用位置爆红找不到,或无法跳转过去,而自己的Linux机器往往缺乏各种C依赖库,配置安装比较麻烦,因此总体的思路是通过CLion远程连接SR社区已经安装完各种依赖库的Docker容器,进行编…...
数模测评:doubao1.5>deepseek-v3>gpt-o1
本次测试了当前评价最高的三款大模型doubao1.5、gpt-o1、deepseek-v3(r1崩溃),都是采用无提示词的硬核提问方式,测试视频如下。 gpto1、doubao1.5、deepseek测评 测试方式: 上传美赛六道题目文件 直接提问以下5句话: 这是一道数学…...
晴,初三,年已过
既然直播如此影响情绪,为什么还要直播?因为无聊?明明那么多事情可以打发时间。 真不想懂。 今日初三,昨天晚上小舅家聚,今天大舅家聚,计划明天小姨妈家聚。 今晚喝了点大舅哥哥泡的白葡萄酒,…...
Vue3 v-bind 和 v-model 对比
1. 基本概念 1.1 v-bind 单向数据绑定从父组件向子组件传递数据简写形式为 : 1.2 v-model 双向数据绑定父子组件数据同步本质是 v-bind 和 v-on 的语法糖 2. 基础用法对比 2.1 表单元素绑定 <!-- v-bind 示例 --> <template><input :value"text&quo…...
Smalltalk语言是何物?面向对象鼻祖Simula的诞生?Simula和Smalltalk有什么区别?面向对象设计?
Smalltalk语言是何物? Smalltalk语言的前身可以追溯到Flex系统,这是由Alan Kay最早提出的。在随后的发展中,Smalltalk逐渐演化,并出现了Smalltalk-72和Smalltalk-76等版本。最终,在经过近10年的研究与发展后,Xerox研究…...
KVM/ARM——基于ARM虚拟化扩展的VMM
1. 前言 ARM架构为了支持虚拟化做了些扩展,称为虚拟化扩展(Virtualization Extensions)。原先为VT-x创建的KVM(Linux-based Kernel Virtual Machine)适配了ARM体系结构,引入了KVM/ARM (the Linux ARM hypervisor)。KVM/ARM没有在hypervisor中引入复杂的…...
Windows系统中Docker可视化工具对比分析,Docker Desktop,Portainer,Rancher
Docker可视化工具对比分析,Docker Desktop,Portainer,Rancher Windows系统中Docker可视化工具对比分析1. 工具概览2. Docker Desktop官网链接:主要优点:主要缺点:版本更新频率: 3. Portainer官网…...
【架构面试】二、消息队列和MySQL和Redis
MQ MQ消息中间件 问题引出与MQ作用 常见面试问题:面试官常针对项目中使用MQ技术的候选人提问,如如何确保消息不丢失,该问题可考察候选人技术能力。MQ应用场景及作用:以京东系统下单扣减京豆为例,MQ用于交易服和京豆服…...
算法【完全背包】
完全背包与01背包的区别仅在于每种商品可以选取无限次。时间复杂度O(物品数量 * 背包容量) 下面通过题目加深理解。 题目一 测试链接:疯狂的采药 - 洛谷 分析:这是一道完全背包的模板题。对于第i个物品的可能性展开也有两种,第一种是不取第…...
二叉树的遍历
有一个结点的二叉树。给出每个结点的两个子结点编号,建立一棵二叉树,如果是叶子结点,则输入 0 0。 建好树这棵二叉树之后,依次求出它的前序、中序、后序列遍历。 输入格式: 第一行一个整数n ,表示结点数。 之后n 行…...
华为云AI开发平台ModelArts
华为云ModelArts:重塑AI开发流程的“智能引擎”与“创新加速器”! 在人工智能浪潮席卷全球的2025年,企业拥抱AI的意愿空前高涨,但技术门槛高、流程复杂、资源投入巨大的现实,却让许多创新构想止步于实验室。数据科学家…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
3.3.1_1 检错编码(奇偶校验码)
从这节课开始,我们会探讨数据链路层的差错控制功能,差错控制功能的主要目标是要发现并且解决一个帧内部的位错误,我们需要使用特殊的编码技术去发现帧内部的位错误,当我们发现位错误之后,通常来说有两种解决方案。第一…...
Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...
关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命
在华东塑料包装行业面临限塑令深度调整的背景下,江苏艾立泰以一场跨国资源接力的创新实践,重新定义了绿色供应链的边界。 跨国回收网络:废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点,将海外废弃包装箱通过标准…...
2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面
代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口(适配服务端返回 Token) export const login async (code, avatar) > {const res await http…...
c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
python执行测试用例,allure报乱码且未成功生成报告
allure执行测试用例时显示乱码:‘allure’ �����ڲ����ⲿ���Ҳ���ǿ�&am…...
