ProjectEuler 162

包除原理の例題みたいな問題。

先頭から続く0は無視することだけ注意すればよい。

n桁の16進数xの個数は15*16^n個
f(prop) = 条件propを満たすn桁の16進数の個数
とすると

f(0を含む & 1を含む & Aを含む) = 15*16^n - f(0を含まない | 1を含まない | Aを含まない)]

包除原理より
f(0を含まない | 1を含まない | Aを含まない)=f(0を含まない)+f(1を含まない)+f(Aを含まない)
-f(0を含まない & 1を含まない)-f(1を含まない & Aを含まない)-f(Aを含まない & 0を含まない)
+f(0を含まない & 1を含まない & Aを含まない)

それぞれ
f(0を含まない) = 15^n
f(1を含まない) = f(Aを含まない) = 14*15^(n-1)
f(0を含まない & 1を含まない) = f(Aを含まない & 0を含まない) = 14^n
f(1を含まない & Aを含まない) = 13*14^(n-1)
f(0を含まない & 1を含まない & Aを含まない) = 13^n

したがって
f(0を含まない | 1を含まない | Aを含まない) = 15^n+2*14*15^(n-1)-2*14^n-13*14^(n-1)+13^n
f(0を含む & 1を含む & Aを含む) = 15*16^(n-1)-43*15^(n-1)+41*14^(n-1)-13^n