数位 dp

数位dp

特点

问题大多是指“在 $[l,r]$ 的区间内，满足……的数字的个数、种类，等等。”

但是显然，出题人想要卡你，$r$ 肯定是非常大的，暴力枚举一定超时。

于是就有了数位 dp。

基本思路

数位 dp 说白了就是个数字（$R$​ 进制下），从高位到地位依次填空。

若询问区间为 $[l,r]$，那么可以处理出 $[0,r]$ 与 $[0,l-1]$，相减即可。

显然，一一枚举是不可行的，不妨将其分为若干数位（这应该不可能被卡），每个数位讨论。

在代码中表现为：

设数组 $a$，$a_i$ 表示在 $R$ 进制下，数字 $x$ 第 $i$ 位的数字（位从 $1$ 开始）。

注意到，如果前面填入的数字全部与上界 $r$ 相同，那么这一位就不可以超过 $r$ 的这一位。

那么就可以用一个变量 $Up$ 表示目前是否与 $r$ 完全相同，再进行记忆化搜索即可。

那么有了记忆化搜索（迭代）写法就必然有递推式写法，毕竟记忆化搜索本质上就是 dp。

挑些例题

洛谷 P4999 烦人的数学作业

记忆化搜索显然要有 dp 数组。

设 $f_{i,j}$ 表示在 不顶上界的情况下， 填数到前 $i$ 位，数字和为 $j$ 的方案数，初始值为 $-1$。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=25,Mod=1e9+7;
using ljl = long long;
int T,a[N];
ljl l,r,f[N][9*18+5];
ljl dfs(int st,bool Up,ljl sum)
{if(st<=0)//搜完了return sum;if(!Up&&f[st][sum]!=-1)//搜过了return f[st][sum];int UP=Up?a[st]:9;ljl ans=0;for(int k=0;k<=UP;++k)ans=(ans+dfs(st-1,(Up&&k==UP),sum+k))%Mod;if(!Up)f[st][sum]=ans;return ans;
}
ljl solve(ljl x)
{int lens=0;while(x>0)//搞定每一位。由于是倒着存，所以搜索时也要倒着搜{a[++lens]=x%10;x/=10;}return dfs(lens,1,0);
}
void Main()
{cin>>l>>r;cout<<(solve(r)-solve(l-1)+Mod)%Mod<<'\n';return;
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>T;memset(f,-1,sizeof(f));while(T--)Main();return 0;
}