ABC 372 F — Teleporting Takahashi 2

考察

環の辺に沿う移動だけなら、各頂点にいる方法の数は一つ隣へ回るだけである。値を毎回コピーせず、配列を読む位置をずらしてこの移動を表そう。追加辺は少ないので、その寄与だけを個別に足せばよい。ただし、一手分の寄与はすべて移動前の値から求める必要がある。

全辺をたどるDPから、環の部分を取り出す

以後、頂点番号を0始まりに読み替える。追加辺も入力順に 0,…,M−10,\ldots,M-1 と番号を付け直し、始点を xi=Xi+1−1x_i=X_{i+1}-1、終点を yi=Yi+1−1y_i=Y_{i+1}-1 とする。通常辺は v→(v+1) mod Nv\to(v+1)\bmod N である。z mod Nz\bmod N は、負の整数についても 0,…,N−10,\ldots,N-1 の範囲へ戻した余りを表す。

dpt[v]dp_t[v] を、ちょうど tt 回移動して頂点 vv にいる方法の数とする。値は法 P=998244353P=998244353 で持つ。初期状態は dp0[0]=1dp_0[0]=1、他の頂点では0である。次の一手で頂点 vv に来る方法を、最後に使う辺で分けると

dpt+1[v]≡dpt[(v−1) mod N]+∑i: yi=vdpt[xi](modP)dp_{t+1}[v] \equiv dp_t[(v-1)\bmod N] +\sum_{i:\,y_i=v}dp_t[x_i] \pmod P

となる。第一項は通常辺、第二項は追加辺からの寄与である。この式を全頂点で毎手計算すると O(K(N+M))O(K(N+M)) 時間かかる。N,KN,K はともに最大 2×1052\times10^5 なので、毎手の全頂点走査を省きたい。

追加辺は高々50本しかない。第一項だけなら、例えば旧配列 (2,1,3,4)(2,1,3,4) は (4,2,1,3)(4,2,1,3) へ回る。各値の位置が変わるだけなら、配列の中身を動かす代わりに、どの要素を頂点0として読むかを変えられる。

頂点番号と保存配列の添字を分ける

長さ NN の保存配列を aa、添字のずれを表す整数をoffset oo とし、一手の開始時と終了時に次の対応を保つ。

dpt[v]=a[(v−o) mod N]dp_t[v]=a[(v-o)\bmod N]

ここで vv はグラフ上の頂点番号、(v−o) mod N(v-o)\bmod N は実際に値を置く配列添字である。初めは o=0o=0、a[0]=1a[0]=1、残りを0とすればよい。

旧offsetを oo として、新offsetを o′=(o+1) mod No'=(o+1)\bmod N に変える。保存配列を触らなくても、新しい読み方での頂点 vv の値は

