当前位置: 首页 > 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 行…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; 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&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

蓝桥杯3498 01串的熵

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

C++使用 new 来创建动态数组

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

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、一个结构体实现多…...