まず、LIS の長さを考える上では座標圧縮のようなものを行った後の状態のみが重要です。\(N\) 個をいくつかのグループに分けた上で順序をつける場合の数は Ordered Bell number / Fubini number などと呼ばれており、\(N = 6\) で \(4683\) 通りあります。

これを固定すると、同じグループ内では \(X\) のminを取っておくと、次のような問題を解けばよいことになります。

• 長さ \(k\) の狭義単調増加列であって \(1 \leq a_i \leq M_i (1 \leq i \leq k)\) を満たすものの個数を求めよ

これは、\(M_i\) たちを座標圧縮しておき dp[\(i\)][\(j\)] := \(i\) 項目まで見て最後が \(j\) 番目の区間に属するような場合の数 とおくと、\(i+1, \cdots, k\) 項目を同じ区間から選ぶ、ただし区間は \(j+1\)以上からしか使えない、というような遷移のみ考えると正しく計算することができ、このパートの時間計算量は \(\mathrm{O}(N^3)\) となります。 (係数は \(\binom{x}{y}\) の形で xが大きいが、yが\(N\) 以下であるので高速に計算できます)