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

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) (nm+1)个正整数 b 1 , b 2 , . . . , b n − m + 1 b_1,b_2,...,b_{n-m+1} b1,b2,...,bnm+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 1xnm+1,其中选到 y ( 1 ≤ y ≤ n − m + 1 ) y(1\leq y\leq n-m+1) y(1ynm+1)的概率为 b y ∑ i = 1 n − m + 1 b i \frac{b_y}{\sum_{i=1}^{n-m+1}b_i} i=1nm+1biby。将 a x , a x + 1 , . . . , a x + m − 1 a_x,a_{x+1},...,a_{x+m-1} ax,ax+1,...,ax+m1增加 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 nm+1个整数 b 1 , . . . , b n − m + 1 b_1,...,b_{n-m+1} b1,...,bnm+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%): 无特殊限制。

为了求解这个问题,我们需要计算操作完成后序列中所有元素的乘积的期望。由于每次操作会影响连续的区间元素,我们需要考虑这些操作之间的依赖关系,并使用生成函数和动态规划的方法来处理。
该方法通过动态规划和生成函数的高效结合,解决了元素乘积期望的计算问题,确保了在合理的时间复杂度内处理较大的输入规模。

方法思路

  1. 问题分析:每次操作随机选择一个区间并增加该区间内的元素值。最终需要计算所有元素乘积的期望。由于元素之间的依赖关系,直接计算所有可能的组合是不现实的。
  2. 生成函数:使用生成函数来表示每个操作对覆盖次数的影响,通过生成函数的导数来计算期望。
  3. 动态规划:利用动态规划来高效计算生成函数的导数,并结合快速幂来优化计算过程。

解决代码

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

代码解释

  1. 输入处理:读取输入的序列长度、区间长度和操作次数,以及每个区间的权重。
  2. 生成覆盖概率:计算每个位置被覆盖的概率,并将权重转换为概率。
  3. 动态规划计算:使用动态规划来计算覆盖所有位置的组合概率,并结合快速幂计算最终结果。
  4. 结果输出:输出最终的期望值,对结果取模处理。

相关文章:

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> 头文件来实现大小写转换。以下是常用的方法&#xff1a; 1. 使用 std::transform 和 std::toupper/std::tolower 1.1 转换为大写 #include <iostream> #include <string> #include <algorithm> //…...

MySQL知识点总结(十六)

请说明在复制拓扑中&#xff0c;中继日志集和从属服务器状态日志的作用。 中继日志用来保存从主服务器接受的二进制日志&#xff0c;与二进制日志相同的格式存储&#xff0c;由服务器自动管理&#xff0c;在其全部内容重放后会自动删除。 从属服务器状态日志存储关于如何连接…...

Windows程序设计10:文件指针及目录的创建与删除

文章目录 前言一、文件指针是什么&#xff1f;二、设置文件指针的位置&#xff1a;随机读写&#xff0c;SetFilePointer函数1.函数说明2.函数实例 三、 目录的创建CreateDirectory四、目录的删除RemoveDirectory总结 前言 Windows程序设计10&#xff1a;文件指针及目录的创建与…...

geolocator包的功能和用法

文章目录 1 概念介绍2 使用方法3 示例代码4 体验分享 我们在上一章回中介绍了如何实现滑动菜单相关的内容&#xff0c;本章回中将介绍如何获取位置信息.闲话休提&#xff0c;让我们一起Talk Flutter吧。 1 概念介绍 我们在这里说的获取位置信息本质上是获取当前手机所在位置的…...

Node.js——body-parser、防盗链、路由模块化、express-generator应用生成器

个人简介 &#x1f440;个人主页&#xff1a; 前端杂货铺 &#x1f64b;‍♂️学习方向&#xff1a; 主攻前端方向&#xff0c;正逐渐往全干发展 &#x1f4c3;个人状态&#xff1a; 研发工程师&#xff0c;现效力于中国工业软件事业 &#x1f680;人生格言&#xff1a; 积跬步…...

22.Word:小张-经费联审核结算单❗【16】

目录 NO1.2 NO3.4​ NO5.6.7 NO8邮件合并 MS搜狗输入法 NO1.2 用ms打开文件&#xff0c;而不是wps❗不然后面都没分布局→页面设置→页面大小→页面方向→上下左右&#xff1a;页边距→页码范围&#xff1a;多页&#xff1a;拼页光标处于→布局→分隔符&#xff1a;分节符…...

Agent 高频知识汇总:查漏补缺参考大全

Agent 高频问题汇总 一、基础概念类 &#xff08;一&#xff09;请解释 Agent 的概念及其主要特点 Agent 是一种能够感知所处环境&#xff0c;并基于感知信息做出决策、采取行动以实现特定目标的实体。它既可以是简单的规则基系统&#xff0c;也能是复杂的智能体&#xff0c…...

