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

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

article 2025/2/1 7:20:31

有一个长度为 $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;
}