题意：大街上到处在卖彩票，一元钱一张。购买撕开它上面的锡箔，你会看到一个漂亮的图
案。图案有n种，如果你收集到所有n（n≤33）种彩票，就可以得大奖。请问，在平均情况
下，需要买多少张彩票才能得到大奖呢？如n=5时答案为137/12。
分析：设f[i]代表还有i个优惠券没有收集到的期望开箱次数，那么我们只要计算再没有取到的期望+上一个取到的期望+操作次数1，即f[i]=(n-i)/n*f[i]+i/n*f[i+1]+1,移项后是f[i] = f[i+1] + n/i,然后就是一个分数计算的模板了

整理了一个分数类模板，支持常见操作，记录一下：

const int maxn = 510;
typedef long long LL;
struct Fraction{
    LL a, b; //a代表分子，b代表分母
    Fraction(){
        a = 0; b = 1;
    }
    void reduction(){
        if(a == 0){
            b = 1;
            return;
        }
        LL gcdnum = __gcd(a, b);
        a /= gcdnum;
        b /= gcdnum;
    }
    Fraction(LL num){ //整数
        a = num; b = 1;
    }
    Fraction(LL x, LL y){
        a = x, b = y;
        this->reduction();
    }
    void operator = (const LL &num){
        a = num; b = 1;
        this -> reduction();
    }
    void operator = (const Fraction &y){
        a = y.a; b = y.b;
        this -> reduction();
    }
    Fraction operator + (const Fraction &y) const{
        LL gcdnum = __gcd(b, y.b);
        Fraction tmp = Fraction(a * (y.b / gcdnum) + y.a * (b / gcdnum) , b / gcdnum * y.b);
        tmp.reduction();
        return tmp;
    }
    Fraction operator + (const LL &y) const{
        return ((*this) + Fraction(y));
    }
    Fraction operator - (const Fraction &y) const{
        return ((*this) + Fraction(-y.a, y.b));
    }
    Fraction operator - (const LL &y) const{
        return ((*this) - Fraction(y));
    }
    Fraction operator * (const Fraction &y) const{
        Fraction tmp = Fraction(a * y.a, b * y.b);
        tmp.reduction();
        return tmp;
    }
    Fraction operator / (const Fraction &y) const{
        return ((*this) * Fraction(y.b, y.a));
    }
    void print(){
        if(b == 1){
            printf("%lld\n", a);
        }
        else{
            LL num = a / b;
            LL tmp = num;
            int len = 0;
            while(tmp){
                len++; tmp /= 10;
            }
            for(int i = 0; i < len; i++){
                printf(" ");
            }
            if(len != 0) printf(" ");
            printf("%lld\n", a % b);
            if(num != 0) printf("%lld ", num);
            tmp = b;
            while(tmp){
                printf("-");
                tmp /= 10;
            }
            printf("\n");
            for(int i = 0; i < len; i++) printf(" ");
            if(len != 0) printf(" ");
            printf("%lld\n", b);
        }
    }
};

本题完整代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 510;
typedef long long LL;
struct Fraction{
    LL a, b; //a代表分子，b代表分母
    Fraction(){
        a = 0; b = 1;
    }
    void reduction(){
        if(a == 0){
            b = 1;
            return;
        }
        LL gcdnum = __gcd(a, b);
        a /= gcdnum;
        b /= gcdnum;
    }
    Fraction(LL num){ //整数
        a = num; b = 1;
    }
    Fraction(LL x, LL y){
        a = x, b = y;
        this->reduction();
    }
    void operator = (const LL &num){
        a = num; b = 1;
        this -> reduction();
    }
    void operator = (const Fraction &y){
        a = y.a; b = y.b;
        this -> reduction();
    }
    Fraction operator + (const Fraction &y) const{
        LL gcdnum = __gcd(b, y.b);
        Fraction tmp = Fraction(a * (y.b / gcdnum) + y.a * (b / gcdnum) , b / gcdnum * y.b);
        tmp.reduction();
        return tmp;
    }
    Fraction operator + (const LL &y) const{
        return ((*this) + Fraction(y));
    }
    Fraction operator - (const Fraction &y) const{
        return ((*this) + Fraction(-y.a, y.b));
    }
    Fraction operator - (const LL &y) const{
        return ((*this) - Fraction(y));
    }
    Fraction operator * (const Fraction &y) const{
        Fraction tmp = Fraction(a * y.a, b * y.b);
        tmp.reduction();
        return tmp;
    }
    Fraction operator / (const Fraction &y) const{
        return ((*this) * Fraction(y.b, y.a));
    }
    void print(){
        if(b == 1){
            printf("%lld\n", a);
        }
        else{
            LL num = a / b;
            LL tmp = num;
            int len = 0;
            while(tmp){
                len++; tmp /= 10;
            }
            for(int i = 0; i < len; i++){
                printf(" ");
            }
            if(len != 0) printf(" ");
            printf("%lld\n", a % b);
            if(num != 0) printf("%lld ", num);
            tmp = b;
            while(tmp){
                printf("-");
                tmp /= 10;
            }
            printf("\n");
            for(int i = 0; i < len; i++) printf(" ");
            if(len != 0) printf(" ");
            printf("%lld\n", b);
        }
    }
} dp[maxn];

int main()
{
    int n;
    while(scanf("%d", &n) != EOF)
    {
        dp[0] = 0;
        for(int i = 1; i <= n; i++) dp[i] = dp[i - 1] + Fraction(1, i);
        dp[n] = dp[n] * n;
        dp[n].print();
    }
    return 0;
}