AcWing 1084. 数字游戏 II python
原题链接
中等
作者:
ppz
,
2021-01-11 17:04:54
,
所有人可见
,
阅读 221
Python 代码
# DP 推f
def init(P):
N = 11; # 数据位数
M = 110; # 取余范围
# 状态数组:f(i, j, k),i位数,高位是j,模P余k的数的个数
# 每次f需要清空
f = [[[0 for _ in range(M)] for _ in range(10)] for _ in range(N)]
# 一位时
for i in range(10):
f[1][i][i % P] += 1
# 状态计算
for i in range(2, N):
for j in range(10):
for k in range(P):
for x in range(10):
f[i][j][k] += f[i-1][x][(k-j) % P]
return f
def dp(n, P, f):
# 边界判断
if n == 0:
return 1
# 拆分数字,从低位到高位
nums = []
while n:
nums.append(n % 10)
n //= 10
res = 0 # 答案
last = 0 # 前面位的和
# 树形
# 从高位到低位枚举每一位
for i in range(len(nums)-1, -1, -1):
x = nums[i]
for j in range(x): # 左分支
res += f[i+1][j][(-last) % P] # 前面位的和是last,那么后面位的和就是-last % P,依据0 % P = 0
last += x
if i == 0 and last % P == 0:
res += 1
return res
# 读入数据
while True:
try:
line = input()
except:
break
a, b, p = map(int, line.split())
# 每次P不同都要重新初始化
f = init(p);
# 输出结果
print(dp(b, p, f) - dp(a-1, p, f))