ABC178 C問題 Ubiquity を解く
ABC178のC問題 Ubiquity をシンプルに解説します。
長さ N の整数の列
であって以下の条件をすべて満たすものはいくつありますか。
なる i が存在する。
なる i が存在する。
ただし、答えはとても大きくなる可能性があるので、
で割った余りを出力してください。
まず で割った余りを求めるのはたまに出てきます。
大きい数字を扱うときのテクニックとしても参考になります。
今回は詳細は書きません。
@drkenさんの記事がとてもわかりやすいです。
qiita.com
どこかで私も理解していることを確認するために記事にしようと思います。
Nの最大値がなので何かしら工夫が必要です。
全体の場合の数から、0を含まない場合の数
、9を含まない場合の数
を引いてあげるのが良いと閃きました。
ただし、にすると、0も9も含まない場合の数を2回引いてしまっているので、
を足してあげます。
N=2のときの集合をイメージすると理解しやすいかもしれません。
なのでを
で割った余りが答えになります。
足し算と掛け算については、途中いつでもの余りを求めても結果に影響しません。
引き算については結果がマイナスになったときはを足す必要があります。
ビビりで、頻繁にの余りを求めていたこともあり、最後の引き算で負の値になって1回ミスしました。。。
他の方の解答を見て気づいたのですが、頻繁にの余りを求める必要はなくて、最後に計算して1回余りを求めれば問題ありませんでした。。。
あえて周りくどいコードを書いておきます。
N = int(input()) MOD = 10 ** 9 + 7 # 全パターンの数 subete = (10 ** N) % MOD # 0を含まないパターン数 no_0 = (9**N) % MOD # 9を含まないパターン数 no_9 = (9**N) % MOD # 0も9も含まないパターン数 no_0_9 = (8**N) % MOD ans = subete + no_0_9 ans -= no_0 # 引いた後に負の数だったら10**9+7を足す if ans < 0: ans += MOD ans -= no_9 # 引いた後に負の数だったら10**9+7を足す if ans < 0: ans += MOD print(ans)
ちなみに今回のような考え方を含除原理（ほうじょげんり）と言います。
manabitimes.jp
