P1291 [SHOI2002]百事世界杯之旅 （期望）

P1291 [SHOI2002]百事世界杯之旅 （期望）

题意：

中文不解释了

分析：

假设表示一共有n个球星，现在还剩k个未收集到，还需购买饮料的平均次数。

那么要求的就是

假设我们现在推到了，我们再买一瓶饮料，有两种可能性，一种是：我们买到了我们没有拥有的球员，那么剩下的子问题就是；如果买到了我们拥有的球员，那么剩下的子问题就是。然而我们任意买一个瓶盖，有的可能性买到我们没有的，有的可能性买到我们已经有的。所以这道题目的递推是就是：  

化简得:

#include<cstdio>
#include<cstring>using namespace std;typedef long long ll;inline ll gcd(ll a,ll b){if(b==0) return a;else return gcd(b,a%b);
}inline int dig_len(ll a){int ans=0;while(a){ans++;a/=10;}return ans;
}int main(){int n;ll p=0,q=1,r;scanf("%d",&n);for(int i=1;i<=n;i++){p=p*i+q*n;q*=i;ll f=gcd(p,q);p/=f;q/=f;}r=p/q;p=p%q;if(p==0){printf("%lldn",r);}else{for(int i=dig_len(r);i>0;i--){printf(" ");}printf("%lldn",p);if(r) printf("%lld",r);for(int i=dig_len(q);i>0;i--){printf("-");}printf("n");for(int i=dig_len(r);i>0;i--){printf(" ");}printf("%lldn",q);}return 0;
}