题链：

题解：

dp，期望

定义dp[i]表示还剩下i个盖子没收集时，期望还需要多少次才能手机完。

初始值：dp[0]=0

显然对于一个状态，我们随机得到一个盖子，有两种可能：

1.得到了曾经没有的盖子，概率为i/N，并转移到dp[i-1]。

2.得到了已经有了的盖子，概率为(N-i)/N，并转移到dp[i]。

所以dp转移式:

dp[i]=(i/n)*dp[i-1]+((N-i)/i)*dp[i]+1(加一表示本次的操作对答案贡献了1的值)

移项:

(i/N)dp[i]=(i/N)dp[i-1]+1

dp[i]=dp[i-1]+(N/i)

然后按上式累加起来就是答案了。

代码：

 

#include
     
      using namespace std;int N;long long getcnt(long long rtm){	int cnt=0;	while(rtm) cnt++,rtm/=10;	return cnt;}long long gcd(long long a,long long b){	while(b^=a^=b^=a%=b);	return a;}int main(){	cin>>N;	long long a=0,b=1;	for(long long i=1,g;i<=N;i++)		g=gcd(b,i),b=b/g*i;	for(long long i=1,g;i<=N;i++)		g=b/i,a+=N*g;	if(a%b==0) cout<