Contest20140711 loop 数论

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=0;
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<=100000)
        {
                for (i=1;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-1);
}