526互联

AT_abc326_e Revenge of "The Salary of AtCoder Inc." 题解

发布时间 2023-10-31 10:18:35作者: RainPPR

AT_abc326_e Revenge of "The Salary of AtCoder Inc." 题解

一道简单的概率论+动态规划题目（然而我赛时没看这道题

题意

有一个长度为 \(n\) 的序列 \(A\)、一个 \(n\) 面骰子，掷若干次骰子，如果这一次掷骰子的点数小于等于上一次的点数，则结束。

定义这若干次掷骰子的总的结果为，每次掷出的点数 \(x\) 对答案的贡献为 \(A_x\)。

求最终结果的期望值对 \(998244353\) 取模。

分析

回忆高中数学（数学期望的公式

\(E(X)=\sum\limits_{k=1}^\infty x_kp_x\)，其中 \(x_k\) 为 \(X\) 的一个取值，\(p_k\) 为此取值对应的概率。

而在本题中，显然的 \(A_x\) 即为取值，而我们要求的则是其对应的概率 \(p_k\)。

考虑动态规划解决，显然的：

对于一个下标 \(x\)，它可能从小于它的任意一个转移过来，即取值一定严格递增。

于是有转移式：\(p_i=\sum\limits_{j=0}^{i-1}(\frac{1}{n}p_j)\)，其中 \(\frac{1}{n}p_j\) 表示计入 \((j\to i)\) 的贡献。

整理一下就是：\(p_i=\frac{1}{n}\sum\limits_{j=0}^{i-1}p_i\)，可以使用一个变量滚动解决。

代码

评测记录：https://atcoder.jp/contests/abc326/submissions/47082411

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int MOD = 998244353;

#define rr read()
inline int read() {
    int num = 0, flag = 0, ch = getchar();
    for (; !isdigit(ch); ch = getchar()) flag |= ch == '-';
    for (; isdigit(ch); ch = getchar()) num = (num << 1) + (num << 3) + ch - '0';
    return flag ? -num : num;
}

inline ll qpow(ll a, int b, ll p) {
    ll r = 1;
    for (; b; b >>= 1, a = a * a % p) if (b & 1) r = r * a % p;
    return r;
}

signed main() {
    int n = rr, inv = qpow(n, MOD - 2, MOD);
    ll r = 0, p = inv; while (n--)
        r = (r + rr * p) % MOD, p = (p + p * inv) % MOD;
    printf("%lld\n", r);
    return 0;
}