zcmimi's blog

arrow_back数位dp共2篇文章

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

数位dp模板题

我们先不考虑前导0,那么满i位所有数字出现的次数是相同的

f_i为满i位数字出现的个数(因为相同就不需要再加一维了)

那么f_i = f_{i-1} \times 10 + 10^{i-1}

((0-9)+(0-9.....))

(0-9:10^{i-1},(0-9.....):f_{i-1} \times 10)

我们来想想ABCD的答案

先考虑A000中的000,每种数据出现的次数是A \times f_3(因为A后面有3位)

那么0~A-1出现的次数还要加上10^{i-1}(X xxx(xxx:0-999))

接着考虑ABCD中的BCD,A出现的次数加上BCD+1(000-BCD)

最后减去前导0,也就是0001,0002,...0101,0102,...,0999这些,那么0出现的次数减去10^{i-1}

答案就是solve(r)-solve(l-1)

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

https://www.cnblogs.com/dplearning/p/4719375.html

f[i][0]:不包含624,

f[i][1]:2开头幸运数,

f[i][2]:含462,

f[0][0]=1,f[0][1]=f[0][2]=1.

1/1
Search
search