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 行…...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...

uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)
要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况,可以通过以下几种方式模拟或触发: 1. 增加CPU负载 运行大量计算密集型任务,例如: 使用多线程循环执行复杂计算(如数学运算、加密解密等)。运行图…...
uniapp中使用aixos 报错
问题: 在uniapp中使用aixos,运行后报如下错误: AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...

蓝桥杯3498 01串的熵
问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798, 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

C++使用 new 来创建动态数组
问题: 不能使用变量定义数组大小 原因: 这是因为数组在内存中是连续存储的,编译器需要在编译阶段就确定数组的大小,以便正确地分配内存空间。如果允许使用变量来定义数组的大小,那么编译器就无法在编译时确定数组的大…...

Golang——7、包与接口详解
包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...