Python3で解く AtCoder Beginner Contest 178 C - Ubiquity

包括原理より、全パターンから条件に合わないものを引く。
計算過程では繰り返し二乗法を使う（ $x^n$ という形は愚直に計算すると遅い）

概要

長さ個の整数列が以下の条件に当てはまる個数をとするとを求める。
- 整数列で使えるのは整数は0から9までの10個の整数。
- 長さ $n$ 個の整数列 $a$ に0を含む。
- 長さ $n$ 個の整数列 $a$ に9を含む。

解くときに考えた内容

コンテスト中は求めたいものをそのまま求めようとして失敗。
全てのパターンから条件に合わないパターンを引く
全パターンは長さ個の整数列で10文字使えるので、
- $10^n$ 個
0を含まないパターンは、長さ個の整数列で0以外で構成するので9文字使えるので、
- $9^n$ 個
同様に9を含まないパターンは、長さ個の整数列で9以外で構成するので9文字使えるので、
- $9^n$ 個
ただ、上記だと0と9をどちらも含まない場合を重複してかぞえているので、その値は、長さ個の整数列で0, 9以外で構成するので8文字使えるので、
- $8^n$ 個
よって、求める組み合わせの数は、
$10^n - (2 \times 9^n - 8^n) = 10^n - 2 \times 9^n + 8^n$ 個
今回は $n$ が大きいと、これは巨大な数になるので、 $mod (10^9+7)$ で考えるが、制約が大きいため愚直にやるとTLEになる。
ここで、 $x^n$ はどう計算するかを考える。繰り返し二乗法と呼ばれる方法を使う。
繰り返し二乗法
例えば、 $x^{50}$ の時、 $50 = 2^5 + 2^4 +2^1$ なので、 $x^{50} = x^{2^{2^{2^{2^2}}}} \times x^{2^{2^{2^2}}} \times x^2$ とかける。
実装としては以下のようになる。ただし、Pythonはmathにpowがありこれ自体が繰り返し二乗法で実装されているらしいので自分で実装する必要はないが、勉強のため。

# 繰り返し二乗法の実装例
def modpow(x, n, mod):
    res = 1
    while n:
        if n % 2:
            res *= x % mod
            res %= mod
        x *= x % mod
        n >>= 1
    return res

$10^n - 2 \times 9^n + 8^n$ を計算する時に、それぞれの項で繰り返し二乗法をつかって求める。
（足し引き後もmodを計算するのを忘れずに）

コード

n = int(input())
mod = 10 ** 9 + 7 #素数

# 繰り返し二乗法
def modpow(x, n, mod):
    res = 1
    while n:
        if n % 2:
            res *= x % mod
        x *= x % mod
        n >>= 1
    return res

# 全パターン:10 ** n
all_p = modpow(10, n, mod)
# 0を含まないパタンーン:9 ** n
not_0 = modpow(9, n, mod)
# 9を含まないパターン:9 ** n
not_9 = modpow(9, n, mod)
# 0と９を含まないパターン:8 ** n
not_0_9 = modpow(8, n, mod)
# 条件のパターン
ans = (all_p - not_0 - not_9 + not_0_9) % mod
print(ans)

書籍

アルゴリズムの参考書籍

問題解決力を鍛える!アルゴリズムとデータ構造
けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」ご本人の記事の中で難易度は、螺旋本ということで初学者でも結構読みやすいのではないかと期待。（というのもけんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているので）
投稿時点では、まだ発売前だけど、すでにベストセラー。予約しておかないとすぐ手元に来ないかも!?と思って速攻ポチった。

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

作者:大槻兼資
発売日: 2020/10/02
メディア: 単行本（ソフトカバー）

drken1215.hatenablog.com

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

いわゆる、螺旋本。Aizu Online Judgeの問題を題材に解説されている。自分としては、 Aizu Online Judgeは最近はβ版運用中で、構成がアルゴリズムの項目ごとに問題がタグ付けされているようなイメージで、ここら辺弱いから集中的にやってみようっていう感じでできるので、いいと思っている。（AtCoderもそんな感じのリスト作って欲しい）ただ、この書籍はC++で書かれているのでPythonでやる場合はあくまでもその過程の考え方を参考にし自分で実装する必要がある。（AOJも解いているので、記事にしていこうかなぁ）