🔺 Garbage Remembering Exam UVA

题目大意：给你N个单词，有两种方法随机排列，一种随机排成一行，另一种随机排成一圈，当两个单词之间的距离在两种排列中都严格小于K时，则这两个单词构成无效单词，问无效单词的期望。

解题思路：首先对于一排单词的每个单词，取出距离它为K的单词，然后把取出的单词放到环形序列的这个单词的两边

如果我们能分别算出1-n的有效概率，那么就等于算出了无效概率

其中 x为当前单词的左右距离为k的单词的个数， 分子是把一排单词中一个单词的有效距离的单词取出来全排列到环形的无效距离内，然后剩余的单词全排列；

考虑到排列与组合数据过大，用  exp（）函数，其中log（N！）=log(N)+log(N-1)+...+log(1);

需要注意  用long double能过。。。

代码如下：

没大弄明白为什么n-1-x < 2*k 的时候不考虑

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 100005
long double temp[N];
int n,k;
double solve()
{
    if(n==1) return 0;//只有一个单词，无效为0
    else if(2*k+1>=n) return n;//如果圈中的一个单词从左边或右边距离都小于K，则该单词无效，所有单词等效
    double ret=0;
    for(int i=1;i<=n;i++)
    {
        int x=min(k,i-1)+min(k,n-i);//一个单词左右k范围内的单词个数
        if(n-1-x-2*k>=0)
        {
            ret+=exp(temp[n-1-x]+temp[n-1-2*k]-temp[n-1]-temp[n-1-x-2*k]);
        }
//        else
//            ret += exp(temp[2*k] - temp[2*k-n+1+x] + temp[x] - temp[n-1]);
    }
    return n-ret;
}
int main()
{
    temp[0]=0;
    for(int i=1;i<N;i++)
        temp[i]=temp[i-1]+log((long double)i);
    int cas=1;
    while(scanf("%d%d",&n,&k))
    {
        if(n==0&&k==0) break;
        printf("Case %d: %.4lf
",cas++,solve());
    }
    return 0;
}