結構迷走しながら考察しましたが、何とか解けました。
解説見たらめちゃくちゃ賢い解法が書いてあってビビりましたが、自分の賢くない解法も残します。
解法
である各
について、
と
の間に辺を張った
頂点の無向グラフの連結成分を考える。
まず、すべての連結成分の頂点数がであるならば、解は
になる。(すべての
で
となり、辞書順が常に一致するため。)
そうでないとき、すべての連結成分について、連結成分内の頂点数を並べた配列を作り、次のようなDPを考える。
番目の連結成分までみたとき、
であれば辞書順で
より小さいことがすでに確定しており、
であれば、辞書順で
と等しいような場合の数
つまるところ、桁DPのようなことをする。
ここでを連結成分
内の頂点数とすると、このDPの更新は以下のようになる。(
については後述)
式中のについては、連結成分内で条件通りに数字を並べる場合の数である。
これはある連続する2つの数を見たとき、その部分が増加していて、それ以前は連続する数の1つ目の数と同じ数が並び、それ以後はどんな並び方をしていても良い場合の数とも言える。
例えば、入力を]とすると、すべての
が同じ連結成分に属し、
は以下のような並び方が考えられる。(
は、
から
まで何が並んでいても良い。)
つまり、は、
と求められる。
の合計は
なので、上記式は愚直に計算しても
の時間計算量で求まる。また、連結成分ごとの頂点数を求めるのにはUnionFind木を用いたり、連結リストをたどるようにして求めれば、
かその定数倍とみなせる計算量で求めることが出来る。
そのため、全体としての時間計算量で解を求めることが出来る。
コードは以下の通り。(実装の問題でlogがついたりしてますが、気にしないでください)
