NECプログラミングコンテスト2022 (AtCoder Beginner Contest 267) G - Increasing K Times (600)
$ dp[i][j] で$ iまでの数で増加するような並びが$ j個の場合の数とする
それまでに使った数が$ sumで増加するような並びが$ l個あるときに今見ている数によって$ m個そのような並びを増やす場合を考える
$ m個については$ sumの中の増加列になっていないそれぞれ別の要素の後ろに置けばどこにおいても良い
$ _{sum-l}C_{m}
今見ている数の残りは増加列を新たに作らないようにするために既に増加列の所に置くまたは上で置いた場所必要がある
$ _{cs_i+l}C_{m}
最後に同じ数の並べ方を全列挙するために階乗をかける
$ cs_i!
階乗や組み合わせの数は事前に求めておく
遷移が$ \mathcal{O}(N^3) の様だが$ dp[*][j] を求めるときの遷移元が$ \mathcal{O}(N)なので遷移は全体で$ \mathcal{O}(N^2)