A:Little Pony and Permutation

直接暴力搜索，复杂度O（n）

#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
#include<stack>
#include<map>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
#define maxn 110000
int a[maxn];
int vis[maxn];
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++)
        {
            if(vis[i])continue;
            int x=i;
            cout<<"("<<x;
            vis[x]=1;
            x=a[x];
            while(!vis[x])
            {
                vis[x]=1;
                cout<<" "<<x;
                x=a[x];
            }
            cout<<")";
        }
        cout<<endl;
    }
    return 0;
}

我们可以发现，这是一个调和序列。

然后。。。就很那个啥了。。、

#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
#include<stack>
#include<map>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
#define maxn 1100000
double f[maxn];
int main()
{
    int n;
    f[1]=1.0;
    for(int i=2;i<maxn;i++)f[i]=f[i-1]+1.0/i;
    while(~scanf("%d",&n))
    {
        if(n<maxn)printf("%.4lf\n",f[n]);
        else printf("%.4lf\n",log(n)+0.5772156649);
    }
    return 0;
}

dp[i]: 恰好走到i点的概率

dp[i]=dp[i-1]*(1/m)+(dp[i-1]-dp[i-m-1]*(1.0/m))

dp[i-1]*(1/m)代表从i-1这个点走到i点的概率。

(dp[i-1]-dp[i-m-1]*(1.0/m))所有走到i-1的点除了i-m-1点外，其他的点都能走到i，并且走到i-1和走到i的概率相同

如果相邻的两个i之间的dp[i]相差很小，那说明下一个dp[i]的变化也会很小。以后就都是这个定值了。所以直接输出就好。

<pre name="code" class="cpp">#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<string>
#include<math.h>
using namespace std;
#define LL __int64
#define maxn 703000
#define eps 1e-13
#define zero(x) (fabs(x)<eps?0:x)
double dp[maxn];
int main()
{
    int n,m;
    while(~scanf("%d%d",&m,&n))
    {
        dp[0]=1.0;
        dp[1]=1.0/m;
        int i;
        for(i=2;i<=n;i++)
        {
            dp[i]=dp[i-1]+dp[i-1]*1.0/m;
            if(i>m)dp[i]=dp[i]-dp[i-m-1]*1.0/m;
            if((zero(dp[i]-dp[i-1])==0))
            {
                printf("%.5lf\n",dp[i]);
                break;
            }
        }
        if(i>n)printf("%.5lf\n",dp[n]);
    }
    return 0;
}

BestCoder Round #7-A,B,C