AT_arc174_e [ARC174E] Existence Counting

[problemUrl]: https://atcoder.jp/contests/arc174/tasks/arc174_e 整数 $ N,K $ が与えられます。このとき、以下の条件を全て満たす長さ $ K $ の数列 $ a=(a_1,a_2,\dots,a_K) $ を考えます。 - $ a_i $ は $ 1\ \le\ a_i\ \le\ N $ を満たす整数である - $ a $ の全ての要素は相異なる $ a $ として考えられる数列を辞書順に全て並べた 「数列の列」 を辞書 $ s $ とします。 辞書 $ s $ 中に存在する数列 $ P $ が与えられるので、整数 $ t=1,2,\dots,N $ に対して以下の質問に答えてください。 - 以下の条件を全て満たす数列 $ b $ の個数を $ 998244353 $ で割った余りを求めよ。 - 数列 $ b $ は辞書 $ s $ 中に存在する。 - 数列 $ b $ 中に整数 $ t $ が含まれる。 - 数列 $ b $ は辞書順で数列 $ P $ 以下である。 数列の辞書順とは？ 数列 $ A\ =\ (A_1,\ \ldots,\ A_{|A|}) $ が $ B\ =\ (B_1,\ \ldots,\ B_{|B|}) $ より**辞書順で真に小さい**とは、下記の 1. と 2. のどちらかが成り立つことを言います。 1. $ |A|\ かつ\ (A_{1},\ldots,A_{|A|})\ =\ (B_1,\ldots,B_{|A|}) $ である。 2. ある整数 $ 1\leq\ i\leq\ \min\{|A|,|B|\} $ が存在して、下記の $ 2 $ つがともに成り立つ。 - $ (A_{1},\ldots,A_{i-1})\ =\ (B_1,\ldots,B_{i-1}) $ - $ A_i $

N/A

N/A

### 制約 - 入力は全て整数 - $ 1\ \le\ K\ \le\ N\ \le\ 3\ \times\ 10^5 $ - $ P $ は問題文中の条件を満たす。 ### Sample Explanation 1 この入力では、 $ N=4,K=2 $ です。 このとき、辞書 $ s=((1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3)) $ となります。 辞書 $ s $ に含まれ、かつ辞書順で $ (3,2) $ 以下である数列のうち、 - $ 1 $ が含まれるものは $ (1,2),(1,3),(1,4),(2,1),(3,1) $ の $ 5 $ 個 - $ 2 $ が含まれるものは $ (1,2),(2,1),(2,3),(2,4),(3,2) $ の $ 5 $ 個 - $ 3 $ が含まれるものは $ (1,3),(2,3),(3,1),(3,2) $ の $ 4 $ 個 - $ 4 $ が含まれるものは $ (1,4),(2,4) $ の $ 2 $ 個 です。