本地化部署DeepSeek-R1

本文环境搭建均基于免费工具&#xff0c;感谢开源。 一、下载工具并安装 1. Ollama&#xff1a;最新版本 0.5.7 官网在这里 https://ollama.com/download 但是下载太慢&#xff0c;得换个思路 https://sourceforge.net/projects/ollama.mirror/ 2.Chatbox https://cha…...

验证二叉搜索数(98)

98. 验证二叉搜索树 - 力扣&#xff08;LeetCode&#xff09; 解法&#xff1a; /*** 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源码时&#xff0c;很多类的引用位置爆红找不到&#xff0c;或无法跳转过去&#xff0c;而自己的Linux机器往往缺乏各种C依赖库&#xff0c;配置安装比较麻烦&#xff0c;因此总体的思路是通过CLion远程连接SR社区已经安装完各种依赖库的Docker容器&#xff0c;进行编…...

数模测评:doubao1.5>deepseek-v3>gpt-o1

本次测试了当前评价最高的三款大模型doubao1.5、gpt-o1、deepseek-v3(r1崩溃)&#xff0c;都是采用无提示词的硬核提问方式&#xff0c;测试视频如下。 gpto1、doubao1.5、deepseek测评 测试方式&#xff1a; 上传美赛六道题目文件 直接提问以下5句话&#xff1a; 这是一道数学…...

晴,初三,年已过

既然直播如此影响情绪&#xff0c;为什么还要直播&#xff1f;因为无聊&#xff1f;明明那么多事情可以打发时间。 真不想懂。 今日初三&#xff0c;昨天晚上小舅家聚&#xff0c;今天大舅家聚&#xff0c;计划明天小姨妈家聚。 今晚喝了点大舅哥哥泡的白葡萄酒&#xff0c;…...

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系统&#xff0c;这是由Alan Kay最早提出的。在随后的发展中&#xff0c;Smalltalk逐渐演化&#xff0c;并出现了Smalltalk-72和Smalltalk-76等版本。最终&#xff0c;在经过近10年的研究与发展后&#xff0c;Xerox研究…...

KVM/ARM——基于ARM虚拟化扩展的VMM

1. 前言 ARM架构为了支持虚拟化做了些扩展&#xff0c;称为虚拟化扩展(Virtualization Extensions)。原先为VT-x创建的KVM(Linux-based Kernel Virtual Machine)适配了ARM体系结构&#xff0c;引入了KVM/ARM (the Linux ARM hypervisor)。KVM/ARM没有在hypervisor中引入复杂的…...

Windows系统中Docker可视化工具对比分析,Docker Desktop,Portainer,Rancher

Docker可视化工具对比分析&#xff0c;Docker Desktop&#xff0c;Portainer&#xff0c;Rancher Windows系统中Docker可视化工具对比分析1. 工具概览2. Docker Desktop官网链接&#xff1a;主要优点&#xff1a;主要缺点&#xff1a;版本更新频率&#xff1a; 3. Portainer官网…...

【架构面试】二、消息队列和MySQL和Redis

MQ MQ消息中间件 问题引出与MQ作用 常见面试问题&#xff1a;面试官常针对项目中使用MQ技术的候选人提问&#xff0c;如如何确保消息不丢失&#xff0c;该问题可考察候选人技术能力。MQ应用场景及作用&#xff1a;以京东系统下单扣减京豆为例&#xff0c;MQ用于交易服和京豆服…...

算法【完全背包】

完全背包与01背包的区别仅在于每种商品可以选取无限次。时间复杂度O(物品数量 * 背包容量) 下面通过题目加深理解。 题目一 测试链接&#xff1a;疯狂的采药 - 洛谷 分析&#xff1a;这是一道完全背包的模板题。对于第i个物品的可能性展开也有两种&#xff0c;第一种是不取第…...

二叉树的遍历

有一个结点的二叉树。给出每个结点的两个子结点编号&#xff0c;建立一棵二叉树&#xff0c;如果是叶子结点&#xff0c;则输入 0 0。 建好树这棵二叉树之后&#xff0c;依次求出它的前序、中序、后序列遍历。 输入格式: 第一行一个整数n &#xff0c;表示结点数。 之后n 行…...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

Maven 概述、安装、配置、仓库、私服详解

目录 1、Maven 概述 1.1 Maven 的定义 1.2 Maven 解决的问题 1.3 Maven 的核心特性与优势 2、Maven 安装 2.1 下载 Maven 2.2 安装配置 Maven 2.3 测试安装 2.4 修改 Maven 本地仓库的默认路径 3、Maven 配置 3.1 配置本地仓库 3.2 配置 JDK 3.3 IDEA 配置本地 Ma…...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...

搭建DNS域名解析服务器(正向解析资源文件)

正向解析资源文件 1&#xff09;准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2&#xff09;服务端安装软件&#xff1a;bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...