桁DP Typical DP Contest E 数 - tshitaの備忘録Ⅱ

桁DPがいまいち理解出来ていないので考えました．
問題はE: 数 - Typical DP Contest | AtCoderです．

次のページの解法を参考にしています．
Typical DP Contest E 数 - simezi_tanの日記

桁DPとは与えられた数字の桁に関するDP（動的計画法）です．
用語解説 - 桁DP - ゲームにっき（仮）別館（仮）

$N = 226, D = 4$ として具体的に考えてみます．
まず，愚直な方法として1から226までの整数をすべて列挙して，各々の整数の各桁を足してDの倍数となっている整数の個数を調べるというものです．
この場合の答えは55となります．
しかし，この方法だと最大で $10^{10000} \times 1000$ の演算が必要となります．
また，最大のNは $10^{10000}$ となり多倍長の整数型となります．
f:id:tatanaideyo:20141218003836p:plain

桁DPの説明に移る前にこの方法をグラフ上で見てみます．
整数Nの桁数をLとします．（以下の図ではLがNとなっている箇所が多々あります．時間があれば直しますm(. .)m）
有向グラフG = (V,A)を考えます．
頂点集合VをL桁以下からなる整数全体とします（便宜上0を含む）．
桁は大きい方から1桁目，2桁目,・・・L桁目とします．
また，各頂点に $v_{i,j}$ には重み j が付いているとします．

$v_{i,j} \in V$ 　i桁目の数字がj
$(v_{i,j}, v_{i+1,k})$ 　 $(i=1,...,L-1, j=0,1,...,9, k=0,1,...,9)$

f:id:tatanaideyo:20141218012031p:plain

ある整数を1桁目の頂点からL桁目の頂点への有向道に対応させます．
例えば，4桁以下からなる整数全体に含まれる整数219は次の赤色のパスとなります．
f:id:tatanaideyo:20141218012903p:plain

初めに，L桁以下からなる整数全体の中で，各桁の和がDの倍数となる整数の個数を求める問題を考えます．
先ほどの愚直な方法をグラフ上の問題として考えると，1桁目の頂点からL桁目の頂点への有向道の中で通る頂点の重み和がDの倍数となるパスの総数を求める問題となります．

次にN以下の整数という条件を加えた問題を考えます．
具体例としてN = 2198の場合を考えます．
この時の桁数Lは4です．また，便宜上頂点 $v_{0,0}$ を加えて頂点 $v_{1,j} (j=0,...,9)$ への有向辺を加えます．
0桁目の頂点 $v_{0,0}$ からは2以下の頂点 $v_{1,0}, v_{1,1}, v_{1,2}$ のいづれかしか選ぶことが出来ません．
1桁目の頂点の中から2より小さい頂点 $v_{1,0}, v_{1,1}$ のいづれかを選んだ場合は．2桁目では9以下の頂点 $v_{2,0},v_{2,1},...,v_{2,9}$ のいづれかが選べます．
f:id:tatanaideyo:20141218020759p:plain
次に1桁目の頂点の中から頂点 $v_{1,2}$ を選んだとします．
この場合，2桁目の頂点は1以下の頂点 $v_{2,0},v_{2,1}$ の中からしか選ぶことが出来ません．
f:id:tatanaideyo:20141218020809p:plain
このように，N以下の整数という条件を加えると選べるパスは直前に選んだ頂点によって制限されます．
しかし，制限されていてもパスの総数はたくさんあるので愚直な方法は使えません．

ここで，桁DPを使用して計算量を削減していきます．
動的計画法とはhttp://www-or.amp.i.kyoto-u.ac.jp/~yagiura/papers/surikagaku200212.pdfで次のように書かれています．

動的計画法は，解の列挙にあたって，多くの場合を１つの状態にまとめて列挙の手間を削減するというアイデアに基づいている．

ここで，解（パス）の列挙にあたって1つの状態にまとめることが出来るのかを見ていきます．
N=9999，D=4で具体的に見ていきます．
3桁目までの頂点を選んだパス「111」と「210」を考えます．
この時のそれぞれのパスの重み和は3となり等しくなります．
したがって，パス「111」で4桁目を選んだ時のパスの重み和がDの倍数となるパスの総数と，
パス「210」で4桁目を選んだ時のパスの重み和がDの倍数となるパスの総和は等しくなります．
f:id:tatanaideyo:20141218023400p:plain

