数位DP站在巨人的肩膀上,此文章思路来源于灵茶山艾府,文章原思路视频版:数位 DP 通用模板
例题:2376. 统计特殊整数
要解决这道题需要前置知识「位运算与集合论」,在这简述一下:
集合可以用二进制表示,二进制从右往左第 iii 位为 111 表示 iii 在集合中,为 000 表示 iii 不在集合中。例如集合 {0,2,3}\left\{ 0,2,3 \right\}{0,2,3} 对应的二进制数为 1101(2)1101_{(2)}1101(2)
设集合对应的二进制数为 xxx,本题需要用到两个位运算操作:
判断元素 ddd 是否在集合中:x >> d & 可以取出 xxx 的第 ddd 个比特位,如果是 111 就说明 ddd 在集合中
把元素 ddd 添加到集合中:x = x|(1<<d)
思路:
将 nnn 转换为字符串 sss,定义 f(i,mask,isLimit,isNum)f(i,mask,isLimit,isNum)f(i,mask,isLimit,isNum) 表示构造第 iii 位及其之后数位的合法方案数,其余参数的含义: ...