十六进制数系统使用16个不同的符号$0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F$分别代表0到15，十六进制数AF在十进制下等于$10\times16+15=175$。

三位十六进制数10A，1A0，A10和A01都包含数字0，1和A。有多少不超过十六位的十六进制自然数（从1开始）同时包含0，1和A？把结果用十六进制数表示。

本题难度:

解答

用容斥原理难以直接算出结果，这是因为形如00011的十六进制数的规范表达应为11并不含0，因此需要用动态规划的手段递推计算。

令$f(n,k)$为包含了总共0、1、A这三种字符中的k种的n位十六进制数的总数，k的取值在0到3之间。

显然$f(1,0)=13$、$f(1,1)=2$。考虑在$n-1$位的十六进制数末尾添加一个数的情况，则有 \begin{align*} f(n,0)&=13\times f(n-1,0), \\ f(n,1)&=3\times f(n-1,0)+(13+1)\times f(n-1,1), \\ f(n,2)&=2\times f(n-1,1)+(13+2)\times f(n-1,2), \\ f(n,3)&=f(n-1,2)+(13+3)\times f(n-1,3). \end{align*} 递推计算可得结果是$f(3,3)+\ldots+f(16,3)=4420408745587516162$，转换成十六进制是$3D58725572C62302$。

f=[[0,0,0,0] for n in range(17)]
f[1][0]=13
f[1][1]=2

for n in range(2,17):
    f[n][0]=13*f[n-1][0]
    f[n][1]=3*f[n-1][0]+14*f[n-1][1]
    f[n][2]=2*f[n-1][1]+15*f[n-1][2]
    f[n][3]=f[n-1][2]+16*f[n-1][3]

s=sum(f[n][3] for n in range(17))

print s,format(s,"X")