ケーキ同好会でも、プログラミングは必須スキルです！ 作：蒼(DPD)
「3！2！1！スタート！！」
王城さんの掛け声が室内に響いた。
「作戦通り問題を読んでね！」
問題はAからI問題までの9問だった。
最後の方の問題は上級者向けの問題で難しいと聞いていたので、
三人で分担して前から6問を解くことになっていた。
有彩ちゃんがAとB、望結ちゃんがCとD、私がEとFを読む。
「A問題できそうだから実装するねー！」
「お願い！」
E問題はPBCの問題で似たような問題を解いたことがあったので、そこまで詰まらず解くことができた。
「E問題実装できるよー」
「C問題時間かかりそうだから、パソコン空いたら先にEお願い」
「わかった！」
F問題を読む。
F - Brute Force Attack 2
実行制限時間:$2$sec/メモリ制限:$1024$MB
配点:$600$点
問題文
あなたは自分でかけたデジタル錠の暗証番号を忘れてしまいました。
かろうじて、暗証番号が $N$ 以下であったことと、各位の和 $S$ は思い出すことができました。
条件からあり得る暗証番号が何通りあるかを出力してください。
ただし、答えは非常に大きくなる可能性があるので、$998244353$で割った余りを出力してください。
制約
入力はすべて整数
$1 \leq N < 10^{10^3}$
$0 \leq S \leq 10^3$
入力形式
$N\ S$
入力例1
$\texttt{50 5}$
出力例1
$\texttt{6}$
条件からあり得る暗証番号は、$\texttt{05,14,23,32,41,50}$ の$6$通りであるので、$6$ と出力してください。
入力例2
$\texttt{100 20}$
出力例2
$\texttt{0}$
条件からあり得る暗証番号が存在しないこともあることに注意してください。
これも、PBCの問題に似たものがあったね。
まず、$N$以下の暗証番号をfor文で全探索して、各位の和が$S$になるものを数える方針で行こう。
とりあえず、$N$以下の暗証番号を全探索する部分で、少なくとも計算量は$O(N)$になる。
この問題の制約は......あれ、$N$が$10^{10^3}$までだ。
$10^8$回の計算が1秒くらいだったから、実行制限時間の2秒には全然間に合わない。
高速化が必要だね。
ひまり先輩が言っていた、
「何回もやってる処理を減らす」、
「計算に必要なデータを前計算する」、
「適切なデータ構造を使う」
のどれかが使えたりしないかな。
というかその前に、全ての暗証番号を全探索する時点で計算量が$O(N)$になっているから、
全ての暗証番号を全探索しちゃだめなのかも。
うーん、難しい。
「A通ったよー！」
有彩ちゃんがA問題を解いたので、B問題に取り掛かる。
E問題の実装をするために、私は有彩ちゃんと交代でパソコンの前に座った。
●
「E問題通った！ごめん、1回間違えた！」
「大丈夫、問題ない」
C問題を解いていた望結ちゃんと交代して、F問題を再び考えます。
でも、ちょっとF問題を解ける気がしない。
「B問題解けたよー」
「望結ちゃんの後お願い！」
「了解しました！」
全ての暗証番号を全探索しちゃだめなら、
暗証番号の各桁の和$S$の方から暗証番号が何通りあるのか分かるのかな？
......高速化が必要な問題はまだほとんど解けたことがないから、ちょっと解くの無理そうかなあ。
「ゆいちゃん、F問題どう？」
「ごめん、解けなさそう」
「ちょっと見てほしい問題があるんだけど」
最後の問題読んでみて、と望結ちゃんが私たちに言った。
「最終問題、私たちで解けるかもしれない」