数位 DP

数位 DP 统计区间 [0,x] 内满足数字性质的整数，再以 solve(R)-solve(L-1) 得到任意区间答案。按从高到低填数，并记录前缀是否仍贴着 x 的上界。

状态

典型记忆化搜索为 dfs(pos,state,tight,started)：pos 是当前位；state 是题目需要的余数、前一位、出现次数或掩码；tight 表示前缀等于上界；started 区分前导零与真正的数字 0。

long long dfs(int p,int mod,bool tight,bool started){
 if(p==len) return started && mod==0;
 if(!tight && memo[p][mod]!=-1) return memo[p][mod];
 int up=tight?dig[p]:9; long long ans=0;
 for(int d=0;d<=up;d++) ans+=dfs(p+1,(mod*10+d)%K,tight&&d==up,started||d);
 return tight?ans:memo[p][mod]=ans;
}

流程与复杂度

  1. 把 x 拆成数位；
  2. 枚举当前位 0 到上界；
  3. 更新题目状态并递归；
  4. 只缓存 tight=false 的状态。

若状态数为 S、位数为 D，时间 O(10DS)、空间 O(DS)。处理“无前导零”“数字 0 是否计入”“上界为负数”是最常见边界。

整理自 XOJ《数位DP》。