AcWing 1081. 度的数量
原题链接
中等
作者:
ppz
,
2021-01-11 10:11:17
,
所有人可见
,
阅读 209
度的数量,跟着视频写
Python 代码
# 获得输入
X, Y = list(map(int, input().split()))
K = int(input())
B = int(input())
N = 35 # 根据数据范围选择空间大小
f = [[0] * N for _ in range(N)]
def init():
# 从i个数里选j个数的方案数
global N
for i in range(N):
for j in range(N):
if j == 0:
f[i][j] = 1
else:
f[i][j] = f[i-1][j] + f[i-1][j-1]
init()
# 数位DP
def dp(n):
global K, B # B进制下选K个1
# 边界判断
if n == 0:
return 0
# 将数拆分为b进制,每一位是处于[0,B)之间的整数,从低位到高位
nums = []
while n:
nums.append(n % B)
n //= B
res = 0 # 答案
last = 0 # 本题中表示前缀1的个数
# 从高位到低位枚举每个位
for i in range(len(nums)-1, -1, -1):
x = nums[i]
if x: # x 不为0,才会存在分支
res += f[i][K - last]
if x > 1: # x > 1 才会存在左分支
if K - last - 1 >= 0:
res += f[i][K-last-1] # 从a个数中选b个数:C(a,b) = C(a-1,b) + C(a-1,b-1)
break
else:
last += 1 # x = 1,则往下层走
if last > K: break
if i == 0 and last == K: # 走到最后一位
res += 1 # 右分支只加1
return res
# 题目的意思则转化为B进制表示下选择K个1的问题
print(dp(Y) - dp(X-1))