Expected Swap Count and Variance in the Card Sorting Game

In this problem, you are given a deck of N cards numbered from \(1\) to \(N\) (all numbers distinct). Before every round the cards are arranged in increasing order. However, after a game the cards become shuffled. The two friends Mo Toutiao ("没头脑", the brainless one) and Bu Gaoxing ("不高兴", the unhappy one) play a card‐game. One day, after they laid the shuffled cards on the table in a row, Bu Gaoxing (who was jealous after losing the previous game) decided to partially sort the cards by arranging only those in odd positions (i.e. positions 1, 3, 5, …) into ascending order (when read from left to right). He then left the remaining task to Mo Toutiao.

Mo Toutiao uses a very simple method: as long as there is an adjacent pair of cards \(X[i]\) and \(X[i+1]\) such that \(X[i] > X[i+1]\), he swaps them (each swap taking 1 unit of time). He repeats this process until the entire sequence is sorted in ascending order. Since each swap fixes exactly one inversion, the total time spent is equal to the number of inversions in the sequence after Bu Gaoxing’s operation.

Your task is to analyze the card‐sorting process in the following three aspects:

1. Assuming Bu Gaoxing always sorts the cards at odd positions (and leaves the cards at even positions untouched), compute the expected number of swaps (i.e. the expected sorting time) that Mo Toutiao will perform, and also compute the variance of the required number of swaps. (Call this Mode 0.)
2. Now suppose that Bu Gaoxing instead sorts some other fixed set of positions (not necessarily the odd positions). In this case, you are only asked to compute the expected number of swaps that Mo Toutiao makes. (Call this Mode 1.)

Note: The entire initial permutation is uniformly random. In Mode 0, the operation is as described above. In Mode 1, assume that when Bu Gaoxing sorts the fixed set of positions, the final card arrangement is obtained by taking the cards originally at those positions, sorting them into ascending order and putting them back into the same positions, while the other cards remain in their original (random) order.

Input Format: The input consists of a single line containing two integers \(N\) and \(M\) where \(N\) is the total number of cards and \(M\) is the mode. If \(M = 0\), then the case corresponds to Mode 0 (odd‐position sorting, output expectation and variance). If \(M = 1\), then the case corresponds to Mode 1 (other fixed positions sorted, output only the expected number of swaps).

Output Format:

• In Mode 0, output two real numbers separated by a space: the expected sorting time and its variance.
• In Mode 1, output a single real number: the expected sorting time.

All answers are to be printed with 6 digits after the decimal point.

Analysis and Hints:

After the initial uniform random permutation of \(\{1,2,\dots,N\}\), Bu Gaoxing sorts the cards at some fixed positions. In Mode 0, these positions are exactly the odd positions. Let

[ m = \lceil N/2 \rceil, \quad k = \lfloor N/2 \rfloor. ]

Then the cards at odd positions become the sorted order of a uniformly chosen \(m\)-subset of \(\{1,2,\dots,N\}\), and the cards at even positions remain in a uniformly random order amongst the remaining \(k\) cards. Mo Toutiao then uses adjacent swaps until the entire sequence is sorted. Since swapping adjacent out‐of‐order cards exactly eliminates one inversion, the total number of swaps equals the number of inversions.

A somewhat lengthy combinatorial analysis can show that in Mode 0 the expected number of swaps is given by

[ E_0 = \frac{k(k-1)}{4} + \frac{m \cdot k}{m+1}, ]

and an (admittedly technical) derivation gives the variance as

[ Var_0 = \frac{k(k-1)(2k+5)}{72} + \frac{m \cdot k}{(m+1)(m+2)} + \frac{1}{18}. ]

In Mode 1, one may show that the expected number of swaps is exactly the expected number of inversions in a uniformly random permutation of \(N\) elements:

[ E_1 = \frac{N(N-1)}{4}. ]

You are to implement these formulas and output the results accordingly.

inputFormat

The input consists of a single line containing two integers \(N\) and \(M\) separated by a space: \(N\) (\(1 \le N \le 10^5\)) is the number of cards and \(M\) is the mode. If \(M = 0\), use Mode 0 (odd‐position sorted) and output expected swaps and variance. If \(M = 1\), use Mode 1 (other fixed positions sorted) and output only the expected swaps.

outputFormat

In Mode 0, output two real numbers (expected swap count and variance) separated by a space, each rounded to 6 digits after the decimal point. In Mode 1, output a single real number (expected swap count) rounded to 6 digits after the decimal point.

sample

3 0

0.666667 0.222222