洛谷P1291 [SHOI2002]百事世界杯之旅——期望DP

题目：https://www.luogu.org/problemnew/show/P1291

水水的经典期望DP；

输出有毒。(其实也很简单啦)

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
ll n,fz[35],fm[35],s1,s2,ans,w,w2;
//double f[35];
ll gcd(ll x,ll y){return x%y?gcd(y,x%y):y;}
ll getlen(ll x)
{
    ll ret=0;
    while(x){ret++; x/=10;}
    return ret;
}
int main()
{
    scanf("%lld",&n);
    fz[n]=0; fm[n]=1;
    for(ll i=n-1;i>=0;i--)
    {
        ll tfm=(n-i)*fm[i+1];
        ll tfz=(n-i)*fz[i+1] + n*fm[i+1];
        ll k=gcd(tfz,tfm);
        fz[i]=tfz/k; fm[i]=tfm/k;
    }
//    for(ll i=n-1;i>=0;i--)
//        f[i]=f[i+1]+n/(n-i);
//    printf("%lf",f[0]);
    s1=fz[0],s2=fm[0];
    if(s2==1)
    {
        printf("%lld",s1); return 0;
    }
    ans=s1/s2,s1%=s2;
    w=getlen(s2);
    if(ans)w2=getlen(ans);
    if(!s1)
    {
        printf("%lld",ans); return 0;
    }
    if(ans) 
//        while(w2--) printf(" ");//把 w2 减掉了！！！
        for(int i=1;i<=w2;i++) printf(" "); 
    printf("%lld
",s1);
    if(ans)printf("%lld",ans);
    while(w--)printf("-"); printf("
");
    if(ans) while(w2--) printf(" ");
    printf("%lld",s2);
    return 0;
}