比较典型的动态规划问题。
用$c_{i,k}$表示各位数字之和为k的i位b进制数的总数，并记$m=d/2$。
前m位等于后m位等于k的d位车票共有$c_{m,k}^2$种情况（前m位和后m位各$c_{m,k}$种选择）。
一个i位b进制数，各位数字之和最小是0，最大是$i(b-1)$，共$i(b-1)+1$种情况。
因此幸运票总数是$\sum_{k=0}^{m(b-1)+1}c_{m,k}^2$
$c_{i,k}$可以递推计算：
$$c_{i,k}=\sum_{j=0}^{b-1} c_{i-1,k-j}$$
最终代码有五行。
代码长度：185字节 vs. 全站第一：98字节。
import sys
for a in sys.argv[1:]:
d,b=map(int,a.split());c,i=[1]*b,2
while i<=d//2:c=[sum(x*(0<=j-k<b)for k,x in enumerate(c))for j in range(i*b-i+1)];i+=1
print(sum(i*i for i in c))
|
