AtCoder Beginner Contest 178 C問題 - Qiita

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が存