关于数位dp

本来是8个月前答应写的，咕咕了240天，汗
数位dp

定义：from-OI Wiki

说点人话：

当一道关于特定数字计数的问题出现，值域范围到达\(10^{18}\),可以通过枚举每个数位上的数, 递推/搜索 出答案
小思想:关于统计区间\([L,R]\)之间数的数量

前缀和:\(sum[L,R]=sum[1,R]-sum[1,L-1]\)
具体例题

1. P2602 [ZJOI2010] 数字计数

可以发现,如果直接枚举数字,会炸掉,联想一下会枚举的数字

• 11111111
  
• ......
  
• 21111111
  
• ''''''
  
• 31111111
  
• ......
  

发现重合部分好多,可不可以避免重合呢?
直接告诉你 : 爆搜+剪枝
(比如)搜到亿位时,发现后面的数字出现次数相当,直接返回搜过的值
给出基本代码并讲解

[code]int dfs(int pos,bool limit,int sum,bool lead0,int d){        int res=0;        if(!pos) return sum;        if(!limit&&dp[pos][sum]!=-1) return dp[pos][sum];        int up=limit?a[pos]:9;        for(int i=0;i