UVa 10288 Coupous题解 概率递推

题意

有n种彩票，每次抽取一张新彩票，每种彩票出现的概率始终相同。求集齐所有种类彩票的期望抽奖次数，并用带分数表示。

题解

假设当前已经集齐了k种彩票，接下来抽到新一种彩票的概率是\frac{n-k}{n}，则抽到新一种的期望次数是\frac{n}{n-k}，则总期望次数是：

E=\sum_{k=0}^{n-1} \frac{n}{n-k}=n\sum_{k=0}^{n-1} \frac{1}{n-k}

值得注意的是期望与概率的倒数关系并不是那么的显然，有时间需要写一篇文章来讨论这件事情。

代码

写的稍微丑了一点，这个带分数处理的类是现场手写的，比较粗糙。（竞赛码风和工程区别还是很大的啊）

#include <bits/stdc++.h>

using namespace std;

long long gcd(long long a, long long b)
{
    return (b == 0 ? a : gcd(b, a % b));
}

long long read()
{
    long long x;
    cin >> x;
    return x;
}

struct frac
{
    long long intpart;
    long long above;
    long long below;

    void yuefen()
    {
        long long x = gcd(above, below);
        above /= x;
        below /= x;
    }

    void quzheng()
    {
        yuefen();
        if (above >= below)
        {
            intpart += (long long)(above / below);
            above -= (below * (long long)(above / below));
        }
    }

    frac operator+(const frac &obj) const
    {
        frac tmp;

        tmp.intpart = intpart + obj.intpart;
        tmp.above = above * obj.below + below * obj.above;
        tmp.below = below * obj.below;

        return tmp;
    }
} ans, cur;

long long cntdigit(long long x)
{
    int ans = 0;
    while (x)
    {
        x /= 10;
        ++ans;
    }
    return ans;
}
long long n;
signed main()
{
    while (scanf("%lld", &n) != EOF)
    {
        for (long long i = 0; i <= n - 1; ++i)
        {
            cur.intpart = 0;
            cur.above = n;
            cur.below = n - i;
            cur.quzheng();
            if (i == 0)
                ans = cur;
            else
                ans = ans + cur, ans.quzheng();
        }
        if (ans.above == 0)
        {
            cout << ans.intpart << endl;
        }
        else if (cntdigit(ans.intpart) == 0)
        {
            printf("%lld\n", ans.above);
            for (int i = 1; i <= cntdigit(max(ans.above, ans.below)); ++i)
                printf("-");
            printf("\n");
            printf("%lld\n", ans.below);
        }
        else
        {
            for (int i = 1; i <= cntdigit(ans.intpart) + 1; ++i)
                printf(" ");
            printf("%lld", ans.above);
            printf("\n%lld ", ans.intpart);
            for (int i = 1; i <= cntdigit(max(ans.above, ans.below)); ++i)
                printf("-");
            printf("\n");
            for (int i = 1; i <= cntdigit(ans.intpart) + 1; ++i)
                printf(" ");
            printf("%lld\n", ans.below);
        }
    }
}