ABC 458 E — Count 123

考察

隣接条件で禁止されるのは、1と3が直接隣り合うことだけである。そこで、いったん2をすべて取り除き、1と3の並び方を決めてから、両者が隣り合う箇所へ2を挟むと考える。先に必要な2を確保すれば、残りの2は自由に配れる。

1・2・3の個数をそれぞれ X1,X2,X3X_1,X_2,X_3 とする。求める列を AA、そこから2を取り除いた列を BB とし、BB の長さを m=X1+X3m=X_1+X_3 とおく。各個数は最大 10610^6 なので、全列の生成や、1・2・3の使用個数をすべて状態に持つDPでは大きすぎる。BB 自体も多数あるが、2を必ず挟む箇所の数が同じなら、2の挿入方法の数は同じになる。この箇所数でまとめて数えたい。

両端を決めて連続区間の個数を数える

BB における、同じ記号が続く極大な区間を連続区間(run)と呼ぶ。1の連続区間の個数を r1r_1、3の連続区間の個数を r3r_3 とする。例えば 1113311 は 111 | 33 | 11 に分かれ、r1=2,r3=1r_1=2,r_3=1 である。

連続区間の記号は1・3・1・3と交互に現れる。したがって、BB の先頭と末尾を固定すれば、r1,r3r_1,r_3 の関係も決まる。異なる記号が隣り合う境界数を hh とおくと、これは連続区間と次の連続区間の間の数なので h=r1+r3−1h=r_1+r_3-1 である。

表では、両端が同じ場合はその端の記号の連続区間数、異なる場合は各記号の連続区間数を ii とする。

BB の先頭・末尾r1r_1r3r_3hh
1・1iii−1i-12i−22i-2
3・3i−1i-1ii2i−22i-2
1・3iiii2i−12i-1
3・1iiii2i−12i-1

1と3はともに1個以上あるので、両端が同じ場合は i≥2i\geq2、異なる場合は i≥1i\geq1 となる。

次に、固定した連続区間数から BB を何通り作れるかを数える。nn 個の同じ記号を kk 個の非空な連続区間へ分ける方法の数を part⁡(n,k)\operatorname{part}(n,k) とする。左から並べた nn 個の間にある n−1n-1 箇所から、区切りを k−1k-1 箇所選ぶため、

part⁡(n,k)=(n−1k−1)\operatorname{part}(n,k)=\binom{n-1}{k-1}

となる。ただし 1≤k≤n1\leq k\leq n を満たさない場合は0とする。両端と各連続区間の長さを決めれば、交互に連結して BB が一意に決まるので、その個数は

part⁡(X1,r1)part⁡(X3,r3)\operatorname{part}(X_1,r_1)\operatorname{part}(X_3,r_3)

である。ここで数える連続区間は、あくまで2を除いた列のものである。後で同じ記号の間に2を入れても、この分類は変わらない。

必須の2を置いてから、残りを隙間へ配る

一つの BB を固定する。元の列で1と3を隣接させないためには、異記号境界の hh 箇所すべてに少なくとも1個の2が必要である。h>X2h>X_2 なら2が足りず、この BB から作れる列は0通りとなる。

h≤X2h\leq X_2 なら、それぞれの境界用に2を1個ずつ確保する。残る2の個数を q=X2−hq=X_2-h とする。これらは、BB の要素間と両端、合計 m+1m+1 個の隙間(gap)へ自由に配れる。同じ記号の間にも、既に必須の2を確保した境界にも、追加してよい。

隙間ごとの追加個数は非負整数で、合計が qq となる。その配分は、qq 個の印と隙間を区切る mm 本の仕切りを並べることで表せる。隣り合う仕切りは、追加個数0の隙間を表す。よって配分数は

(q+mm)=(m+X2−hm)\binom{q+m}{m}=\binom{m+X_2-h}{m}

となる。上側の添字は「残った2の個数+仕切りの本数」である。必須の2を先に完成列へ置き、その2の前後を別々の隙間として数えると重複するため、隙間は元の BB に対して固定する。

例えば B=(1,3,1)B=(1,3,1) なら m=3,h=2m=3,h=2 で、隙間は □1□3□1□ の4箇所である。X2=2X_2=2 なら追加分は0個なので、作れるのは 12321 の1通りだけ。X2=3X_2=3 なら追加の2を入れる隙間が4通りあり、212321、122321、123221、123212 を得る。それぞれ (33)=1\binom{3}{3}=1、(43)=4\binom{4}{3}=4 と一致する。

以上より、両端と ii を固定した寄与は次の積になる。

part⁡(X1,r1)part⁡(X3,r3)(m+X2−hm)\operatorname{part}(X_1,r_1)\operatorname{part}(X_3,r_3) \binom{m+X_2-h}{m}

