AtCoder Beginner Contest 178を見直す

全体の感想

A問題に2分、B問題で30分、C問題で時間切れになりました。C問題は1時間以上考えたんですが、最終的に考え方を間違って回答できなかったので、C問題を見直そうと思います。

C - Ubiquity

問題
整数Nが与えられるので、0から9で作られる長さNの整数列で、0と9が含まれるものの数を求めよ。解答が大きくなる可能性があるので10^9+7で割った余りを出力してください。

解説
ベン図を使って考えると良いです。
まず、0〜9の数字で構成される長さNの数列全体の個数は10^Nです。
次に下図a、９が含まれない長さNの数列の個数は構成される数字が0〜8になので9^Nになります。
同様に下図b、０が含まれない長さNの数列の個数も9^Nとなります。
更に下図c、0も9も含まれない1〜8で構成される数列の個数は8^Nとなります。

ここから、上図水色斜線部分を求めたいので、上記しているように式は以下のようになります。

10^N - ( 9^N + 9^N - 8^N )

のこaとbの集合を求めるときに重複部分を引く考え方を包除原理と呼ぶそうです。

包除原理 - Wikipedia

解説見て作成したコード

上記の考え方で作成したコードが以下です。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod=1000000007;

ll modpow(ll a, ll n) {
   ll res = 1;
   while (n > 0) {
       if (n & 1) res = res * a % mod;
       a = a * a % mod;
       n >>= 1;
   }
   return res;
}

int main() {
   int n;
   cin >> n;
   ll ans = modpow(10, n) - (modpow(9, n)*2 - modpow(8, n));
   ans %= mod;
   if(ans < 0) ans += mod;
   cout << ans << endl;
   return 0;
}