P1291 [SHOI2002]百事世界杯之旅（概率）

P1291 [SHOI2002]百事世界杯之旅

设$f(n,k)$表示共n个名字,剩下k个名字未收集到，还需购买饮料的平均次数

则有：

$f(n,k)=\frac{n-k}{n}*f(n,k) + \frac{k}{n}*f(n,k+1) +1$

移项整理，可得：

$f(n,k)=f(n,k+1)+\frac{n}{k}$

根据递推式，可得：

$f(n,0)=n\sum_{k=1}^{n}\frac{1}{k}$

蓝后gcd搞搞约分

注意输出

end.

#include<iostream>

#include<cstdio>

#include<cstring>

#define re register

using namespace std;

typedef long long ll;

ll p,q=,g; int n;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

int wid(ll x){//计算位数

    int res=;

    for(;x;x/=)++res;

    return res;

}

int main(){

    scanf("%d",&n);

    for(re int i=;i<=n;++i){

        p=p*i+q*n; q*=i;

        g=gcd(p,q);

        p/=g,q/=g;

    }g=p/q,p%=q;
//分多种情况输出

    if(!p) printf("%lld",g);

    else{

        for(re int i=wid(g);i>=;--i) putchar(' ');

        printf("%lld\n",p);

        if(g) printf("%lld",g);

        for(re int i=wid(q);i>=;--i) putchar('-');

        putchar('\n');

        for(re int i=wid(g);i>=;--i) putchar(' ');

        printf("%lld",q);

    }return ;

}

巴特西

P1291 [SHOI2002]百事世界杯之旅（概率）

最新文章

热门文章