実際の計算では、N=X1+X2+X3N=X_1+X_2+X_3、法を P=998244353P=998244353 とし、NN までの階乗・逆階乗を前計算して各二項係数を定数時間で求める。表の行ごとに、1・1では 2≤i≤min⁡(X1,X3+1)2\leq i\leq\min(X_1,X_3+1)、3・3では 2≤i≤min⁡(X1+1,X3)2\leq i\leq\min(X_1+1,X_3)、異なる両端では 1≤i≤min⁡(X1,X3)1\leq i\leq\min(X_1,X_3) を走査する。各項で h>X2h>X_2 なら飛ばし、残る積を法 PP で加算する。1・3と3・1は同数なので、片方の寄与を2倍してもよい。

入力例の (X1,X2,X3)=(2,2,1)(X_1,X_2,X_3)=(2,2,1) では、両端1・1の寄与が1、3・3は作れず0、1・3と3・1の寄与が各4で、答えは 1+0+4+4=91+0+4+4=9 となる。

典型の発動条件

run構造による列数え上げ

同じ記号が何個続くかより、記号の切り替わる回数が制約を決めるときは、連続区間の個数でまとめる。二記号の連続区間は必ず交互になるので、両端を固定すると二つの区間数を一つの変数で表せる。

正の整数分割とgap挿入

同じ記号を非空な連続区間へ分けるなら、正の長さの和を数える。別の記号を隙間へ挿入するなら、各隙間の個数を数える。後者に下限がある場合は、必須分を先に差し引き、残りを非負整数として配れるか確認する。

問題固有の要素

隣接差の条件が禁止するのは1と3の組だけで、2はどの記号とも隣り合える。この違いに注目すると、2を除いて問題の骨格を取り出し、必要な境界だけ2で遮る方針が見える。

別の問題へ持ち帰る視点は、一部の記号を取り除いた列を先に決め、取り除いた記号を戻す条件が隙間ごとの下限へ変わらないか調べることである。

正当性

任意の合法な列から2を除くと、列 BB、その両端、各連続区間の長さが一意に決まる。逆に両端と正の区間長を選ぶと BB を一意に復元できるため、part⁡\operatorname{part} の積が各分類の BB を漏れなく重複なく数える。BB の異記号境界 hh 箇所では2が1個以上必要であり、それ以外の隙間では0個以上でよい。各異記号境界の個数から1を差し引くと、残る X2−hX_2-h 個の2の全隙間への非負配分と一対一に対応する。逆に配分へ必須分を戻せば必ず合法な列になる。したがって各分類の積は合法列をちょうど一度ずつ数え、四つの両端の分類と全区間数の総和が答えとなる。

実装上の注意

  • 1と3はともに正の個数なので、両端が同じ場合に i=1i=1 は使えない。どの連続区間も長さ1以上とし、part⁡(n,k)\operatorname{part}(n,k) は k<1k<1 または k>nk>n なら0を返す。
  • h>X2h>X_2 の項は二項係数を評価する前に飛ばす。h=X2h=X_2 なら残りは0個で、挿入方法は1通りとなる。
  • X1=X3=1X_1=X_3=1 なら BB は 13 と 31 だけで、各々 h=1h=1。答えは 2(X2+12)=X2(X2+1)2\binom{X_2+1}{2}=X_2(X_2+1) であり、最小入力 (1,1,1)(1,1,1) では 123 と 321 の2通りになる。
  • 二項係数は 0≤k≤n0\leq k\leq n のときだけ階乗表を参照する。階乗と逆階乗を 00 から NN まで用意する。積を取るたびに法 PP で割った余りへ戻し、整数で実装する場合は乗算に64 bit整数を使う。

復習の核

  • 隣接条件を扱いにくいときは、一部の記号を取り除き、残った列で「必ず埋める境界」を探す。
  • 二記号の連続区間は交互になる。両端を決めれば、区間数の関係と必要な境界数を表にできる。
  • 下限つきの配分は必須分を差し引く。挿入の隙間は元の列に固定し、必須分の前後を別々に数えない。

計算量と制約

時間

固定された法 P=998244353P=998244353 のもとで O(N)O(N)。階乗表の構築に O(N)O(N)、末尾の階乗の逆元を二分累乗で求めるのに O(log⁡P)O(\log P)、逆階乗表の構築に O(N)O(N) かかる。各分類の走査は合計 O(X1+X3)O(X_1+X_3) 項で、1項の評価は O(1)O(1) である。

空間

O(N)O(N)。階乗・逆階乗の二つの表を保持し、数え上げには定数個の変数を使う。

制約との対応

公式制約は整数 1≤X1,X2,X3≤1061\leq X_1,X_2,X_3\leq10^6、実行時間制限は2秒、メモリ制限は1024 MiBである。N≤3×106<PN\leq3\times10^6<P なので階乗は法 PP で0にならず、逆階乗による計算が使える。各二項係数の上側の添字も NN 以下なので、上の前計算範囲で足りる。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Count 123 の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

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

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

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

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

      学習の位置

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

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

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

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

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題