桁DP絶対一行で遷移するマン

　桁 DP のややこしい点は、遷移の上限を場合分けしなければいけない点だと思います。具体的には、以下のような分岐を辿ります。（その桁の上限の数を $A_i$ とします）

 - 余裕がある　→　$0\sim9$ まで遷移可能
 - 余裕がない　→　$0\sim A_i$ まで遷移可能 
   - 次の遷移は $A_i$ 未満か？　→　余裕ができる
   - 次の遷移は $A_i$ か？　→　余裕がないまま

　なので、コードの可読性を重視すると以下のような感じになると思います。
 
 　説明のためのシンプルな例として、「$N$ 以下の数を桁DPで求める」というコードを書きます。

 ```c++
    vector<vector<ll>> dp(71,vector<ll>(2));
    dp[0][0] = 1;
    rep(i, 70)
    {
        rep(next, 10)
        {
            dp[i + 1][1] += dp[i][1];
        }
        rep(next, a[i] + 1)
        {
            if (next < a[i])
            {
                dp[i + 1][1] += dp[i][0];
            }
            else
            {
                dp[i + 1][0] += dp[i][0];
            }
        }
    }
```

　しかし、できれば、

 ```c++
     rep(...) // 何らかのループ
     {
         rep(...) // 何らかのループ
         {
             // 何らかの一行の処理
         }
     }
```

　という形で書けた方が助かる。なぜなら、何か変更があった時に、手を加えるところがひとつで済むからです。それに、ループの範囲自体が変わるよりも、ループは同じだけど、適用される操作によって違いが出ると考えた方が、見通しがいい。

# 基本形

　結論として、以下のように書けます。

 ```c++
    rep(i, 70)
    {
        rep(small, 2)
        {
            rep(next, 10)
            {
                dp[i + 1][small || (next < a[i])] += dp[i][small] * (small || (next <= a[i]));
            }
        }
    }
```

- `i` どの桁まで見たか
- `small` 余裕があるか

　式の左に出てくる不等号が `<`、式の右に出てくる不等号が `<=` であることに注意です。

 　これが基本形になります。
  
  　後はこの式に付加情報を足すだけで、基本的な桁 DP を一行で解くことができます。

   ## ABC-C 007

   https://atcoder.jp/contests/abc007/tasks/abc007_4

```c++
    rep(i, 70)
    {
        rep(contains, 2)
        {
            rep(small, 2)
            {
                rep(next, 10)
                {
                    dp[i + 1][contains || next == 4 || next == 9][small || (next < a[i])] += dp[i][contains][small] * (small || (next <= a[i]));
                }
            }
        }
    }
```

- `i` どの桁まで見たか
- `contains` $4$ か $9$ のいずれかを少なくともひとつ含むか
- `small` 余裕があるか

## ナベアツ数

　みんな大好きナベアツ数も一行で遷移することができます。

https://paiza.io/projects/RHH3G_y73HwVCADu3CWHVw

```C++
    rep(i, 70)
    {
        rep(mod, 3)
        {
            rep(contains, 2)
            {
                rep(small, 2)
                {
                    rep(next, 10)
                    {
                        dp[i + 1][(mod + next) % 3][(next == 3) || contains][small || (next < a[i])] += dp[i][mod][contains][small] * (small || (next <= a[i]));
                    }
                }
            }
        }
    }
```

- `i` どの桁まで見たか
- `mod` $3$ で割ったあまり
- `contains` $3$ を少なくともひとつ含むか
- `small` 余裕があるか

# Leading Zero

　桁 DP では、leading zero を単位元として **扱ってはいけない** 場合は対策をする必要があります。つまり、「$321$」を「$...000321$」として扱うとバグが出てしまうような場合です。

  https://atcoder.jp/contests/abc161/tasks/abc161_d

  　具体的にはこういう問題など。

　さて、この場合の基本的な遷移はどうなるか。

 - 余裕がある　→　$0\sim9$ まで遷移可能
 - 余裕がない　→　$0\sim A_i$ まで遷移可能 
   - 次の遷移は $A_i$ 未満か？　→　余裕ができる
     - 次の遷移は $0$ か？　→　leading zero 継続
     - 次の遷移は $0$ 超過か？　→　leading zero 離脱
   - 次の遷移は $A_i$ か？　→　余裕がないまま
     - 次の遷移は $0$ か？　→　leading zero 継続
     - 次の遷移は $0$ 超過か？　→　leading zero 離脱

　こうなります。皆様はすんなり理解できますか？　私はできません。

