AcWing 1081. 度的数量 - python3 带一点解释
原题链接
中等
作者:
vitalime
,
2022-03-29 13:33:05
,
所有人可见
,
阅读 157
x,y = map(int, input().split())
k = int(input())
b = int(input())
N = 35
f = [[0 for i in range(N+1)] for i in range(N+1)]
# 递推预处理组合数
for i in range(N+1):
for j in range(N+1):
if j == 0:
f[i][j] = 1
else:
f[i][j] = f[i-1][j] + f[i-1][j-1]
# 将n转为b进制,然后从高到低分位考虑
def dp(n):
if not n: return 0
nums = []
res = 0
last = 0
while n:
nums.append(n%b)
n //= b
for i in range(len(nums) - 1, -1, -1):
x = nums[i]
if x > 0:
# 当前位大于0,说明假如当前位取0,剩下的i位(从0到i-1)随意取,所以求解空间是i个位置放0或1
# C(i, k-last) 即从i位选k-last个位置放1其余放0
res += f[i][k-last]
if x == 1:
# 当前位正好是1,剩下的位置不能随便取,因为有可能会大于当前数,所以last++,留给后面解决
last += 1
if last > k:
# 当当前位置取1之后超过了k个1就没必要继续往下走了
break
else:
# 当前位大于1,那剩下i位中随便取都不会大于n,
# 所以这涵盖了剩余的所有情况,可以break
if k - last - 1 >= 0:
res += f[i][k-last-1]
break
if i == 0 and last == k:
res += 1
return res
print(dp(y) - dp(x-1))