公式解説とは違う解法です（たぶん）。
解法
あり得る全ての場合に対するLISの長さを合計して、全事象数 で割ることにします。
取っ掛かりが非常に掴みにくい問題ですが、 という制約から何らかの全探索をやることを目指してみます。
座標圧縮とゾーン分け
座標圧縮をします。数列 に含まれる値の種類数を
として、
に
を加えてソート・重複排除した数列を
（
）と置きます。するといずれかの
が取り得る正整数の範囲は、
,
,
という半開区間で表される
個のゾーンに分けることができます。それぞれの
は最大値
の値に応じて、このゾーンのうち前からいくつかに属することになります。
まず、 がそれぞれどのゾーンに属するかを全探索します。これは
通りの全探索をすれば良いです。このとき
がそのゾーンに属することができない（
が区間の下端以下である）ような
がある場合、そのパターンは無視します。
ゾーン内部の大小関係
その上で各ゾーンについて、その内部での大小関係を全探索します。このとき複数の要素が同じ値を取り得る場合があるので、それも含めて全探索する必要があります。
ゾーンに含まれる要素の数が であるとき、数列
の大小関係の列挙は、
長さ の非負数列で、その最大値が
であるときに
が全て含まれているもの
として列挙できます。この数列の個数が公式解説に書かれている Ordered Bell Numberです。例えば であって非負数列が
であれば、大小関係は
です。
この数列を予め要素数 のそれぞれについて列挙しておくと、ゾーン分けを固定した後にそれぞれのゾーン内の大小関係を全探索できます。
場合の数とLISの長さ計算
ゾーン分けとゾーン内部の大小関係を全探索したら、そのパターンに該当する場合の数とLISの長さを計算して合計します。
場合の数は、各ゾーンで使う整数の選び方を計算した積になります。 番目（0始まり）のゾーンに含まれる整数は
個であり、その中で
種類の整数を使う場合、その選び方は
通りです。
LISの長さは、ゾーン分けとゾーン内部の大小関係に応じて と大小関係が等しい数列を適当に作り、そのLISを求めれば良いです。例えば小さい方から
番目のゾーンで小さい方から
番目の値を
とすれば
と大小関係が等しくなります。
計算量の評価は難しいですが、 で
が全て異なる入力ケースにおいてパターン数を実際に計算すると
通りでした。なのでこの中で毎回LISのアルゴリズムを回しても問題ないでしょう。
ACコード
Submission #17196593 - AtCoder Regular Contest 104
実装はなかなかの筋肉系です。