ABC 401-500/ABC433D - 183183 - 競技プログラミング用 知識集積所

---

問題

ABC433D

必要知識

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

• 剰余類環

考え方

問題のややこしさの原因は、Aの中身がものによりバラバラの桁数をしていることにある。
そこで、まずは「仮に全部3桁だとしたら、」で考えてみる。

この場合、以下の手順で解ける。

• 全ての要素について、1000倍してmで割った余りを用意する
• どんなものが何個あったか、map※か何かを使ってカウントする
• 再び全ての要素について、前半部分の余りがいくつだったらちょうどmの倍数になるかを考え、そうなっているものの個数を結果に計上

さて、Aの桁数がバラバラな場合は、1000倍するところを、10倍版、100倍版、1000倍版…10^10倍版と全て用意し、毎回桁数に合わせて参照すればよいだけである。
具体的には、剰余類環の考え方で、「10倍してmで割った余りを求める」を何度も繰り返して、それぞれの0の個数に対応する異なるmap※に計上していけばよい。

解答例

解答例

注意点

答えの集計にはlong long型を用いる

Aの中身が全部同じだったりすると、答えがint型の範囲をはみ出る場合があるので注意。

愚直に数を作ると、long long型ですらはみ出る

1000000000に1000000000をくっつけた10000000001000000000は10^19を超えており、long long型すらはみ出る。
unsignedなら足りるが、そもそもそんなギリギリを攻めなくてもよい方法がある。

別解

二分探索※で頑張る

map※はO(N*logN)ではあるが定数がちょっと重く、TLEのリスクが少しある。
それが怖い場合、全部vectorにいれてソートし、二分探索で個数を数えてもよい。
同じオーダーでも、定数倍が圧倒的に軽くなる。