洛谷P5081 Tweetuzki 爱取球 题解

题目链接：P5081 Tweetuzki 爱取球

题意：

Tweetuzki 有一个袋子，袋子中有 \(N\) 个无差别的球。Tweetuzki 每次随机取出一个球后放回。求取遍所有球的期望次数。

取遍是指，袋子中所有球都被取出来过至少一次。

输入格式：

一行一个整数 \(N\) \((1 \le N \le 10^7)\)。

输出格式：

一行一个整数，表示期望次数。由于这个数可能很大，输出对 \(20040313\) （是个质数）取模。

数据范围：

对于 \(100\%\) 的数据，\(1 \le N \le 10^7\)。

引理：设成功完成事情 \(A\) 的概率为 \(P\) ，如果不成功就继续。则期望 \(\dfrac{1}{P}\) 次完成这件事。

证明：设期望 \(k\) 次完成事情 \(A\) 。根据定义有 \[ k = 1 + p\times 0 + (1 - p)\times k \] 其中 \(1\) 表示初始的一次尝试，\(p\) 表示本次成功，\((1-p)\) 表示本次失败。移项得 \(k = \dfrac{1}{p}\) 。\(\square\)

现在我们来看原题。考虑从 \(n\) 个球中取出一个球，期望次数为 \(\left(\frac{n}{n}\right)^{-1} = 1\) 。

接着考虑取出剩下的 \(n-1\) 个球中的一个球，期望次数为 \(\left(\frac{n-1}{n}\right)^{-1} = \frac{n}{n-1}\) 。依此类推可知答案为： \[ \frac{n}{n} + \frac{n}{n-1}+\frac{n}{n-2}+\cdots+\frac{n}{1} = n \times \sum_{i = 1}^{n - 1}\frac{1}{n - i} \] 时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e7 + 15))

int n,sum,inv[N]; const int p = 20040313;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; inv[1] = 1; sum = 1;
    for(int i = 2; i <= n; i++) {
        inv[i] = (p - p / i) * inv[p % i] % p; sum = (sum + inv[i]) % p;
    } cout << (n * sum % p) << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/blog/SCP-Foundation/solution-p5081