标签: 数位dp

6 篇文章

bzoj 3209 & Luogu P4317 花神的数论题 题解
题目链接:bzoj Luogu Description 求$1$到$n$每个数的$1$的个数之积。 对于$ 100\% $的数据,$n\leq 10^15$ Solution 数位$DP$。 可以先把$n$拆成二进制,然后$DFS$。 Code [crayon-5fc3d2b09c3be193299197/]
Luogu P3413 SAC#1 – 萌数 题解
Describe 题目链接 定义“萌数”: 存在长度至少为$2$的回文子串。 问$[L,R]$中共有多少个萌数字? 对于$100\%$的数据$0\leq L\leq R \leq {10}^{1000}$。 Solution 数位$dp$裸题。 $$DFS(x,las,lasqr,has,lim,st)$$ 分别表示第$x$位,上一个数字是$las…
Luogu P4127 [AHOI2009]同类分布 题解
Describe 题目链接 给出两个数$a,b$,求出$[a,b]$中各位数字之和能整除原数的数的个数。 Solution 数位dp。 $DFS(x,sum,dig,lim)$分别表示第$x$位,当前数位之和为$sum$,数字为$dig$,是否到达极限。 但是数据极大,$dig$会达到${10}^{18}$是不可能来记忆化的,所以考虑取模 那么模多…
Luogu P4124 [CQOI2016]手机号码 题解
Describe 题目链接 人们选择手机号码时都希望号码好记、吉利。比如号码中含有几位相邻的相同数字、不含谐音不吉利的数字等。手机运营商在发行新号码时也会考虑这些因素,从号段中选取含有某些特征的号码单独出售。为了便于前期规划,运营商希望开发一个工具来自动统计号段中满足特征的号码数量。 工具需要检测的号码特征有两个:号码中要出现至少 $3$ 个相邻的…
#10168. 「一本通 5.3 练习 3」恨 7 不成妻
Link loj #10168. 「一本通 5.3 练习 3」恨 7 不成妻 Describe 共$T$组数据,求在区间$[L,R]$与$7$无关的数的平方之和。 与$7$有关的数的定义: 1. 整数中某一位是$7$; 2. 整数的每一位加起来的和是$ 7$的整数倍; 3. 这个整数是$7$的整数倍。 $1\leq T\leq 50,1\leq L…
数位dp 学习笔记
前言 数位dp真的好简单啊qwq 什么是数位dp 让我们以这道题为例:Luogu P2657 [SCOI2009]windy数 如果您很懒不想点开题面可以看下面: windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道, 在A和B之间,包括A和B,总共有多少个windy数? 100%的数…