求出至少有一个0,1和A的16位十六进制数的个数

Question

我正在尝试解决 Project Euler 问题 162- https://projecteuler.net/problem=162

In the hexadecimal number system numbers are represented using 16 different digits:

0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F

The hexadecimal number AF when written in the decimal number system equals 10x16+15=175.

In the 3-digit hexadecimal numbers 10A, 1A0, A10, and A01 the digits 0,1 and A are all present.

Like numbers written in base ten we write hexadecimal numbers without leading zeroes.

How many hexadecimal numbers containing at most sixteen hexadecimal digits exist with all of the digits 0,1, and A present at least once? Give your answer as a hexadecimal number.

这看起来是一个简单的问题，只需一点代码就可以解决：

import math

def ncr(n,r):
    return math.factorial(n)//math.factorial(r)//math.factorial(n-r)

sum =0
n=16
for x in range(1,n):
    for y in range(1,n):
        for z in range(1,n):
            if(x+y+z <= n):
                s = x+y+z
                t = ncr(n,s)*ncr(s,x)*ncr(y+z,y)*pow(13,n-s)
                sum += t

for x in range (1,n-1):
    for y in range (1,n-1):
        if(x+y<=n-1):
            s = x+y
            t = ncr(n-1,s)*ncr(s,x)*pow(14,n-1-s)
            sum -= t

print(sum)

我的逻辑 -

假设数字中有 x 个 0、y 个 1 和 z 个 A，现在，对于 x+y+z 小于或等于 16 的所有可能情况，我定义 s = x+y+z

现在我从总共16个数字中选择s个位置，

然后 x 个地方从那些 s 个地方，

然后y个地方从y+z个剩下的地方，

然后，最后，剩下的 16-s 位可以用 0,1,A 以外的任何其他数字填充，所以 13^( 16-s)

现在，由于这些情况涉及 0 出现在第一个位置，我添加了第二个循环来减去第一个位置为 0 且至少有一个 1 和 A 的所有值。我也使用相同的逻辑。

现在我不知道我是在犯一个巨大的逻辑错误还是只是一个愚蠢的小错误，但我真的无法弄清楚为什么我没有得到正确的答案。

我不需要正确的答案或正确的方法来解决这个问题，只想知道这个逻辑/代码有什么问题，任何形式的帮助都将不胜感激。

谢谢

P.S。 - 这是我在这里的第一个问题，请告诉我提问的方式是否有问题。

Answer 1

我在你的代码中看到的一个问题是你只考虑了 16 位数字，而问题要求 "containing at most sixteen hexadecimal digits"。

求出至少有一个0,1和A的16位十六进制数的个数

Finding the number of 16-digit hexadecimal numbers with atleast one 0,1 and A

algorithm

math

combinations

probability

combinatorics