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

C++计算特定随机操作后序列元素乘积的期望

news 来源：原创 2025/5/19 13:46:34

有一个长度为 $n$ 的序列 $a_1,a_2,...,a_n$ 。初始序列的所有元素均为 $0$ 。再给定正整数 $m$ 、 $c$ 和 $(n - m + 1)$ 个正整数 $b_1,b_2,...,b_{n-m+1}$ 。
对序列 $a_1,a_2,...,a_n$ 进行 $c$ 次操作，每次操作为：
随机选择整数 $1\leq x\leq n-m+1$ ，其中选到 $y(1\leq y\leq n-m+1)$ 的概率为 $\frac{b_y}{\sum_{i=1}^{n-m+1}b_i}$ 。将 $a_x,a_{x+1},...,a_{x+m-1}$ 增加 $1$ 。
$c$ 次操作中对 $x$ 的随机是独立的。
写一个C++程序求操作完成后序列中所有元素的乘积的期望。为了避免浮点数输出，你需要将答案对 $998244353$ 取模。

输入格式说明：
从标准输入读入数据。
第一行三个整数 $n$ 、 $m$ 、 $c$ ，分别表示序列长度、操作区间长度和操作次数。
第二行 $n - m + 1$ 个整数 $b_1,...,b_{n-m+1}$ ，描述随机的权重。
输出格式说明：
输出到标准输出。
输出一行一个整数，表示 $c$ 次操作后序列中所有数的乘积的期望。
样例1输入为：

3 2 2
1 1

样例1输出为：

样例1解释为：当两次操作选择的x不同时，最终序列为1 2 1，序列元素乘积为2；否则序列为2 2 0或0 2 2，序列元素乘积均为0。两次操作选择的 $x$ 不同的概率为 $\frac{1}{2}$ ，因此输出 $2\times\frac{1}{2} =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;
}

代码解释

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

方法思路

解决代码

代码解释

相关文章：