\(Z = N - X - Y\) とします。このとき \(Z\) は \(A\) に含まれる \(3\) の個数を表します。また、\(D_i = (A_i, B_i, C_i)\) とします。

\(1 \le i < j \le N\) を満たす \(i, j\) について、\((i, j)\) の寄与を、\(3\) つの不等式 \(A_i > A_j, B_i > B_j, C_i > C_j\) のうち成り立つものの個数と定義します。このとき本問題は、\((i, j)\) の寄与の合計が \(K\) になるような \(D\) の個数を求める問題と言い換えることができます。

ここで、\((1, 2, 3)\) の順列を以下の \(2\) つのグループに分けます。

• グループ \(P\) : \((1, 2, 3), (2, 3, 1), (3, 1, 2)\)
• グループ \(Q\) : \((1, 3, 2), (2, 1, 3), (3, 2, 1)\)

このとき、次の事実が成り立ちます。

• \(1 \leq i < j \leq N\) を満たす \(i, j\) について、\(D_i\) と \(D_j\) が異なるグループの順列であるならば、\((i, j)\) の寄与は \(1\) である。

\[ \begin{aligned} & (\text{グループ } P \text{ 内の寄与の合計}) \\ &+ (\text{グループ } Q \text{ 内の寄与の合計}) \\ &+ (\text{グループ } P \text{ の順列の個数}) \times (\text{グループ } Q \text{ の順列の個数}) \end{aligned} \]

と表すことができます。

\(dp[x][y][z][k]\) を、\((1, 2, 3)\) が \(x\) 個、\((2, 3, 1)\) が \(y\) 個、\((3, 1, 2)\) が \(z\) 個含まれ、寄与の合計が \(k\) であるような、グループ \(P\) の順列からなる列の個数と定義します。この DP テーブルは \(O(N^5)\) 時間で計算できます。グループ \(Q\) についても同様の DP で計算ができます。

\(D\) に含まれる \((1, 2, 3), (2, 3, 1), (3, 1, 2)\) の個数をそれぞれ \(x, y, z\) とし、グループ \(P\) 内の寄与の合計を \(k\) としたとき、

\[\binom{N}{x + y + z} \times dp[x][y][z][k] \times dp[X - x][Y - y][Z - z][K - k - (x + y + z)(N - x - y - z)]\]

が本問題の答えに寄与します。\(0 \le x \le X, 0 \le y \le Y, 0 \le z \le Z, 0 \le k \le K\) を満たす \(x, y, z, k\) すべてに対して上記の値を足し合わせることで、答えを \(O(N^5)\) 時間で求めることができます。

実装例 (C++)