AtCoderを始めましたが、ABCのA・B問題はほぼ解ける、C問題は運が良ければ解けるというレベルです。
まずはC問題を難なく解けるというの目標に、まずは過去問のC問題までをどんどんやっていってます。
自力では解けなかった問題を、解説を見て、理解した内容の整理とその結果のコードを書いていきたいと思います。
#問題
長さ N の整数の列 A_1,A_2,…,A_N であって以下の条件をすべて満たすものはいくつありますか。
・0 < A_i < 9
・A_i=0 なる i が存在する。
・A_i=9 なる i が存在する。
ただし、答えはとても大きくなる可能性があるので、10^9+7 で割った余りを出力してください。
#解けなかった原因
総当たりでは、計算量がかかりすぎるがので、それ以外の方法が必要
#解説を見て理解した内容
包除原理を適用して計算する
- 長さNの整列の組み合わせは、10のN乗
- i=0が存在しない組み合わせは、9のN乗
- i=9が存在しない組み合わせは、9のN乗
- i=0とi=9両方が存在しない組み合わせは、8のN乗
10のN乗(1) - 9のN乗(2) - 10のN乗(3) + 8のN乗（4)
で組合せ数が求まる
#ACしたコード
N = int(input().strip())
print( (10**N - 9**N - 9**N +8**N) % (10**9+7) )