數位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;
}