このように，i桁目までのパスで重みの和が等しいパスは残りのL-1桁目までの分岐するすべてのパスの総数が等しくなります．
なので，N以下という制限（パスの制限）が無い場合は必要な状態はi桁目とそこまでの各桁の和の2つとなります．
また，求めるのは各桁の和がDの倍数となるパスの総数なので，mod Dをとって状態数を減らすことが出来ます．

次に，N以下という制限（パスの制限）は先ほどのパスの制限と同様に考えます．
すなわち，直前の頂点でパスの制限を受けているか受けていないかによって選べる頂点が異なってきます．
これは，ソースコードを見たほうが分かりやすいと思います．
桁DPの漸化式もソースコードを見たほうが分かりやすいと思います．
また，0は任意のDの倍数となり答えにカウントされるので答えから1引いてます．

#include <bits/stdc++.h>

using namespace std;

typedef long long  ll;

const int MOD = 1000000007;
int D;
string N;
// dp[pos][sum][sml] := pos桁目まで見た時の(各桁の和 mod D)がsumで
//                      パスに制限があるかどうか（sml=0ならある，sml=1ならない）
int dp[10001][101][2];

int Solve()
{
    const int len = N.size();
    dp[0][0][0] = 1;

    for (int pos = 0; pos < len; ++pos) {
        for (int sum = 0; sum < D; ++sum) {
            for (int sml = 0; sml <= 1; ++sml) {
                if (!dp[pos][sum][sml]) // ここまでのパスが存在しない場合
                    continue;

                if (sml == 1) {// 次へのパスに制限が無い場合
                    int lim = 10;
                    for (int d = 0; d < lim; ++d)
                        (dp[pos + 1][(sum + d) % D][1] += dp[pos][sum][1]) %= MOD;
                }
                else { // 次へのパスに制限がある場合
                    int lim = static_cast<int>(N[pos] - '0');
                    for (int d = 0; d < lim; ++d)
                        (dp[pos + 1][(sum + d) % D][1] += dp[pos][sum][0]) %= MOD;
                    (dp[pos + 1][(sum + lim) % D][0] += dp[pos][sum][0]) %= MOD;
                }
            }
        }
    }

    // Dの倍数で制限のある場合と制限のない場合の和が答え
    int ans = (dp[len][0][0] + dp[len][0][1]) % MOD;
    return (ans + MOD - 1) % MOD;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> D >> N;
    cout << Solve() << endl;

    return 0;
}

桁DPを使う他の問題に次の問題があります．

D: 禁止された数字 - AtCoder Beginner Contest #007 | AtCoder

同様のやり方で解くことが出来ますが，状態と状態遷移が多少異なります．
ソースコードを載せとくので参考程度にどうぞ．

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll dp[20][10][2];               // dp[pos][i][sml] : = pos桁目の数字がiで制限があるか
                               // sml = 0なら制限あり，sml=1なら制限無し

// n以下で4と9を含まない数の個数
ll Count(ll n)
{
    if (n == 0)
        return 0;

    int len = log10(n) + 1;     // nの桁数
    int num[len];               // nのi-1桁目はnum[i]

    // nを配列numに変換
    for (int i = 0; i < len; ++i) {
        num[len - i - 1] = n % 10;
        n /= 10;
    }

    memset(dp, 0, sizeof(dp));
    dp[0][0][0] = 1;

    for (int i = 0; i < len; ++i) {
        for (int j = 0; j < 10; ++j) {
            if (j == 4 || j == 9)
                continue;
            for (int k = 0; k <= 1; ++k) {
                if (!dp[i][j][k])
                    continue;

                if (k == 0) { // 制限がある場合
                    int lim = num[i];
                    for (int l = 0; l < lim; ++l) {
                        if (l == 4 || l == 9)
                            continue;
                        dp[i + 1][l][1] += dp[i][j][0];
                    }
                    dp[i + 1][lim][0] += dp[i][j][0];
                }
                else {          // 制限が無い場合
                    for (int l = 0; l < 10; ++l) {
                        if (l == 4 || l == 9)
                            continue;
                        dp[i + 1][l][1] += dp[i][j][1];
                    }
                }
            }
        }
    }

    ll res = 0;
    for (int i = 0; i < 10; ++i)
        if (i != 4 && i != 9)
            res += (dp[len][i][0] + dp[len][i][1]);

    // 0もカウントされているので答えから引く
    return res - 1;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll a, b;
    cin >> a >> b;

    cout << (b - a + 1) - (Count(b) - Count(a - 1)) << endl;

    return 0;
}