loop|loop.in|loop.out
题目描述：
有N个点。
现在重复这样的操作：
随机找一个出度为0的点p1，随机找一个入度为0的点p2，连一条有向边从p1指向p2。直到没有出度为0的点。
统计最终状态这个图中的环的期望个数。
为了保证答案精度，提供另外一个参数W（正整数），请你输出小于你的答案乘上W后的最大整数。
输入格式：
一行两个整数N，W。
输出格式：
一行一个整数（保证不超过10^6）。
样例输入（多组，测试数据中只有一组）：
1
100
2
100
样例输出：
99
149
数据范围：
30%
N<=100
70%
N<=5*10^6
100%
N<=10^18
这道题思路很经典，一个闭环等同于消失，一条链等同于一个点，最后期望值为：f(n)=1/1+1/2+1/3+...+1/n
f(n)为发散的，然而f(n)-ln(n)为收敛的，极值为欧拉常数0.57721566490153286060651209。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long double real;
#define PROB "loop"
#define eps 1e-30
#define lim 0.577215
real ans=;
int main()
{
freopen(PROB".in","r",stdin);
// freopen(PROB".out","w",stdout);
int i,j,k,x,y,z,w;
long long n;
scanf("%lld%d",&n,&w);
if (n<=)
{
for (i=;i<=n;i++)
{
ans+=(real)1.0/i;
}
}else
{
ans=log(n)+lim;
}
int ans2;
// real ans3=log(n)+lim;
ans2=ceil(ans*w);
printf("%d",ans2-);
}