対称性より \(P_i=i\) と固定して考えます。また、場合の数を考えるのではなく \(Q\) を \(N!\) 通りの中から一様ランダムに \(1\) つ選んだ時の \(f(P,Q)\) の期待値を計算し、最後に \(P_i=i\) と固定した分も合わせて \(N!^2\) 倍することで答えを計算することを考えます。

まず、\(P_i \le K\) または \(Q_i \le K\) を満たす人はどちらの選抜方法でも必ず通過します。この通過する人数は \(P_i\le K\) と \(Q_i\le K\) を両方満たす人数を \(r\) として \(2K-r\) 人です。

残り \(N-2K+r\) 人のうち、選抜方法①ではコンテスト B で成績の良い \(r\) 人を、選抜方法②ではコンテスト A で成績の良い \(r\) 人を選びます。

選抜方法①で選ばれたある人が選抜方法②では選ばれない確率は \(\displaystyle \frac{N-2K}{N-2K+r}\) なので、期待値の線形性より選抜方法①で選ばれ選抜方法②では選ばれない人数の期待値は \(\displaystyle \frac{r(N-2K)}{N-2K+r}\) です。

\(P_i\le K\) と \(Q_i\le K\) を両方満たす人数がちょうど \(r\) となる確率は \(\displaystyle \frac{\binom Kr\binom{N-K}{K-r}}{\binom NK}\) なので、求める値は \(\displaystyle N!^2\sum_{r=0}^K\frac{r(N-2K)}{N-2K+r}\frac{\binom Kr\binom{N-K}{K-r}}{\binom NK}\) となります。この値は二項係数・逆元の前計算を事前に行うことで \(O(N)\) 時間で計算することができます。

以上を適切に実装することでこの問題に正答することができます。計算量はテストケース毎に \(O(N)\) です。