まずは、「中央値の中央値」が \(k\) に固定された場合について解く方法を考えます。

中央値が \(k\) 未満のグループをA、

中央値が \(k\) のグループB、

中央値が \(k\) より大きいグループC、と呼ぶことにします。

Aが \(\frac{N-1}{2}\) 個、Bが \(1\) 個、Cが \(\frac{N-1}{2}\) 個、となる分割の総数が求めたいものです。

以下の \(2\) つの区別をして、最後に重複を取り除くことにします。

1. Aグループ間、Cグループ間の順序を区別する

   • \(A_1,...A_{\frac{N-1}{2}},B_1,C_1,...C_{\frac{N-1}{2}}\) と順序を決めて数える

2. グループ内の \(k\) より小さい要素間の順序, \(k\) より大きい要素間の順序をそれぞれ区別する

A,B,Cについて以下のように多項式を定めます。(多項式の \(x^n\) の指数 \(n\) は \(k\) より大きい要素の個数を、 係数はそのような状態になるグループの個数を表しています)

• A： \(f_a(x)=(1 + x + \dots + x^{\frac{M-1}{2}})\) ( \(k\) より大きい要素が \(\frac{M-1}{2}\) 個以下、 \(k\) が \(0\) 個となるグループ)

• B： \(f_b(x)=(x^{\frac{M-1}{2}})\)　( \(k\) より大きい要素が \(\frac{M-1}{2}\) 個、 \(k\) が \(1\) 個, \(k\) より小さい要素が \(\frac{M-1}{2}\) 個となるグループ)

• C： \(f_c(x)=(x^{\frac{M-1}{2}+1} + x^{\frac{M-1}{2}+2} + \dots + x^{M})\)　( \(k\) より大きい要素が \(\frac{M-1}{2}+1\) 個以上、 \(k\) が \(0\) 個となるグループ)

「中央値の中央値」が \(k\) となる分割の総数は

\([x^{NM-k}] (f_a(x))^{\frac{N-1}{2}}\cdot f_b(x) \cdot (fc(x))^{\frac{N-1}{2}}\cdot(NM-k)!\cdot(k-1)!\)

です。

次に区別を無くします。

1. Aグループ間、Cグループ間の順序をなくす

   • \(\frac{1}{\left(\frac{N-1}{2}\right)!}\) (Aグループ間の順序をなくす)
   • \(\frac{1}{\left(\frac{N-1}{2}\right)!}\) (Cグループ間の順序をなくす)

2. グループ内の要素(kより小さい要素間、kより大きい要素間)の順序の区別をなくす

先ほどの式から \(f_a(x),f_b(x),f_c(x)\) の係数をそれぞれ以下のようにします

\(f_a(x)=\left(a_0 + a_1x + \dots + a_{\frac{M-1}{2}}x^{\frac{M-1}{2}}\right)\) \(\left( a_i = \frac{1}{i!(M-i)!} \right)\)

\(f_b(x)=\left(\frac{1}{\left(\frac{M-1}{2}\right)!\left(\frac{M-1}{2}\right)!}x^{\frac{M-1}{2}}\right)\)

\(f_c(x)=\left(c_{\frac{M-1}{2}+1}x^{\frac{M-1}{2}+1} + \dots + c_Mx^M\right)\) \(\left( c_i = \frac{1}{i!(M-i)!} \right)\)

分割の総数は

\([x^{NM-k}] (f_a(x))^{\frac{N-1}{2}}\cdot f_b(x) \cdot (f_c(x))^{\frac{N-1}{2}} \cdot (NM-k)! \cdot (k-1)! \cdot \frac{1}{\left(\frac{N-1}{2}\right)!} \cdot \frac{1}{\left(\frac{N-1}{2}\right)!}\)

です。

全ての \(k\) について、

\((f_a(x))^{\frac{N-1}{2}} \cdot f_b(x) \cdot (f_c(x))^{\frac{N-1}{2}}\) を共通して求めることができます。

これは、FFTと繰り返し二乗法を用いることで \(O(NM\log(NM))\) で求めることができます。

全体の計算量も \(O(NM\log(NM))\) です。

クレジット

原案： mono_1729

解法： tatyam, mono_1729, null0124, nu50218

問題準備・解説： akua

レビュー： US_cube

テスター： DEGwer

校正： nu50218