Link

Description

有 $n$ 个人参加比赛,最终的排名恰好不重复。马老师想要知道自己的排名,于是他询问了 $m$ 个人,结果都比他排名靠后。马老师觉得他rank1稳了,求马老师真实排名的期望。

Sol

马老师事件$B_i$为随机一个排名在第$i$名, $P(B_i)=\frac{1}{n}$

设事件$A$为连续$m$次抽排名都没抽中$i$,$P(A) = (\frac{i}{n-1})^m$

那么

$$ P(A|B_i) = (\frac{n-i}{n-1}) ^ m $$

那么根据全概率公式:

$$ P(A|B) = \frac{1}{n} \sum_{i=1}^{n} (\frac{n-i}{n-1}) ^ m $$

再按照贝叶斯公式有:

$$ P(B|A) = \frac{P(A|B)P(B)}{\sum_{i} P(A|B_j)P(B_j)} $$

现在来计算$E(P(B|A))$,我们已经知道$E(P(B)) = i$

$$ E=\frac{\frac{1}{n} \sum_{i=1}^{n} (\frac{n-i}{n-1}) ^ m \times i}{\frac{1}{n} \sum_{i=1}^{n}(\frac{n-i}{n-1}) ^ m} $$

可以约掉$\frac{1}{n}$ ,$(\frac{n-i}{n-1}) ^ m$ 注意该项仅仅可以约掉分母

$$ E = \frac{\sum_{i=1}^{n} (n-i)^m \times i}{\sum_{i=1}^{n} (n-i)^m } $$

对$n-i$这种项的求和倒过来就是$i$了吧,注意换一下后面的乘$i$要变成$n-i$

$$ E = \frac{\sum_{i=1}^{n} i^m \times (n-i)}{\sum_{i=1}^{n} i^m } $$

把$n$放在外面乘,现在就是

$$ E = n - \frac{\sum_{i=1}^{n} i^{m+1}}{\sum_{i=1}^{n} i^m } $$

只要进行自然数幂求和就可以了,现在来推倒自然数幂求和公式。题目仅仅要求在$O(m^2)$级别的时间内做到

我们要计算

$$ \sum_{i=0}^{n} i^m $$

把幂转成第二类斯特林数和下降幂(非常套路

$$ \sum_{i=0}^{n}\sum_{j=0}^{m} \begin{Bmatrix}m\\j\end{Bmatrix} i^{\underline j} $$

把下降幂拆了,约掉分母中的$j!$ 。再把斯特林数提到前面去算

$$ \sum_{j=0}^{m} \begin{Bmatrix}m\\j\end{Bmatrix} \sum_{i=0}^{n} \frac{i!}{(i-j)!} $$

然后不会算了,改变思路。如果不约掉分母中的$j!$的话

$$ \sum_{j=0}^{m} \begin{Bmatrix} m\\ j\end{Bmatrix} j! \sum_{i=0}^{n} \binom{i}{j} $$

这是在上指标求和吧,变成了

$$ \sum_{j=0}^{m} \begin{Bmatrix}m\\j\end{Bmatrix}j!\binom{n+1}{j+1} $$

直接$O(m^2)$预处理第二类斯特林数,注意到$n$的范围很大所以递推顺便算一下就好了

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE = 5e3 + 20;
const int mod = 998244353;

int n, m;
int inv[SIZE], fac[SIZE], s[SIZE][SIZE];

namespace ae86 {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using ae86::read;

int qPow(int a, int b) {
    int ans = 1;
    for ( ; b; b >>= 1, a = a * a % mod) {
        if (b & 1) ans = ans * a % mod;
    }
    return ans % mod;
}

void init() {
    fac[0] = 1;
    for (int i = 1; i <= m + 2; ++ i) fac[i] = fac[i - 1] * i % mod;
    inv[m + 2] = qPow(fac[m + 2], mod - 2) % mod;
    for (int i = m + 1; ~i; -- i) inv[i] = inv[i + 1] * (i + 1) % mod;
    s[0][0] = 1;
    for (int i = 1; i <= m + 2; ++ i) {
        for (int j = 0; j <= i; ++ j) s[i][j] = ((j > 0 ? s[i - 1][j - 1] : 0) + s[i - 1][j] * j) % mod;
    }
}

int sol(int n, int m) {
    int ans = 0, c = n + 1;
    for (int i = 0; i <= m; ++ i) {
        ans = (ans + s[m][i] * fac[i] % mod * c % mod) % mod;
        c = (c * qPow(i + 2, mod - 2) % mod * (n - i) % mod) % mod;
    }
    return ans % mod;
}

signed main() {
    // freopen("code.in", "r", stdin);
    n = read() % mod, m = read(); init();
    int sum1 = 0, sum2 = 0;
    sum1 = sol(n - 1, m + 1), sum2 = qPow(sol(n - 1, m) % mod, mod - 2) % mod;
    (sum1 *= sum2) %= mod; printf("%lld\n", (n - sum1 + mod) % mod);
    return 0;
}
最后修改:2021 年 09 月 28 日
如果觉得我的文章对你有用,请随意赞赏