考察
禁止条件に触れる位置と値の組を先に選ぶと、残りは使っていない値を自由に並べるだけになる。この数え方を包除原理で組み合わせる。先に選ぶ組では、位置に近い値しか使わないため、使用済みの値を狭い窓に絞って記録できる。
求めるのは、すべての位置 で となる順列 の個数である。 なので全順列の列挙はできない。一方、禁止される値は を満たす近傍だけで、 と小さい。この局所性を利用したい。
禁止する割当てをあえて固定する
包除原理で、禁止条件を満たすように先に値を決める位置の集合を選ぶ。選んだ各位置 には、 を満たす値 を割り当てる。順列なので同じ値を二度使ってはいけない。このように、一部の位置と相異なる値を組にしたものを部分マッチングと呼ぶ。
固定した組数を とする。残る位置は 個、まだ使っていない値も 個なので、埋め方は 通りである。この段階では、残りの位置が禁止条件を満たしてもよい。禁止条件を持つ順列は、最後の包除の符号 で打ち消す。
サイズ の部分マッチング数を とすると、答えは
となる。ここで は包除のために固定した位置数であり、完成した順列で禁止条件を満たす位置の総数ではない。以降は をまとめて計算する。
位置を処理する直前の窓を決める
位置を の順に処理する。位置 に固定できる禁止値の窓を
とする。 は窓の幅である。実在する候補は、この区間と の共通部分だけになる。
窓の使用状況を非負整数 mask の下位 bitで表す。bit番号は最下位を とし、位置 を処理する直前の bit は、値 に対応する。その値を以前の固定で使っていれば 、使っていなければ とする。実在範囲外のbitは常に のままにし、割当て候補から除く。
この時点で窓より小さい値は、以後の禁止値の候補には戻らない。窓より大きい値は、以前の位置に固定できた範囲よりも大きく、まだ使われていない。したがって、今後の値の重複を避けるには窓内の使用状況だけ分かればよい。
dp[t][k][mask] を、位置 の処理を終えて 組を固定し、次の窓 の使用状況が mask である部分マッチング数とする。位置 を処理するときに読む層は dp[i-1] であり、そのmaskが を表す。初期値は dp[0][0][0] = 1、それ以外は とする。まだ何も固定していないので、最初の窓 の全bitが になる。
固定するかを決めてから、窓を一つ進める
dp[i-1][k][mask] の各状態から、次の二種類の遷移を行う。>> 1 は非負整数の右シフト、| はbitごとの論理和、1 << b はbit だけが立った整数を表す。
- 位置 を固定しない。
dp[i][k][mask >> 1] に現在の個数を加える。これは後で自由に埋める位置として残す選択であり、禁止条件を避けた値を今決める操作ではない。
- 位置 に値 を固定する。 bit を調べ、対応する値 が を満たし、かつbit が の場合だけ選べる。
dp[i][k+1][(mask | (1 << b)) >> 1] に現在の個数を加える。
固定する場合は、今の窓で未使用を確認し、そのbitを立ててから右シフトする。二つの操作を逆にすると、同じbit番号が別の値を指してしまう。
右シフトで値 に対応するbitが消え、残りの値のbit番号は一つ小さくなる。次の窓は なので、同じ値への対応が保たれる。新しい右端の値 は位置 まででは固定できず、使用済みである可能性がない。従って、次の最上位bitは とする。この規約では、幅 のmaskを右シフトするだけでそのbitも自動的に になる。
例えば で、位置 の処理直前を考える。窓は であり、bit は順に値 に対応する。以前に値 だけを固定していれば、maskは二進表記で 010 である。表の二進数は左から bit の順に書く。
後者では、先にbit を立てる。シフト後の 011 は値 が使用済み、値 が未使用という意味になる。値 をもう一度固定する遷移は、元のbit が立っているので作らない。
全終端maskを集めて階乗を掛ける
位置 まで処理すると、各 に対して
と求められる。最後のmaskに使用済みの値が残っていても、部分マッチングは完成している。もう禁止値を固定する位置はないので、maskを空にする条件は課さない。例えば で位置 に値 を固定すると、処理後の窓 に値 のbitが残る。この状態も数える必要がある。
窓から消えた使用値を忘れてよいのは、以後の禁止割当てと衝突しないからである。最後の自由な補完でその値を再利用してよいという意味ではない。どの部分マッチングでも、固定済みの 個の値すべてを除いた残りを並べるため、補完数は で決まる。具体的にどの値を使ったかを忘れても、この個数は変わらない。
階乗を から まで前計算し、上の包除の式を計算する。DPと最終集計の加減乗算は、問題で指定された法 で行う。
典型の発動条件
包除原理と部分マッチング
「どの禁止条件も起きない」配置を直接数えにくく、いくつかの条件を満たすよう固定すれば残りが簡単になるときに使う。順列なら、選んだ位置へ相異なる値を割り当てる部分マッチングと、未固定部分の階乗に分離できる。
帯幅が小さい matching DP
二部グラフの辺が、位置と値の差が小さい範囲に限られるときに使う。走査位置に近い値の使用状況だけをbitmaskに残す。情報を捨てる前に、その値が将来の候補に二度と現れないことを確かめる。
問題固有の要素
順列全体の使用済み集合を記録すると 状態になるが、包除のために固定する禁止割当ては対角近傍に限られる。問題文の と の上限の差に注目すると、指数部分を全体サイズから窓幅 へ移せる。
別の問題へ持ち帰る視点: 順列の条件を行列で見たとき、許可・禁止される組がどの範囲に分布するかを調べる。帯状の辺だけを扱う部分問題に分離できれば、境界状態のDPが候補になる。
正当性
位置を処理する直前のmaskが窓内の固定済み使用値を正しく表すと仮定する。位置を固定しない選択と、未使用の実在する禁止値を一つ固定する選択は、その位置で可能な選択を漏れなく重複なく分けている。固定後に左端の値を捨てても、将来の禁止値の下限はそれより大きいため再使用との衝突は起きない。新しい右端は過去に固定できなかった値なので0でよい。空の初期状態からこの不変条件が保たれ、各部分マッチングは固定位置と固定値に沿うただ一つの遷移列で数えられる。
全終端maskを合計すると、サイズ の部分マッチングをそれぞれ一度数える。各部分マッチングに対する補完は、窓外で使った値も含めて固定済みの 個の値を除き、残る 個の値を並べる 通りである。
完成した順列の禁止条件を満たす位置数を とすると、その順列の符号付き寄与は、 個の位置から包除で固定する位置を選ぶ総和になる。係数は なら 、 なら である。従って、禁止条件を一つも持たない順列だけが一度残る。
実装上の注意
- 位置 の遷移は前層
dp[i-1] だけを読み、初めに クリアした次層 dp[i] に加算する。同じ配列内で更新して、一つの位置を複数回固定しない。
- 端では窓が からはみ出す。実在範囲外のbitは でも選べないため、未使用判定と の判定を両方行う。窓を切り詰めてbit番号を詰め直さない。
- では窓は値 一つだけである。固定したbitは直後のシフトで消えるが、 は増える。これにより、固定点のない順列(完全順列)を数える包除になる。
- なら、任意の位置と値の差は 未満なので答えは である。実在範囲外を除く処理により、この場合も同じDPで扱える。
- の空の部分マッチングも含め、 とする。符号は の偶奇で決め、法での減算後は負の値を正規化する。
復習の核
- 包除の式を書いたら、条件の共通部分を数える構造を見る。順列の禁止割当てなら「部分マッチング数 × 残りの階乗」へ分けられる。
- 窓のDPでは「どの位置を処理する直前か」「各bitがどの値か」を先に固定する。今回の規約では、未使用判定・bitを立てる操作・右シフトの順になる。
- 窓外の使用値を忘れられる理由と、最後の自由な補完数を求める理由を区別する。前者は将来の候補範囲、後者は未使用値の個数に依存する。
計算量と制約
時間
。位置が 通り、固定した組数が高々 通り、maskが 通りで、各状態から高々 個の固定候補と未固定遷移を調べる。階乗の前計算は 、最後の全状態の集計は であり、全体評価に含まれる。
空間
。位置の軸について前層と次層の二つだけを保持する。階乗の配列は である。
制約との対応
公式制約は 、、入力は整数。制限時間は2秒、メモリ上限は1024 MiBである。窓幅は最大 、mask数は最大 であり、位置ごとに固定した組数とmaskを走査できる。 となる小さい でも窓幅を変えず、実在する値だけを選ぶ。
出典