AtCoder Beginner Contest 178 C – Ubiquity を解いた記録
問題の概要
長さ\(N\)の整数の列\(A_1, A_2, \dots, A_N\)（\({A}\)とする）のうち以下の条件をすべて満たすものはいくつあるか．
- \(0 \leq A \leq 9\)
- 列中の整数のうち少なくとも1つは\(0\)
- 列中の整数のうち少なくとも1つは\(9\)
条件を満たすような\({A}\)の数を求め，\(10^9+7\)で割った余りを出力せよ．
制約
- \(1 \leq N \leq 10^6\)
- \(N\)は整数
解法
\({A}\)に登場する数字は\(0\)から\(9\)までの10通りですから，長さ\(N\)の\({A}\)は全部で\(10^N\)通りあります．例えば\(N=3\)の場合，
- 1つ目の数字は他の数字に関係なく\(0\)から\(9\)までの10通り
- 2つ目の数字も他の数字に関係なく\(0\)から\(9\)までの10通り
- 3つ目の数字も他の数字に関係なく\(0\)から\(9\)までの10通り
ですから\({A}\)は全部で\(10 \times 10 \times 10 = 10^3\)通りです．
また，列中に\(0\)を1つも含まないような\({A}\)は全部で\(9^N\)通りです．例えば\(N=3\)の場合，
- 1つ目の数字は他の数字に関係なく\(1\)から\(9\)までの9通り
- 2つ目の数字も他の数字に関係なく\(1\)から\(9\)までの9通り
- 3つ目の数字も他の数字に関係なく\(1\)から\(9\)までの9通り
ですから列中に\(0\)を1つも含まないような\({A}\)は全部で\(9 \times 9 \times 9 = 9^3\)通りです．
同様に，列中に\(9\)を1つも含まないような\({A}\)は全部で\(9^N\)通りです．
さらに，列中に\(0\)と\(9\)の両方を1つも含まないような\({A}\)は全部で\(8^N\)通りです．例えば\(N=3\)の場合，
- 1つ目の数字は他の数字に関係なく\(1\)から\(8\)までの8通り
- 2つ目の数字も他の数字に関係なく\(1\)から\(8\)までの8通り
- 3つ目の数字も他の数字に関係なく\(1\)から\(8\)までの8通り
ですから列中に\(0\)と\(9\)の両方を1つも含まないような\({A}\)は全部で\(8 \times 8 \times 8 = 8^3\)通りです．
ここで，問題の条件をすべて満たすような\({A}\)の数は\(10^N-9^N-9^N+8^N\)となります．先述した通り，
- 全ての\({A}\)の数は\(10^N\)個
- 列中に\(0\)を1つも含まないような\({A}\)は\(9^N\)個
- 列中に\(9\)を1つも含まないような\({A}\)は\(9^N\)個
- 列中に\(0\)と\(9\)の両方を1つも含まないような\({A}\)は\(8^N\)個
です．求める\({A}\)の数は下図のうち背景色が灰色の部分です．背景色が灰色の部分の数を求めるためには，全体の数から背景色が白の部分の数を引けばOKです．
背景色が白の部分の数は，列中に\(0\)を1つも含まないような\({A}\)の数と列中に\(9\)を1つも含まないような\({A}\)の数の和を求め，
そこから列中に\(0\)と\(9\)の両方を1つも含まないような\({A}\)の数を引くことで求められます．
単純に列中に\(0\)を1つも含まないような\({A}\)の数と列中に\(9\)を1つも含まないような\({A}\)の数の和を求めただけだと，
列中に\(0\)と\(9\)の両方を1つも含まないような\({A}\)が2回カウントされてしまう点に注意しましょう．
解説 – AtCoder Beginner Contest 178でも言及されている通り，この解法は包除原理の適用といえます．
実装例
この問題では\(1 \leq N \leq 10^6\)となっているため，10の\(N\)乗などの計算を愚直に行っても十分間に合います．
\(N\)が大きな数の場合は，繰り返し2乗法（バイナリ法）と呼ばれる方法を用いて累乗の計算を行う必要があるでしょう．
感想
私はコンテスト中に制約をよく読まなかったか，それとも累乗の計算を見て条件反射で「繰り返し2乗法を使わないとTLEする」と思ったかで繰り返し2乗法のコード（自前ライブラリ）をコピペしました．