考察
最後の区間をどこから始めるかで、分割を場合分けする。区間和が禁止値になる切れ目は、そこまでの累積和が同じ値になるものに限られる。そこで、過去の全分割数から、その累積和を持つ切れ目の分割数だけをまとめて引けばよい。
最後の区間で分け、禁止条件を累積和の一致に直す
を「先頭 要素を、和が の区間を含まないように分割する方法の数」とする。 は である。空の先頭部分には何も区間を置かない一通りの方法があるとして、 とする。これは空区間を一つ作るという意味ではなく、最初の区間を付け足すための出発点である。
最後の区間が なら、その前の 要素を分割する方法は 通りある。最後の区間は空でないので、 である。各 で全ての を試せばDPになるが、全体で 時間かかり、 には間に合わない。
元の配列の累積和を
と定める。 は要素を一つも含まない空の先頭部分の和である。最後の区間の和は なので、禁止される切れ目の条件は
となる。従って素朴な遷移を、全候補から禁止分を引く形へ変えられる。
同じ累積和の切れ目をまとめて登録する
の計算直前に、二つの集計値を持つ。
all は、既に確定した先頭部分 の合法な分割数の総和。
bucket[x] は、そのうち「元の配列の先頭 要素の和が 」である切れ目だけを選んだ、合法な分割数の総和。
数式では次の意味になる。
bucket[x] に入れるのは切れ目の個数ではなく、各切れ目までの分割数 の和である。同じ累積和が再び現れても、前の値を上書きせず加算する。キーが未登録なら、その値は0と読む。
禁止される累積和は の一つだけなので、遷移は
となる。初めは空の先頭部分 だけを登録し、all = 1、bucket[0] = 1、他のキーは0とする。この初期登録があることで、最初から最後までを一つの区間にする候補も同じ式に含まれる。
以後は個数を全て法998244353で計算し、 の順に次を行う。
- を求める。
- まだ だけを含む集計から、 を求める。
- 求めた を
all と bucket[B_i] の両方へ加える。
取得を終えてから、新しい状態を登録する。 こうすれば次の計算では がちょうど集計される。最後に出力するのは であり、短い先頭部分の分割数も混ざる all ではない。
負数と同じ累積和の再出現を追う
独自の小例 を見る。累積和は で、同じ値が再び現れる。表の all と禁止分 bucket[B_i-K] は、どちらもその行の登録前の値である。最後の列は登録後の bucket[0] と bucket[1] をこの順に並べる。
では、 からの最後の区間 は和0なので禁止される。一方、 からの最後の区間は なので許可され、分割 が一通り残る。この値1を bucket[0] に足して2にする。
では禁止キーが1なので、 の寄与1を引き、 となる。残る分割は と である。最後の登録で bucket[1] は既存の1に2を足した3となる。同じ累積和の境界が二つあることと、その分割数の総和が3であることは異なる。
でも、引く対象はあくまで過去の同じ累積和を持つ境界である。例えば なら、未登録の bucket[1] は0で、答えは1となる。現在位置を遷移元へ先に含めると 、つまり空の最後の区間が候補に混ざってしまう。空の先頭部分の初期登録と、各非空の先頭部分の計算後の登録を区別する。
また、 は負にもなり、 は単調には増えない。切れ目が添字の連続範囲になるとは限らないため、和の大小で尺取りするのではなく、累積和の値をキーにした連想配列でまとめる。
典型の発動条件
全遷移和から禁止classを除くDP
遷移できる過去状態が多くても、禁止条件が少数のキーとの一致だけで決まるなら、全体和とキー別の和を保つ。禁止状態そのものを一つずつ列挙する必要はない。ただし、ここで引くのは状態の個数ではなく、元の遷移式で足すはずだった重みである。
prefix sum値別集約
区間和が固定値になる条件は、両端の累積和の差が固定値になる条件へ直せる。終端を固定し、始端側のどの情報が遷移の可否を決めるかを調べる。同じ値の過去状態が同じ可否を持つなら、そのDP値の和を共有できる。
問題固有の要素
「和が でない」という許可条件は広いが、禁止条件へ裏返すと累積和の値一つで指定できる。要素が負でもこの等式は変わらない。値の単調性を仮定せず、同じ累積和が何度現れても、その都度分割数を足して保持する。
正当性
先頭 要素の合法な分割は、最後の区間の直前の境界 と、先頭 要素の合法な分割に一意に分かれる。ここで であり、最後の区間の和が でないことは と同値である。従って、この条件を満たす の総和が、漏れや重複のない分割数になる。
最初の all と bucket[0] は だけを含み、計算直前の集計の定義を満たす。各 で全体和からキー の寄与だけを除くと、上の総和が得られる。その後に をキー と全体和へ加えるため、次の計算直前にも集計の定義が保たれる。
従って全ての が正しく、 が求める答えである。 や負の要素、同じ累積和の再出現も、等式による分類と の範囲を変えない。個数の加減算は法を取る操作と両立する。
実装上の注意
- 累積和 とキー は、法を取らず符号付き64 bit整数で持つ。異なる区間和を同一視しないためであり、法998244353を取るのはDPと集計の個数だけである。
bucket[B_i] は代入でなく加算する。未登録キーの取得は0とし、減算後のDP値は法の非負範囲へ戻す。
- 全DP配列や全累積和配列は不要である。現在の累積和、最後に求めたDP値、
all、連想配列を持ち、入力を左から処理できる。
- なら で0、それ以外で1になる。全要素が0で の場合も、各段階で
all と禁止分が等しくなり、答えは0となる。
復習の核
- 区間分割の数え上げは最後の区間で分ける。その前の先頭部分の分割数が、各切れ目の重みになる。
- 遷移の可否が遷移元のキーだけで決まるなら、同じキーのDP値をまとめる。「状態が何個か」と「その状態が何通りを表すか」を区別する。
- 空の先頭部分は一通りとして初期登録する。現在の状態は取得後に登録し、非空区間だけを作る。
- 累積和の差を使う等式は負数でも成り立つが、添字順の単調性は成り立たない。
計算量と制約
時間
各要素につき累積和の更新、禁止キーの取得、現在キーへの加算、全体和の更新を一度ずつ行う。ハッシュ表なら各操作が期待 なので、入力の読み込みを含め期待 時間。平衡二分探索木の連想配列なら、一操作 で全体 時間となる。
空間
連想配列に保持するキーは 個であり、全体で 。入力を配列で保持しても同じ評価で、逐次読み込めば入力配列と全DP・累積和配列は省ける。
制約との対応
、、。全ての境界対を調べる は避ける必要がある。、 なので、累積和とキーは符号付き64 bit整数に収まる。キーの大きさや正負によらず検索できる連想配列を用いる。
出典