考虑期望转移
\(E_i\)表示抽出\(i\)人的期望抽数
状态转移 \(E_{i+1}=E_i+\Delta E\)
想办法把\(\Delta E\)求出来就行了，比如抽多少次才抽出新的那一个人
ACcode
#include<bits/stdc++.h>
using namespace std;
#define in Read()
#define int unsigned long long
int in{
int i=0,f=1; char ch=0;
while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if(ch=='-') f=-1, ch=getchar();
while('0'<=ch&&ch<='9') i=(i<<1)+(i<<3)+ch-48, ch=getchar();
return i*f;
}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
struct frac{
int a,b;
frac(){a=0, b=1;}
frac(int aa, int bb){a=aa, b=bb;}
friend frac operator + (const frac x, const frac y){
frac res;
res.b=x.b*y.b;
res.a=x.a*y.b+x.b*y.a;
int d=gcd(res.a,res.b);
res.a/=d; res.b/=d;
return res;
}
}e[100];
signed main(){
// freopen("1.in","r",stdin);
int n=in;
e[1]=frac(1,1);
for(int i=1;i<n;++i) e[i+1]=e[i]+frac(n,n-i);
if(e[n].b==1) printf("%lld\n",e[n].a);
else{
int l=e[n].a/e[n].b;
int tmp=l;
while(tmp) printf(" "), tmp/=10;
printf("%lld\n",e[n].a%e[n].b);
printf("%lld",l);
tmp=e[n].b;
while(tmp) printf("-"), tmp/=10;
puts("");
tmp=l;
while(tmp) printf(" "), tmp/=10;
printf("%lld",e[n].b);
}
return 0;
}