考察
環の辺に沿う移動だけなら、各頂点にいる方法の数は一つ隣へ回るだけである。値を毎回コピーせず、配列を読む位置をずらしてこの移動を表そう。追加辺は少ないので、その寄与だけを個別に足せばよい。ただし、一手分の寄与はすべて移動前の値から求める必要がある。
全辺をたどるDPから、環の部分を取り出す
以後、頂点番号を0始まりに読み替える。追加辺も入力順に と番号を付け直し、始点を
、終点を とする。通常辺は
である。 は、負の整数についても の範囲へ戻した余りを表す。
を、ちょうど 回移動して頂点 にいる方法の数とする。値は法
で持つ。初期状態は 、他の頂点では0である。次の一手で頂点
に来る方法を、最後に使う辺で分けると
となる。第一項は通常辺、第二項は追加辺からの寄与である。この式を全頂点で毎手計算すると
時間かかる。 はともに最大 なので、毎手の全頂点走査を省きたい。
追加辺は高々50本しかない。第一項だけなら、例えば旧配列 は
へ回る。各値の位置が変わるだけなら、配列の中身を動かす代わりに、どの要素を頂点0として読むかを変えられる。
頂点番号と保存配列の添字を分ける
長さ の保存配列を 、添字のずれを表す整数をoffset
とし、一手の開始時と終了時に次の対応を保つ。
ここで はグラフ上の頂点番号、 は実際に値を置く配列添字である。初めは
、、残りを0とすればよい。
旧offsetを として、新offsetを
に変える。保存配列を触らなくても、新しい読み方での頂点 の値は
となる。これは通常辺だけの遷移先の値そのものである。 でも旧頂点
の値を読むので、環の末尾から先頭への移動も含まれる。頂点の移動方向は番号が増える向きで、読む添字にはoffsetを引く。その規約ではoffsetを1増やす。
追加辺の寄与を足すには、offsetを変える前に全追加辺の旧値を保存しておく。一手は次の三段階になる。
- 各辺 について、
を退避する。まだ配列もoffsetも変更しない。
- とする。これで配列は通常辺だけによる次の分布を表す。
- 各辺 について、更新後の添字 の要素に を加え、法
で余りを取る。
4頂点で、読む位置と同時更新を追う
独自の小例として、環 に追加辺 、
がある場合を見る。元の1始まりの番号なら、追加辺は 、
である。初期状態で退避する値は順に となる。
表の保存配列は添字順、頂点順の値は頂点 の順に並べる。「移動のみ」の行は、最初のoffset変更直後で、まだ追加辺の寄与を足していない状態である。
最初のoffset変更後、追加辺 の保存先は
であり、退避した1を足す。追加辺 の寄与は退避した0なので、加算後の分布は
になる。3手目では旧頂点3の値2が頂点0へ回り、4手目ではoffset自身も0へ戻る。
なぜ全辺分を先に保存するのか。最初の一手で、
の加算後に次の辺の旧値を読もうとすると、旧offsetを別に覚えて読んでも頂点1の保存先は
である。そこはすでに0から1へ変わっている。この1を の寄与として足すと、誤った分布
になる。移動前には頂点1にいなかった方法を使ってしまう。offsetを変えた後で新しい頂点番号の読み方を使っても、旧値は取得できない。読み出しをすべて終えてから、読み方の変更と書き込みに進むことが必要である。
初期化から答えまで
全手順を、非実行の擬似コードでまとめる。x[i]、y[i] は0始まりへ変換済みとし、mod(z, N)
は非負の余りを返すものとする。
P = 998244353
if M == 0:
output 1
finish
a = 長さ N のゼロ配列
a[0] = 1
o = 0
s = 長さ M の退避配列
K 回繰り返す:
for i = 0, ..., M-1:
s[i] = a[mod(x[i] - o, N)]
o = (o + 1) % N
for i = 0, ..., M-1:
j = mod(y[i] - o, N)
a[j] = (a[j] + s[i]) % P
answer = 0
for j = 0, ..., N-1:
answer = (answer + a[j]) % P
output answer
終点は指定されていないので、
手後の全頂点の値を足す。頂点番号と配列添字の対応は並べ替えにすぎず、保存配列全体の和がそのまま答えになる。追加辺がない場合は毎手の行き先が一つなので、歩数によらず答えは1である。
公式解説も、通常遷移でほとんど変わらない配列を再利用する方針である。公式の実装例は長さ
の線形配列で読み始める位置を毎手左へずらし、環の境界の値をコピーする。本稿では同じ遷移を、長さ
の循環配列と上の添字対応で表した。
典型の発動条件
inline DP
全状態に共通する移動が添字の並べ替えで、通常の遷移と異なる寄与が少数なら、配列の読み方を変えて共通部分を処理できる。必要な場所だけを書き換えて配列を再利用するDPを、公式解説ではinline
DPと呼んでいる。
使う前に「元の状態をどの保存要素から読むか」を式で定め、その対応を共通移動後も定数時間で更新できるかを確かめる。さらに例外の更新が旧値を壊すなら、必要な旧値だけを退避する。配列全体の複製を避けることと、旧値の保存を省くことは別である。
問題固有の要素
通常辺が全頂点を一周する環なので、共通移動を一つのoffsetだけで表せる。単に「辺が少ない」だけでなく、
本の規則的な辺と高々50本の追加辺に分かれている点が鍵になる。遷移前後のDPを頂点順に並べ、一方を一つずらして見ると、追加辺の行き先以外は同じ値を再利用できることが見える。
正当性
一手の開始時に
が全頂点で成り立つとする。初期化はこの対応を満たす。全追加辺について退避した
は、まだ書き換えていない配列から取得するため、必ず である。
offsetを1増やした直後の頂点 の値は、旧頂点 の値に等しい。そこへ、終点が
の追加辺それぞれの
を足すと、考察で定めた漸化式の右辺になる。退避値は加算中に変わらず、すべての頂点で同じ時刻の値から遷移できる。
各移動方法は、最後に使った通常辺または追加辺と、その直前までの移動方法に一意に分かれる。辺はすべて異なるため、上の和には漏れも重複もない。従って一手終了時には同じ添字対応で
が表され、これを繰り返せば
手後も正しい。終点ごとの方法は互いに重ならないので、全保存要素の和が求める答えになる。法を取る操作は加算と両立するため、以上は法
でも成立する。
実装上の注意
- C++などで負数の
% が負になり得る場合、頂点 の保存先は (v - o + N) % N
とする。 なので、
を一度足せば非負になる。追加辺の始点には旧offset、終点には新offsetを使う。
- 複数の追加辺が同じ始点を持っても、移動先が違えば別の方法である。同じ終点へ来る辺の寄与も、すべて加算する。退避配列には辺ごとに値を持てばよい。
- 毎回の加算後に法 を取り、保存値を に保つ。二値の和は
なので符号付き32 bit整数にも収まるが、最後の和をまとめて計算するなら最大
となるため64 bit整数を使う。擬似コードは最後の和も一項ごとに法を取っている。
- 到達不能な頂点の値は0のまま扱う。 でも同じ三段階でよく、
では自己辺と通常辺以外の辺が存在しないため、公式条件の下では となる。
復習の核
- 全状態を毎手書き換えているなら、その大半が同じ添字移動でないかを調べる。
- offsetの符号は暗記せず、頂点 の値をどこから読むかを定義し、次の一手の式を導く。
- 配列を再利用するときは、同じ保存要素が旧状態と新状態で別の頂点を表す。例外の寄与は全件を旧値から保存してから書き込む。
計算量と制約
時間
初期化と最後の総和に 、一手で全追加辺の退避と加算に 、offsetの変更に
かかる。反復をそのまま行う場合の全体は厳密には 時間である。上の擬似コードでは
なら答え1を即座に返すため、この場合の反復は不要となり、全体を
時間と評価できる。入力の も、 なのでこの評価に含まれる。
空間
保存配列に 、追加辺と退避配列に を使い、合計
。過去の全時刻のDPは保存しない。公式実装例の線形配列を用いる場合は
空間となる。
制約との対応
、、。従って追加辺の処理量を決める
は高々 であり、毎手
頂点を走査する費用を除くことで制約に対応できる。、
で、通常辺を含む全辺が異なる。後者は辺による数え上げと、頂点列で区別される移動方法の数が一致するために使う。答えは法
で求める。公式の実行時間制限は3秒、メモリ制限は1024 MiBである。
出典