ABC 433 F — 1122 Subsequence 2

考察

1122部分列の中央左側の文字を位置 i の数字 S_i に固定する。左側で同じ数字を選べる個数を p、右側で S_i+1 を選べる個数を q とすると、長さ 2k の候補数は binom(p,k-1)binom(q,k) である。

採用する候補: 各 i を中央位置として寄与を一意に数え、Vandermonde の畳み込みで長さ k の和を binom(p+q,p+1) に閉じる。

p,q は prefix/suffix 頻度で O(1)、二項係数も前計算できるため全体 O(N) になる。

棄却する候補: 全ての部分列を列挙し、前半同値・後半が+1かを調べる。

部分列は 2^N 個存在する。

各非空 1122 部分列は前半最後、すなわち |T|/2 文字目の元位置 i をちょうど一つ持つため、i ごとの和に重複がない。

Σ_{k≥1}binom(p,k-1)binom(q,k)=binom(p+q,p+1) は Vandermonde の畳み込みである。

各数字の prefix count または左右総数を用意する。i を左から走査し、p=左側の S_i 個数、q=右側の S_i+1 個数を求め、fact/invfact で binom(p+q,p+1) を答えへ足す。

典型の発動条件

代表位置による部分列分割

発動条件: 各対象部分列に中央・最初・最後など一意な代表添字を割り当てられるとき。

1122部分列を前半最後の位置 i で分類し、左右の選択を独立にする。

Vandermonde の畳み込み

発動条件: Σ_k binom(p,k+a)binom(q,k+b) のように選択数 k を全て足すとき。

長さ別の積和を一つの二項係数 binom(p+q,p+1) へ簡約する。

左右頻度の累積管理

発動条件: 各位置に対して左の同値個数と右の別値個数が必要なとき。

prefix count と総頻度から p,q を定数時間で取得する。

問題固有の要素

部分列長を DP 状態に残さず、中央位置固定後の長さ別和を組合せ恒等式で消去できる。

別の問題へ持ち帰る視点: 一意な代表で分割した後に左右選択の積和が出たら、Vandermonde 型へ変形できないか調べる。

正当性

非空1122型列は前半最後の元位置iが一意である。左の同digit p個からk−1、右の次digit q個からkを選ぶ積がそのiの候補数。Vandermondeで全k和をC(p+q,p+1)へ変えるのは同じ選択を二群へ分けた恒等式。全i和は中央左位置の分類で重複なく全列を数える。

実装上の注意

  • p は i 自身を含まない左側、q は i より右側だけを数える。p+1 が範囲外なら二項係数を 0 とする規約を統一する。

復習の核

  • 長さ 2k で左から k 番目が i となる選択数と、閉形式 binom(p+q,p+1) の対応を確認する。

計算量と制約

時間

O(|S|)。各digit左右個数と階乗表を更新する。

空間

O(|S|)、左右countは定数10。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: S is a string consisting of digits with length between 1 and 10^6, inclusive.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: 組合せ係数と対称性で数える

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

    主タグ: 組合せ係数・数え上げ

    補助タグ: 寄与の数え上げと順序交換

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

    学習の位置

    体系上の位置: 組合せ係数と対称性で数える

    • 選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。

    先に読む単元:

    • 局所寄与へ分解して集計順を交換する — 数える対象を一意に固定し、その対象を含む選択や組の個数へ集計順を交換する。要素・組・区間・値のどれを固定すると重複が消えるかを比較する。

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

    • 重なりを交互加減する包除・Möbius反転。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題