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

有一个长度为$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\le x\le n-m+1$，其中选到$y(1\le y\le 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

样例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%): 无特殊限制。

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

方法思路

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. 结果输出：输出最终的期望值，对结果取模处理。