drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AOJ AUPC DP in-place DP 数え上げ問題 操作列を数え上げる問題 操作 数列 座標圧縮 シーケンシャルDP 制約:複数系列の長さの合計が10^5以下 データ構造 BIT DP高速化 DP高速化:セグメント木 in-place な DP にもっと慣れていきたい 問題へのリンク 問題概要 個の数列がある。 個目の数列は 個の要素からなる。 個目の数列の 番目の要素は と表す。 個目の数列から 1 個以下の要素を選び、選んだ要素を元の数列の順番通りに並べた数列を とする。 数列 が狭義単調増加となるように選ぶ方法は何通りあるか、1000000007 で割ったあまりを求めよ (数列が等しくても選び方が異なれば異なるものとする)。 制約 考えたこと とりあえず、登場する数値は高々 種類しかないようなので、座圧する。そのときの登場しうる数値の種類数を と表すことにする。 さて、この問題を見たとき、次のような … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2020%2F09%2F19%2F210200" title="AOJ 3196 Increasing Sequence (AUPC 2020 day1-D) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1516148889515660 Hatena Blog https://hatena.blog 2020-09-19 21:02:00 rich https://drken1215.hatenablog.com/entry/2020/09/19/210200 1.0 100%