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

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

洛谷题目传送门

解题思路

设 f i f_i fi​表示还差 i i i个名字没收集,一直到收集齐的期望次数
f i = i n ( f i − 1 + 1 ) + n − i n ( f i + 1 ) f_i=frac{i}{n}(f_{i-1}+1)+frac{n-i}{n}(f_i+1) fi​=ni​(fi−1​+1)+nn−i​(fi​+1)
n × f i = i × ( f i − 1 + 1 ) + ( n − i ) × ( f i + 1 ) ntimes f_i=itimes (f_{i-1}+1)+(n-i)times (f_i+1) n×fi​=i×(fi−1​+1)+(n−i)×(fi​+1)
n × f i − ( n − i ) × f i = i × ( f i − 1 + 1 ) + ( n − i ) ntimes f_i-(n-i)times f_i=itimes (f_{i-1}+1)+(n-i) n×fi​−(n−i)×fi​=i×(fi−1​+1)+(n−i)
i × f i = i × f i − 1 + i + n − i itimes f_i=itimes f_{i-1}+i+n-i i×fi​=i×fi−1​+i+n−i
f i = f i − 1 + n i f_i=f_{i-1}+frac{n}{i} fi​=fi−1​+in​
线性递推即可，处理分数有点难受

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double db;
struct node
{LL x,y;
}F[20]; 
LL n;
node Node(LL a,LL b)
{node T;T.x=a;T.y=b;return T;
}
LL gcd(LL a,LL b)
{if(b==0) return a;return gcd(b,a%b);
} 
node Add(node a,node b)
{LL x,y;y=a.y/gcd(a.y,b.y)*b.y;x=a.x*(y/a.y)+b.x*(y/b.y);LL d=gcd(x,y);x/=d;y/=d;return Node(x,y);
}
LL get(LL a)
{LL cnt=0;while(a){a/=10;cnt++;	}return cnt;
}
int main()
{
//	freopen("pepsi.in","r",stdin);
//	freopen("pepsi.out","w",stdout);cin>>n;node ans=Node(1,1);for(LL i=2;i<=n;i++)ans=Add(ans,Node(1,i));LL a=ans.x*n,b=ans.y;LL c=gcd(a,b);a/=c;b/=c;if(b==1)printf("%d",a);else{LL d=a/b;a-=d*b;LL e=get(b);LL f=get(d);for(int i=1;i<=f;i++)printf(" ");printf("%lldn%lld",a,d);for(LL i=1;i<=e;i++)printf("-");printf("n");for(int i=1;i<=f;i++)printf(" ");printf("%lld",b);}return 0;
}