a[(v−o′) mod N]=a[((v−1)−o) mod N]=dpt[(v−1) mod N]a[(v-o')\bmod N] =a[((v-1)-o)\bmod N] =dp_t[(v-1)\bmod N]

となる。これは通常辺だけの遷移先の値そのものである。v=0v=0 でも旧頂点 N−1N-1 の値を読むので、環の末尾から先頭への移動も含まれる。頂点の移動方向は番号が増える向きで、読む添字にはoffsetを引く。その規約ではoffsetを1増やす。

追加辺の寄与を足すには、offsetを変える前に全追加辺の旧値を保存しておく。一手は次の三段階になる。

  1. 各辺 ii について、si=a[(xi−o) mod N]=dpt[xi]s_i=a[(x_i-o)\bmod N]=dp_t[x_i] を退避する。まだ配列もoffsetも変更しない。
  2. o←(o+1) mod No\leftarrow(o+1)\bmod N とする。これで配列は通常辺だけによる次の分布を表す。
  3. 各辺 ii について、更新後の添字 (yi−o) mod N(y_i-o)\bmod N の要素に sis_i を加え、法 PP で余りを取る。

4頂点で、読む位置と同時更新を追う

独自の小例として、環 0→1→2→3→00\to1\to2\to3\to0 に追加辺 0→20\to2、1→31\to3 がある場合を見る。元の1始まりの番号なら、追加辺は 1→31\to3、2→42\to4 である。初期状態で退避する値は順に (1,0)(1,0) となる。

表の保存配列は添字順、頂点順の値は頂点 0,1,2,30,1,2,3 の順に並べる。「移動のみ」の行は、最初のoffset変更直後で、まだ追加辺の寄与を足していない状態である。

段階oo保存配列 aa頂点順の値
初期0(1,0,0,0)(1,0,0,0)(1,0,0,0)(1,0,0,0)
移動のみ1(1,0,0,0)(1,0,0,0)(0,1,0,0)(0,1,0,0)
1手後1(1,1,0,0)(1,1,0,0)(0,1,1,0)(0,1,1,0)
2手後2(1,2,0,0)(1,2,0,0)(0,0,1,2)(0,0,1,2)
3手後3(1,2,0,0)(1,2,0,0)(2,0,0,1)(2,0,0,1)
4手後0(1,2,2,0)(1,2,2,0)(1,2,2,0)(1,2,2,0)

最初のoffset変更後、追加辺 0→20\to2 の保存先は a[(2−1) mod 4]=a[1]a[(2-1)\bmod4]=a[1] であり、退避した1を足す。追加辺 1→31\to3 の寄与は退避した0なので、加算後の分布は (0,1,1,0)(0,1,1,0) になる。3手目では旧頂点3の値2が頂点0へ回り、4手目ではoffset自身も0へ戻る。

なぜ全辺分を先に保存するのか。最初の一手で、0→20\to2 の加算後に次の辺の旧値を読もうとすると、旧offsetを別に覚えて読んでも頂点1の保存先は a[1]a[1] である。そこはすでに0から1へ変わっている。この1を 1→31\to3 の寄与として足すと、誤った分布 (0,1,1,1)(0,1,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

終点は指定されていないので、KK 手後の全頂点の値を足す。頂点番号と配列添字の対応は並べ替えにすぎず、保存配列全体の和がそのまま答えになる。追加辺がない場合は毎手の行き先が一つなので、歩数によらず答えは1である。

公式解説も、通常遷移でほとんど変わらない配列を再利用する方針である。公式の実装例は長さ N+KN+K の線形配列で読み始める位置を毎手左へずらし、環の境界の値をコピーする。本稿では同じ遷移を、長さ NN の循環配列と上の添字対応で表した。

典型の発動条件

inline DP

全状態に共通する移動が添字の並べ替えで、通常の遷移と異なる寄与が少数なら、配列の読み方を変えて共通部分を処理できる。必要な場所だけを書き換えて配列を再利用するDPを、公式解説ではinline DPと呼んでいる。

使う前に「元の状態をどの保存要素から読むか」を式で定め、その対応を共通移動後も定数時間で更新できるかを確かめる。さらに例外の更新が旧値を壊すなら、必要な旧値だけを退避する。配列全体の複製を避けることと、旧値の保存を省くことは別である。

問題固有の要素

通常辺が全頂点を一周する環なので、共通移動を一つのoffsetだけで表せる。単に「辺が少ない」だけでなく、NN 本の規則的な辺と高々50本の追加辺に分かれている点が鍵になる。遷移前後のDPを頂点順に並べ、一方を一つずらして見ると、追加辺の行き先以外は同じ値を再利用できることが見える。

正当性

一手の開始時に dpt[v]=a[(v−o) mod N]dp_t[v]=a[(v-o)\bmod N] が全頂点で成り立つとする。初期化はこの対応を満たす。全追加辺について退避した sis_i は、まだ書き換えていない配列から取得するため、必ず dpt[xi]dp_t[x_i] である。

offsetを1増やした直後の頂点 vv の値は、旧頂点 (v−1) mod N(v-1)\bmod N の値に等しい。そこへ、終点が vv の追加辺それぞれの sis_i を足すと、考察で定めた漸化式の右辺になる。退避値は加算中に変わらず、すべての頂点で同じ時刻の値から遷移できる。

各移動方法は、最後に使った通常辺または追加辺と、その直前までの移動方法に一意に分かれる。辺はすべて異なるため、上の和には漏れも重複もない。従って一手終了時には同じ添字対応で dpt+1dp_{t+1} が表され、これを繰り返せば KK 手後も正しい。終点ごとの方法は互いに重ならないので、全保存要素の和が求める答えになる。法を取る操作は加算と両立するため、以上は法 PP でも成立する。

実装上の注意

  • C++などで負数の % が負になり得る場合、頂点 vv の保存先は (v - o + N) % N とする。0≤v,o<N0\leq v,o<N なので、NN を一度足せば非負になる。追加辺の始点には旧offset、終点には新offsetを使う。
  • 複数の追加辺が同じ始点を持っても、移動先が違えば別の方法である。同じ終点へ来る辺の寄与も、すべて加算する。退避配列には辺ごとに値を持てばよい。
  • 毎回の加算後に法 PP を取り、保存値を 0,…,P−10,\ldots,P-1 に保つ。二値の和は 2(P−1)<2312(P-1)<2^{31} なので符号付き32 bit整数にも収まるが、最後の和をまとめて計算するなら最大 N(P−1)<2×1014N(P-1)<2\times10^{14} となるため64 bit整数を使う。擬似コードは最後の和も一項ごとに法を取っている。
  • 到達不能な頂点の値は0のまま扱う。K=1K=1 でも同じ三段階でよく、N=2N=2 では自己辺と通常辺以外の辺が存在しないため、公式条件の下では M=0M=0 となる。

復習の核

  • 全状態を毎手書き換えているなら、その大半が同じ添字移動でないかを調べる。
  • offsetの符号は暗記せず、頂点 vv の値をどこから読むかを定義し、次の一手の式を導く。
  • 配列を再利用するときは、同じ保存要素が旧状態と新状態で別の頂点を表す。例外の寄与は全件を旧値から保存してから書き込む。

計算量と制約

時間

初期化と最後の総和に O(N)O(N)、一手で全追加辺の退避と加算に O(M)O(M)、offsetの変更に O(1)O(1) かかる。反復をそのまま行う場合の全体は厳密には O(N+K(M+1))O(N+K(M+1)) 時間である。上の擬似コードでは M=0M=0 なら答え1を即座に返すため、この場合の反復は不要となり、全体を O(N+KM)O(N+KM) 時間と評価できる。入力の O(M)O(M) も、K≥1K\geq1 なのでこの評価に含まれる。

空間

保存配列に O(N)O(N)、追加辺と退避配列に O(M)O(M) を使い、合計 O(N+M)O(N+M)。過去の全時刻のDPは保存しない。公式実装例の線形配列を用いる場合は O(N+K+M)O(N+K+M) 空間となる。

制約との対応

2≤N≤2×1052\leq N\leq2\times10^5、0≤M≤500\leq M\leq50、1≤K≤2×1051\leq K\leq2\times10^5。従って追加辺の処理量を決める KMKM は高々 10710^7 であり、毎手 NN 頂点を走査する費用を除くことで制約に対応できる。1≤Xi,Yi≤N1\leq X_i,Y_i\leq N、Xi≠YiX_i\ne Y_i で、通常辺を含む全辺が異なる。後者は辺による数え上げと、頂点列で区別される移動方法の数が一致するために使う。答えは法 998244353998244353 で求める。公式の実行時間制限は3秒、メモリ制限は1024 MiBである。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Teleporting Takahashi 2 の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: DP遷移を因数分解・集約して加速する

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: DP遷移の集約・高速化

      執筆: abc-explanation-author1.1.1 / revision 2

      学習の位置

      体系上の位置: DP遷移を因数分解・集約して加速する

      • 全状態に共通する添字移動・倍率・affine作用を外出しし、旧値の保存と非可逆な作用を扱って例外だけを更新できる。

      先に読む単元:

      この解説で扱わないこと:

      • 固定線形遷移の巨大回累乗。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題