如何高效统计十三进制下13位幸运数字的总数？

问题背景 #

我们需要统计十三进制（数字范围：0,1,2,3,4,5,6,7,8,9,A,B,C，对应数值0-12）下，带前导零的13位数字中「幸运数字」的总数。

幸运数字的定义：一个数的前6位数字之和等于后6位数字之和，中间第7位数字不影响判定。示例：

0055237050A00 - 幸运数字 => 0+0+5+5+2+3 = 0+5+0+A+0+0（A对应数值10）
1234AB988BABA - 非幸运数字 => 1+2+3+4+A+B != 8+8+B+A+B+A

原暴力遍历思路需要覆盖13^13（约3.02×10¹⁴）个数，完全不具备可行性，以下是高效解决方案。

优化思路：动态规划+组合数学 #

核心是拆分问题，避免全量遍历：

• 中间第7位数字可以是0-C任意值，共13种选择，最后直接将结果乘以13即可。
• 单独计算6位十三进制数字（带前导零）的所有可能和的出现次数，再利用组合数的对称性计算符合条件的组合总数。

具体实现步骤 #

1. 计算6位十三进制数的和分布 #

用动态规划统计每个可能的和对应的6位数组合数：

// 6个十三进制数字的最大和为6*12=72，所以数组长度设为73（索引0到72）
long[] sumCount = new long[73];
sumCount[0] = 1; // 初始状态：0个数字，和为0的组合数是1

// 迭代计算每一位数字加入后的和分布
for (int i = 0; i < 6; i++)
{
    long[] nextSumCount = new long[73];
    for (int currentSum = 0; currentSum < 73; currentSum++)
    {
        if (sumCount[currentSum] == 0) continue;
        // 遍历当前位可能的所有数字（0-12）
        for (int digit = 0; digit < 13; digit++)
        {
            nextSumCount[currentSum + digit] += sumCount[currentSum];
        }
    }
    sumCount = nextSumCount;
}

2. 计算幸运数字总数 #

对于每个可能的和s，前6位和为s的组合数是sumCount[s]，后6位和为s的组合数也是sumCount[s]，两者相乘即为该和对应的符合条件的前后6位组合数。将所有和的结果相加，再乘以中间位的13种选择：

long totalLucky = 0;
foreach (long count in sumCount)
{
    totalLucky += count * count;
}
totalLucky *= 13;
Console.WriteLine("幸运数字总数：" + totalLucky);

效率说明 #

该方案的时间复杂度仅为6×73×13 = 5694次运算，瞬间就能得到结果，完全规避了暴力遍历的天文级计算量。

内容的提问来源于stack exchange，提问作者Nick Farsi