753数の数え上げ - さくBは折り紙を折っている

引き続きAtCoderで遊んでます。さっくです。
今日はAtCoderに出てきた「753数」を紹介します。
ある自然数 $N$ が「753数」であるとは

この２つの条件を満たすことを言います。

例えば753や37575、55555537などが753数です。

一方、7775や35、555は753数ではありません。

「与えられた自然数 $N$ に対して、 $N$ 以下の753数の個数を求めよ」

という問題でした。

今回は少し問題を変えて、

「 $N$ 桁の753数の個数を求めよ」

という問題について考えてみたいと思います。

まず、上の条件(1)を満たし、条件(2)を満たさない数を「準753数」と呼ぶことにしましょう。

$N$ 桁の準753数は $3^N$ 個ですね。

なぜなら、各桁には7,5,3の3通りの数字の選び方があるからです。

twitter上で見かけたある方のつぶやきでベン図の有用性を改めて認識したので、

ベン図を描いてみます。

f:id:sakusaku858:20190117004032p:plain

求めたいのはグレーの部分（A）です。

$H=0$ です。3も5も7も含まない準753数は0個。

$E=F=G=1$ です。3しか含まない $N$ 桁の753数は1個です。

$B=C=D=2^N-2$ です。例えば7含まない $N$ 桁の753数は $2^N$ 個です。

したがって

$A=3^N-3(2^N-2)-3=3^N-3\cdot 2^N+3$

です。

ゆえに $N$ 桁の753数は $3^N-3\cdot 2^N+3$ 個でした。

これをうまく使って、与えられた自然数 $N$ に対して、 $N$ 以下の753数の個数を高速に求められないかなぁ。などと考えていました。