ABC 178 C問題 [数学的に解く]

C - Ubiquity

difficulty:653

要約

最初イマイチ問題の意味が掴めなかったが，5分ほど考えて，ようは0~9しか含まないN個の文字列の中で，必ず0,9を含むような文字列のパターンはどのようなものがあるか？という数Aの組み合わせのような問題に帰着した．

ここまで思考できれば，どっかに0か9がこればいいんだけど，それをいちいち全部考えていくことより，逆に0,9を必ず含まない場合を考えて，それを全通りから引いてやれば良いことがわかる．

0か9どちらかを必ず含まない場合

＝(0が一回も出ない) + (9が一回も出ない) - (0,9共に含まない場合)

という計算で求められ，

0が一回も出ない = 1~9しか出ない

と言いかえれるのでこれはN個の文字を選ぶ時，どの時も1~9の9パターンの取り出し方が考えられるので9**N通り考えられる．

という思考の流れ．後はこれを実装するだけ

N = int(input())
a = (10**N)%(10**9+7)
b = (9**N)%(10**9+7)
c = (8**N)%(10**9+7)
print((10**N-2*9**N+8**N)%(10**9+7))
#print(a-2*b+c)

感想

このような数学に寄った問題ならワンちゃんあるので実装力をどんどんつけて行きたい．