/* * Game show elimination by Tomas Rokicki. */ #include #include #include #include using namespace std ; using ll = long long ; const int MAXK = 15 ; // overlap present issec double succ[MAXK][1LL<<(MAXK-1)][MAXK+1] ; double v[2][MAXK][1LL<<(MAXK-1)] ; int main(int argc, char *argv[]) { ll n, k ; cout << setprecision(15) ; cin >> n >> k ; vector xsum(n) ; int rd=0, wr=1 ; v[rd][k-1][(1LL<<(k-1))-1] = 1 ; for (int i=0; i>(k-1)) == 0; j++) succ[i][j][0] = -1 ; // mark uncomputed if (k == 1) xsum[0] = n-1 ; ll bmask = (1LL << (k - 1)) - 1 ; for (int i=0; i+1>(k-1)) == 0; rbits++) { double p = v[rd][o][rbits] ; if (p == 0) continue ; ll off = 2 + __builtin_popcountll(rbits) + o - 2 * k + i ; off = max(off, 0LL) ; ll bits = rbits ; ll first = 0 ; ll sec = first + k - o ; if (n - off - sec - 1 < 60) bits &= (1LL << (n - off - sec - 1)) - 1 ; ll u = (bits << (sec + 1)) ; ll sv = u + (1LL << sec) + 1 ; ll conf = sv ; if (succ[o][bits][0] < 0) { succ[o][bits][0] = 0 ; ll mask = 0 ; while (1) { mask = ((mask | ~conf) + 1) & conf ; if (mask == 0) break ; ll cnt = __builtin_popcountll(mask) ; ll lo = sec ; ll hi = sec + k ; ll u = mask ; while (u) { ll b = ffsll(u) - 1 ; lo = max(lo, b) ; hi = min(hi, b + k) ; u -= 1LL << b ; } for (ll t=lo; t> b) & 1)) { // not in conflict group ll spots = min(k, max(0LL, b + k - t - 1)) ; p2 *= spots ; if (b < t && (b == first || first < t)) canlead |= (1LL << b) ; } p2 /= k ; } if (sec - first >= k) canlead = 1LL << first ; p2 /= cnt ; // this case: leader is in conflict group if (cnt > 1) { u = mask ; while (u) { ll b = ffsll(u) - 1 ; succ[o][bits][max(0LL, b + 1 - sec)] += p2 ; u -= 1LL << b ; } } // next case: leader not in conflict group; pick a leader ll u2 = canlead ; while (u2) { ll b2 = ffsll(u2) - 1 ; u2 -= 1LL << b2 ; if ((mask >> b2) & 1) { // chosen leader can't be in conflict continue ; } p2 = 1 ; p2 *= min(k, (t - b2)) ; p2 /= k ; u = conf & ~(1LL << b2) ; while (u) { ll b = ffsll(u) - 1 ; u -= 1LL << b ; if (0 == ((mask >> b) & 1)) { // not in conflict group ll spots = min(k, max(0LL, b + k - t - 1)) ; p2 *= spots ; } p2 /= k ; } p2 /= cnt ; u = mask ; while (u) { ll b = ffsll(u) - 1 ; succ[o][bits][max(0LL, b + 1 - sec)] += p2 ; u -= 1LL << b ; } } } } } ll newbits = 0 ; if (1 || off + sec + k < n) { if (1 || n > off + sec + k + 60) { newbits = -1LL << min(n-off, sec + k) ; } else { newbits = ((1LL << (n - (off + sec + k))) - 1) << (sec + k) ; } } for (ll u=sv; u; ) { ll b = ffsll(u) - 1 ; u -= 1LL << b ; if (b - sec >= k) break ; double p2 = p * succ[o][bits][max(0LL, b + 1 - sec)] ; if (p2 == 0) continue ; ll nv = sv - (1LL << b) + newbits ; ll nfir = ffsll(nv) - 1 ; ll nsec = ffsll(nv - (1LL << nfir)) - 1 ; if (nsec < 0 || nsec + off >= n) { if (sec - first < k) xsum[off + nfir] += (n-1) * p2 ; v[wr][0][bmask] += p2 ; } else { if (nsec - nfir >= k && sec - first < k) xsum[off + nfir] += (n-1) * p2 ; ll over = max(0LL, k - (nsec - nfir)) ; ll bits = nv >> (nsec + 1) ; v[wr][over][bits & bmask] += p2 ; } xsum[b + off] += i * p2 ; } } } swap(rd, wr) ; for (int o=0; o>(k-1)) == 0; bits++) v[wr][o][bits] = 0 ; } for (int i=0; i