P1291 [SHOI2002]百事世界杯之旅

P1291 [SHOI2002]百事世界杯之旅

Meaning

考虑共有 $n$ 种卡片的抽卡游戏，每次等概率抽取一种卡片。求抽取到所有种类卡片的期望次数。

Sol

我们考虑现在已经抽取了 $i$ 张卡片，那么我们抽取到不同于我们已有卡片的概率为 $\frac{n-i}{n}$，随之易知抽取到不同于我们已有卡片的期望次数为 $\frac{n}{n-i}$ 次。

那么对于所有的 $i\in[0,n)$ 我们对于期望的线性性相加次数。

答案即 $\sum \frac{n}{i}\approx n\ln{n}$ 。

Detail

1. 注意到奇怪的输出方式。

Code

#include <iostream>
#include <cstdio>
#include <cctype>
using namespace std;

template <typename T>
inline T read() {
    T x = 0, f = 1; char c = getchar();
    while (!isdigit(c)) { if (c == '-') f = - f; c = getchar(); }
    while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
    return x * f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read <int> ()
#define readlint read <lint> ()
const int inf = 1e9 + 1e7;
const lint INF = 1e18 + 1e9;

lint a = 1, b = 1, c;
int n, cnt, l1, l2;

lint Gcd(lint A, lint B) {
    if (A < B) swap(A, B);
    return (!B ? A : Gcd(B, A % B));
}

int main(void) {

    scanf("%d", &n);
    for (int  i = 2; i <= n; i ++) {
        c = b * i / Gcd(b, i);
        a = (c / b) * a + (c / i), b = c;
        c = Gcd(a, b), a /= c, b /= c;
    }
    a = a * n, c = Gcd(a, b), a /= c, b /= c, c = a / b;
    while (c) c /= 10, ++ cnt;
    c = a % b;
    while (c) c /= 10, ++ l1;
    c = b;
    while (c) c /= 10, ++ l2;
    if (!l1) printf("%lld\n", a / b);
    else {
        for (int i = 1; i <= cnt; i ++) putchar(' ');
        printf("%lld\n", a % b);
        printf("%lld", a / b);
        for (int i = 1; i <= l2; i ++) putchar('-');
        printf("\n");
        for (int i = 1; i <= cnt; i ++) putchar(' ');
        printf("%lld\n", b);
    }

    return 0;
}