AiScReam

2 secs 1024 MB

制約から、数列の条件は各 $i$ について $b_i$ から $a_i$ に有向辺を張ったDAGに帰着させることができます。よって、この問題は与えられたDAGのトポロジカルソートの個数を求めることと等しいです。

トポロジカルソートの個数は、bitDPを用いることで $O(2^N \times N)$ で計算することができます。制約より、実行時間制限に間に合います。