数位dp有着很明显的特点，一般来说是给定区间[l,r]求满足某种条件区间中的数有多少个
朴素解法一般是O(n)的而n往往很大（10^8起步）
这时候我们就要想办法优化，于是就有了数位dp
数位有两个基本的原则
对于区间数的个数，我们转化为前缀和做（即ans=sum(r)-sum(l-1))
逐位确定
我认为第二条很关键，可以说是数位dp的精髓
一般来说数位dp分两步
打表 形如f[i,j]到有i位且最高位为j的满足条件的个数
统计前缀和
统计前缀和我们需要用到一个非常重要的结论
对于任意一个小于n的数，从高位到低位，必然出现了某一位小于n的那一位
这样我们就可以不受n的限制，用数位开始处理
以bzoj1026这道经典的题目为例
var f:array[..,..] of longint;
d:array[..] of longint;
l,r,t,i,j,k:longint; function get(n:longint):longint;
var i,s,x,j:longint;
begin
if (n>=) and (n<=) then exit(n);
fillchar(d,sizeof(d),);
s:=;
while n<> do
begin
inc(s);
d[s]:=n mod ;
n:=n div ;
end;
get:=;
for i:= to s- do //统计位数小于n的位数的满足条件的数目
for j:= to do
get:=get+f[i,j];
//注意这里是不能直接加前导为0的数组，因为我们在计算前导为0的时候，实际上舍掉了后一位为0~的情况
for i:=s downto do //从高到低逐位统计位数为n的位数且小于n的满足条件的个数
begin
if i<> then x:=d[i]- else x:=d[i]; //小细节，注意n本身也可能是
for j:= to x do //当前位小于n的这位的满足条件的数
begin
if (i=s) and (j=) then continue;
if (s=i) or (abs(j-d[i+])>=) then
get:=get+f[i,j];
end;
if (s<>i) and (abs(d[i+]-d[i])<) then break; //如果逐位统计n本身出现了不满足的情况，那显然要直接退出
end;
end; begin
readln(l,r);
t:=trunc(ln(r)/ln())+;
for i:= to do //题目的特殊要求
f[,i]:=;
for i:= to t do //计算f[i,j]
begin
for j:= to do //注意要包含前导为0的状况
for k:= to do
if abs(j-k)>= then
f[i,j]:=f[i,j]+f[i-,k];
end;
writeln(get(r)-get(l-));
end.
bzoj1026
（话说我第一次拍这道题花了3h，实在太渣……）
当然我们也不能拘泥于这种套路，我觉得
当表打了没什么用的时候我们可以直接逐位计算，如poj3286（统计0的个数）
这里我们讨论，每一位对0的贡献度
var d:array[..] of int64;
i:longint;
l,r:int64; function count(n:int64):int64;
var i,t:longint;
x,y:int64;
begin
for i:= to do
if (n<d[i]) then break;
t:=i-;
count:=;
for i:= to t do
begin
x:=n div d[i]; //当前位前面所组成的数
y:=n mod d[i-]; //当前位后面所组成的数
if (n div d[i-] mod )= then //当前位
count:=count+d[i-]*(x-)+y+
//如果是x0y的情况，是第k位时，我们分2种情况讨论
当小于n的数是p0q的，p∈[,x-],那么这个位上的0可以贡献(x-)*^(k-)
当这个小于等于n的数是x0q, q∈[,y]那么这个位上的0可以贡献y+
else count:=count+d[i-]*x;
//如果当前位不是0，那显然比n小的数中肯定存在当前位为0的；
设数为p0q, p∈[,x], q∈[,^(k-)-] 因为当前位已经小于则显然可以贡献x*^(k-)
end;
end; begin
d[]:=;
for i:= to do
d[i]:=d[i-]*;
readln(l,r);
while (l<>-) do
begin
if l= then writeln(count(r))
else writeln(count(r)-count(l-));
readln(l,r);
end;
end.
poj3286
数位dp需要大量的思考，有时候看起来对的实际上是错的
但由于这种题目暴力，数据都非常好弄
所以一定要孜孜不倦的对拍，恩恩