ABC 401-500/ABC433F - 1122 Subsequence 2 - 競技プログラミング用 知識集積所

---

問題

ABC433F

必要知識

B以下レベルの内容は省略

• 累積和
• 二項係数※
• 剰余類環
  • 繰り返し二乗法※
• ヴァンデルモンドの恒等式※

考え方

C問題の、連続である必要がなくなった版。
連続でなくなったせいで、境界基準で数える方法が使えなくなった。
そこで、ある数に着目し、「そこが前半の最後になるものは何個あるか」を計算していき、合計する。

例えばある桁の数が1だった場合。
そこより前に1がA-1個（つまり、注目の桁がA番目）、そこより後ろに2がB個あったとする。

• "12"を作れるパターン数は、Comb(A-1,0)*Comb(B,1)個
• "1122"を作れるパターン数は、Comb(A-1,1)*Comb(B,2)個
• （中略）
• "1..12..2"（m個ずつ）を作れるパターン数は、Comb(A-1,m-1)*Comb(B,m)個（m=min(A,B)）

なので、その1を前半の末尾とするものはこれらの合計である。

ある桁の数が9以外であれば全て同様で、9だった場合は明らかに0。
ということで、計算量を気にしないならこれで解ける。
しかし、ところどころ計算量が爆発しており、3ヶ所で高速化が必要。

まず、その前後に指定の数が何個あるかを数える方法。
これは、10個の累積和を作っておけばよい。

そして、Σ[i] Comb(A-1,i-1)*Comb(B,i)。
これは一見してmin(A,B)回かかりそうに見えるがそうではない。
これは実は、「使う1と使わない2に印をつける」と考えると、A+B-1個の中からA個のものを選ぶ話になり、Comb(A+B-1,A)で一発で求められる。（ヴァンデルモンドの恒等式※）

最後に、二項係数※Comb(n,r)の計算。
これは、事前に階乗を必要なだけ（A+B-1としてあり得る範囲、つまり|S|-1まで）求めておくと、1つ1つのComb(n,r)は剰余類換※の知識を使ってすぐに求められる。

以上3つの高速化をすると、O(|S|)になって間に合う。

解答例

解答例

注意点

別解