　結論から言うと、「leading zero から遷移する数を始めから計上しておく」ことが対策になります。通常の桁 dp だと、`dp[0]...[0] = 1` という「種」から増殖していくのが、先に dp の各表にそういう `1` が増えるので、個人的な感覚ですが「複数の種を先に撒いておく」というイメージがあります。

　つまり、dp テーブルに対して、先に以下のような種を撒いておきます。

```c++
    rep(i,m){
        if(i==0){
            for(int j=1;j<=a[0];j++){ // 1 始まりである点に注意
                dp[1][j<a[0]]++;    
            }
        }else{
            for(int j=1;j<=9;j++){
                dp[i+1][1]++;
            }
        }
    }
```

　これは、以下のような一行遷移でまとめることができます。

```c++
    rep(i,m){
        for(int j=1;j<10;j++){
            dp[i+1][i||(j<a[0])] += i||(j<=a[0]);
        }
    }
```

## 実装例

https://atcoder.jp/contests/abc161/submissions/61452114

# チートシート

　せっかくなのでチートシートを公開します。リーディングゼロ対応です。決め打ちにぶたんで小さい方から $K$ 番目の数を答える形にしています。初期状態だとただ自分の数を数えるだけですが、各自改造してください。

```c++:公開用：マクロなし
long long solve() {
    long long k;
    std::cin >> k;
    long long ng = 0;
    long long ok = 1e18; // 10^18

    // バイナリサーチで条件を満たす最小の値を探索
    while (abs(ng - ok) > 1) {
        long long mid = (ng + ok) / 2;

        // midを桁ごとに分解してvectorに格納
        std::vector<long long> a(20);
        long long copy = mid;
        for (int i = 0; i < 20; i++) {
            a[i] = copy % 10;
            copy /= 10;
        }
        // 末尾の0を削除
        while (!a.empty() && a.back() == 0) {
            a.pop_back();
        }
        // 桁を逆順に（自然な数値の並びにする）
        std::reverse(a.begin(), a.end());
        int m = a.size();

        // DPテーブルを定義
        using VI = std::vector<long long>;
        using VVI = std::vector<VI>;
        using VVVI = std::vector<VVI>;
        VVVI dp(m + 1, VVI(10, VI(2, 0))); // dp[桁][現在の数][smallerフラグ]

        // 初期条件：1桁目
        for (int i = 0; i < m; i++) {
            for (int j = 1; j < 10; j++) {
                dp[i + 1][j][i || (j < a[0])] += i || (j <= a[0]);
            }
            // 遷移
            for (int now = 0; now < 10; now++) {
                for (int small = 0; small < 2; small++) {
                    for (int next = 0; next < 10; next++) {
                        dp[i + 1][next][small || (next < a[i])] += 
                            dp[i][now][small] * (small || next <= a[i]);
                    }
                }
            }
        }

        // 合計を計算
        long long tmp = 0;
        for (int j = 0; j < 10; j++) {
            for (int small = 0; small < 2; small++) {
                tmp += dp[m][j][small];
            }
        }

        // バイナリサーチの更新
        if (tmp >= k) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    return ok;
}
```

```c++:自分用（マクロ有）
ll solve(){
    ll k;
    cin >> k;
    ll ng = 0;
    ll ok = 1e18;
    while(abs(ng-ok)>1){
        ll mid = ng+ok;
        mid /= 2;
        vector<ll> a(20);
        ll copy = mid;
        rep(i,20){
            a[i] = copy%10;
            copy /= 10;
        }
        while(a.back()==0){
            a.pop_back();
        }
        reverse(all(a));
        int m = a.size();
        using VI = vector<ll>;
        using VVI = vector<VI>;
        using VVVI = vector<VVI>;
        using VVVVI = vector<VVVI>;
        using VVVVVI = vector<VVVVI>;
        VVVI dp(m+1,VVI(10,VI(2)));
        rep(i,m){
            for(int j=1;j<10;j++){
                dp[i+1][j][i||(j<a[0])] += i||(j<=a[0]);
            }
            rep(now,10){
                rep(small,2){
                    rep(next,10){
                        dp[i+1][next][small||(next<a[i])] += dp[i][now][small]*(small||next<=a[i]);
                    }
                }
            }
        }
        ll tmp = 0;
        rep(j,10){
            rep(small,2){
                tmp += dp[m][j][small];
            }
        }
        if(tmp>=k){
            ok = mid;
        }else{
            ng = mid;
        }
    }
    return ok;
}
```