考察
次の値を一つ決めると、その直前に置けない値は、近すぎる値を集めた連続区間になる。直前の値ごとに数えた列数の累積和を作れば、全体からこの禁止区間を引くだけで、次の値で終わる列数を求められる。
末尾の値を残して、列を一つ伸ばす
条件が見るのは隣り合う二つの値だけである。途中まで作った列について、次の値を選ぶために必要なのは末尾の値であり、それ以前の並びを覚える必要はない。
を「長さ で、末尾が である条件を満たす列の数」とする。値は問題文と同じく 、長さは である。長さ1ならどの値も一通りなので、全ての について 。以後、個数の加減算は全て法998244353で行う。
長さ の末尾を に固定し、その一つ前の値を とする。 の場合だけ付け足せるので、素朴な遷移は
となる。これを各 で全ての を走査して求めると 時間かかる。状態数は収まっているので、この和をまとめて取れないか考える。
累積和の添字と区間端を対応させる
まず とする。許される直前値は または であり、禁止される値はその間の である。どれも値の軸上で連続している。
長さ の行を固定し、その行の累積和を とする。
は、末尾の値が1以上 以下の列数の和である。元の数列 の累積和ではなく、DPの一行を値の小さい順に足したものであり、長さを進めるたびに作り直す。両端を含む区間 の和は、 のとき となる。
許可範囲のうち、小さい側 の和は 、大きい側 の和は である。端点を切り詰めれば、空区間の和も0になる。従って
と求められる。禁止区間の両端を 、 とすれば、これは全体から禁止分を引く式
と同じである。 では禁止区間が必ず 自身を含むため、 が成り立つ。
小例として を見る。初期行は 、累積和は である。表の の列には許可される値の集合を示し、 は空集合を表す。
では小さい側、 では大きい側の許可範囲が空である。 では両側とも空、つまり全直前値が禁止され、結果が0になる。次の長さでは新しい行 から を作り直す。長さ3の行も となり、全末尾の和は2。実際の列は と である。
差の下限が0の場合と、最後の集計
なら、どの二値も条件を満たし、禁止区間は空である。従って各 へ全体和 を一度だけ渡す。上の二つの許可範囲をそのまま足すと、 が両方に入り二重に数えられる。
例えば なら、左側 と右側 の和は初期行で になるが、正しい候補は1、2、3の三つである。専用の分岐で とすれば、長さ2の答えは9となる。
実装では前の行から を作り、全ての について次の行を計算してから、前・次の配列を交換する。これを の順に繰り返す。長さ1を既に初期化しているので、更新は 回である。最後に末尾の値の指定はないため、答えは となる。
典型の発動条件
累積和付きDP
同じ行の連続区間の和を、多数の次状態から問い合わせるときに使う。まず素朴な遷移式を立て、許可範囲が定数個の区間に分かれることを確かめる。累積和を一度共有すれば、状態数を変えずに一状態当たりの走査を省ける。
補集合遷移
許可集合より禁止集合の方が簡潔なら、全体の寄与から禁止分を引く。本問では禁止区間が長くても、区間和として一度で取得できる。大切なのは例外の個数そのものより、例外全体の寄与を速く求められることである。
問題固有の要素
絶対値差の条件は、次の値を中心とする連続した禁止帯になる。「差が下限以上」を二つの許可範囲へ直す際、下限0では範囲が重なる。まず条件を満たす値の集合を確定し、その後で総和の式にする。
正当性
長さ1では、各末尾の列が一通りずつあり、初期行は正しい。長さ の行が正しいとして、長さ の合法な列を考える。末尾 を取り除くと、直前値 を末尾とする長さ の合法な列が一意に残り、 が成り立つ。逆に、この条件を満たす列へ を付ければ、必ず合法な列になる。
では、許可される は二つの重ならない区間に分かれる。累積和の差は各区間内の を一度ずつ足した値なので、遷移式と一致する。 では全ての が許可され、全体和を一度だけ使えばよい。従って次の行も漏れや重複なく数えられる。
これを繰り返せば長さ の行も正しい。末尾が異なる列は重ならないため、その行の総和が求める答えとなる。加減算の途中で法を取っても、同じ数え上げの余りを得られる。
実装上の注意
- の添字は0から 、末尾の値は1から とする。右側区間の手前までの和は であり、 ではない。範囲外の添字は式のとおり切り詰める。
- 各累積和とDP値を法998244353の非負範囲に保つ。減算結果も正規化し、加算の途中の値には符号付き64 bit整数を使うと扱いやすい。
- 次の行は前の行から作った同じ だけを参照する。次の値を代入するたびに まで更新すると、異なる長さの寄与が混ざる。
- では公式制約から であり、どの長さでも答えは1となる。
復習の核
- 状態数が収まり遷移だけが重いとき、遷移元の集合を値の軸上に描き、区間和にまとめられないか考える。
- 「全体から禁止分を引く」は、禁止候補が多くても、その総和を速く取れれば使える。
- 範囲の分割では、空区間だけでなく重なりも確かめる。 では全体を一度だけ数える。
計算量と制約
時間
初期行の作成は 。長さを一つ伸ばすごとに、累積和の構築と全末尾の更新がそれぞれ かかる。これを 回行い、最後の合計も なので、全体で 時間。
空間
前・次のDP行と累積和に、それぞれ長さ の配列を使い、全体で 。全ての長さのDPを保存する必要はない。
制約との対応
、、 であり、。一方、各状態から全ての値を試すと は最大 となる。累積和によりこの余分な値域の走査を省く。 と、許可範囲が空になる末尾も上の手順に含まれる。
出典