题目链接：uva 11637 - Garbage Remembering Exam

题目大意：大白数里有很详细的题意。

解题思路：对于有序的序列来说，考虑每个位置为有效性的概率。C(2?kn?1?x)?A(2k2k)?A(n?1?xn?1?x)A(n?1n?1)
x为考虑当前位置，然后与该位置距离小于等于k的位置个数。该位置有效的话，则对应的要将原先邻近的2*k个单词放到另外的位置上。

#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; const int maxn = 1e5; int N, K; long double frc[maxn+5]; double solve () { if (N == 1) return 0; if (N - 2 * K - 1 <= 0) return N; double ret = 0; for (int i = 1; i <= N; i++) { int x = min(K, i - 1) + min(K, N - i); if (N >= x + 2 * K + 1) ret += exp(frc[N-1-2*K] + frc[N-1-x] - frc[N-1] - frc[N - 1 - x - 2 * K]); } return N - ret; } int main () { int cas = 1; frc[0] = 0; for (int i = 1; i <= maxn; i++) frc[i] = frc[i-1] + log((long double)i); while (scanf("%d%d", &N, &K) == 2 && N + K) { printf("Case %d: %.4lf\n", cas++, solve()); } return 0; }