SP1026 FAVDICE - Favorite Dice 题解

题目链接：FAVDICE - Favorite Dice

题意：

多组询问。

一个 $n(1\le n \le 1000)$ 面的骰子，求期望掷几次能使得每一面都被掷到。

前置知识：一件事有 $\frac{1}{p}$ 的概率完成，则期望要做 $p$ 次。

那么这题就很简单了。设 $f_i$ 表示扔出 $i$ 个点数的期望步数，则

$$f_i = f_{i-1} + \frac{n}{n-(i-1)}$$

后面那个就是 $i-1$ 个点数的时候有 $\frac{n-(i-1)}{n}$ 的概率扔出其他的点数，所以期望就是倒数。

时间复杂度 $\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)())

void solve()
{
    int n; cin >> n; double r = 0;
    for(int i = 1; i <= n; i++) r += (double)n / (n - (i - 1));
    cout << r << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cout << fixed << setprecision(2);
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}

---

题外话：

好耶，这次居然 20 分钟就做出来了。