桁DPとは
桁DPとは、「0以上N以下の整数のうち、条件～を満たすものの個数は？」というような問題でNが非常に大きい場合（
実装の仕方
DPテーブルを
dp[何桁目まで確定しているか][未満フラグ][条件] = (条件を満たすものの総数)
と設定します。
未満フラグは、
dp[i][0][ * ]：上からi桁目までがNと一致している
dp[i][1][ * ]：上からi桁目までの段階でN未満が確定している
としておきます。
dp[i][1][ * ]のときは、既にN未満であることが確定しているので必ずdp[i+1][1][ * ]に移ります。
dp[i][0][ * ]のときは、i桁目がN[i]よりも小さくなるときdp[i+1][1][ * ]に、i桁目がN[i]と一致するときはdp[i+1][0][ * ]に移ります。（i桁目がN[i]よりも大きくなるときは、Nより大きくなることが確定するので数えません。）
未満フラグが1のときはそれ以降もずっと1で、未満フラグが0のときは桁の数字によって0か1に遷移するということですね。
初期条件は、0桁目が0であると考えるとそのときの未満フラグは0となり、
dp[0][0][ * ] = ?
とすると上手くできると思います。
例えば、N=12345とすると、
1桁目では、0桁目までの未満フラグは0であり、0はNの1桁目:1よりも小さいので未満フラグ1に、1はNの1桁目:1と等しいので未満フラグ0に移ります。
2桁目では、1桁目までの未満フラグが1のときは0~9すべての場合が未満フラグ1に移り、1桁目までの未満フラグが0のときは、Nの2桁目:2よりも小さい0,1のときは未満フラグ1に、Nの2桁目:2と等しい2のときは未満フラグ0に移ります。Nの2桁目:2よりも大きい3~9はその段階でNよりも大きくなり条件を満たさないことが確定するので数えません。
3桁目以降も同様に考えていけば大丈夫です。
求めたい答えは、n桁目まで確定させて未満フラグが0か1のものなので
dp[n][0][ * ] + dp[n][1][ * ]
となります。
例題（EDPC S -Digit Sum）
1以上K以下の自然数のうち、十進表記における各桁の数字の総和がDの倍数であるようなものは何個でしょうか？
で割った余りを求めてください。 ～制約～
・入力は全て整数である。
・
・
考え方
Dで割った余りが0となる総数が答えになり、Dもそれほど大きくないので、Dで割った余りの情報をDPテーブルに入れてやると上手くできそうですね。
具体的には、DPテーブルを
dp[上から何桁目までを決めたか][未満フラグ][各位の和をDで割った余り]
と設定します。
そして、i桁目に調べている数字をxとすると、DPの遷移は次のようになります。
dp[i+1][1][(sum+x)%D] = dp[i][1][sum%D] （未満フラグが1でK未満が確定しているのでxの値によらず遷移する）
dp[i+1][0][(sum+x)%D] = dp[i][0][sum%D] （x = K[i]のとき)
dp[i+1][1][(sum+x)%D] = dp[i][0][sum%D] （x < K[i]のとき）
0桁目には0が存在すると考えると都合が良く、初期条件は
dp[0][0][0] = 1
となります。
K以下でDの倍数となるものは、Kの桁数をnとすると、
dp[n][0][0] + dp[n][1][0]
になりますが、これは「0」も含まれているので最終的な答えはこの式から1を引いて
dp[n][0][0] + dp[n][1][0] - 1
となります。
コード
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=1000000007;
int main(void){
string K;
int D;
cin>>K>>D;
int n=K.size();
ll dp[10001][2][100]={};//dp[上から何桁目まで決めたか][未満フラグ][各桁の和をDで割った余り]
dp[0][0][0]=1;//初期条件
for(int i=0;i<n;i++){
int a=K[i]-'0';
for(int j=0;j<D;j++){
for(int x=0;x<=9;x++){
dp[i+1][1][(j+x)%D]+=dp[i][1][j];//i桁目までの段階でK未満確定→(i+1)桁目までの段階でK未満確定
if(x==a){
dp[i+1][0][(j+x)%D]+=dp[i][0][j];//i桁目まで一致→(i+1)桁目まで一致
}
else if(x<a){
dp[i+1][1][(j+x)%D]+=dp[i][0][j];//i桁目まで一致→(i+1)桁目の段階でK未満確定
}
dp[i+1][0][(j+x)%D]%=mod;
dp[i+1][1][(j+x)%D]%=mod;
}
}
}
cout<<(dp[n][0][0]+dp[n][1][0]-1+mod)%mod<<endl;//dpでは「0」も数えられているのでそれを引く
return 0;
}
練習問題
ABC007 D - 禁止された数字
ABC029 D - 1
ABC154 E - Almost Everywhere Zero
