ABC 401-500/ABC444D - Many Repunit Sum - 競技プログラミング用 知識集積所

---

問題

ABC444D

必要知識

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

• 階差数列※
  • 累積和

考え方

まずは桁数が非常に大きい数を扱う方法を考える必要がある。
これは、長ーい十進法の数を、桁ごとに別枠にしたvectorとして表現してしまえばよい。
つまり、111を足すなら、

• 百の位に該当する要素に1を足す
• 十の位に該当する要素に1を足す
• 一の位に該当する要素に1を足す
• もし10以上の値が入っているところがあれば、繰り上がり処理を行う

とやればよい。

しかし、これをそのままやると、足すレピュニットの桁数が多いと計算量が増えてTLE。
そこで高速化の工夫をする。
足すのがレピュニットであるということは、vectorのある範囲全てに1を足すということである。
つまり、まずはそのvectorの階差数列※を作っておき、全入力分処理した後で累積和で本来の値を復元すればよい。
これであとはvectorの長さに気を付けながら繰り上がり処理をするだけとなる。

解答例

解答例

注意点

別解