Title Link: https://cn.vjudge.net/contest/163023#problem/D
Abstract: the number of 49 numbers in the range of 1-N is required
Problem analysis: there are three ways to do the second problem of digital dp.
The first one (I think of it):
Find out the number excluding 49 in the range of 1~n, then subtract the number excluding 49 from the total number and add one (minus one more 0)
The code is as follows:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int data[30];
ll dp[30][2];

ll dfs(int pos, int pre, bool limit)
{
    if(pos == -1) return 1;
    if(!limit && dp[pos][pre == 4])
    {
        return dp[pos][pre == 4];
    }
    int up = limit ? data[pos] : 9;
    ll ans = 0;
    for(int i = 0; i <= up; i++)
    {
        if(i == 9 && pre == 4) continue;
        ans += dfs(pos - 1, i, limit && i == data[pos]);
    }
    if(!limit) return dp[pos][pre == 4] = ans;
    return ans;
}

ll solve(ll n)
{
    memset(dp, 0, sizeof(dp));
    int pos = 0;
    while(n)
    {
        data[pos++] = n % 10;
        n /= 10;
    }
    ll ans = dfs(pos - 1, -1, true);
    return ans;
}

int main()
{
    ll n;
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%lld", &n);
        printf("%lld\n", n - solve(n) + 1);
    }
    return 0;
}

The second method:
Suppose n is 123456. When dfs reaches 049, it is obvious that the last three bits can be placed in any number. There are 10 * 10 * 10 placement methods. This is the case of! limit. When n is 49123, we run to 49
_There are only 123 + 1 methods at the back. So as long as we mark the limit and preprocess the unlimited situation, we can easily calculate the result.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll dp[30][2], kind[30], n;
int data[30];

ll dfs(int pos, int pre, bool limit)
{
    if(pos == -1) return 0;
    if(!limit && dp[pos][pre == 4]) return dp[pos][pre == 4];
    int up = limit ? data[pos] : 9;
    ll ans = 0;

    for(int i = 0; i <= up; i++)
    {
        if(pre == 4 && i == 9)
        {
            ans = ans + (limit ? ((n % kind[pos]) + 1) : kind[pos]);
        }
        else ans += dfs(pos - 1, i, limit && i == data[pos]);
    }
    if(!limit)
    return dp[pos][pre == 4] = ans;
    return ans;
}

ll solve(ll k)
{
    int pos = 0;
    memset(dp, 0, sizeof(dp));
    while(k)
    {
        data[pos++] = k % 10;
        k /= 10;
    }

    return dfs(pos - 1, -1, true);
}

int main()
{
    int t, i;
    kind[0] = 1;
    for(i = 1; i <= 18; i++)
        kind[i] = kind[i - 1] * 10;

    scanf("%d", &t);
    while(t--)
    {
        scanf("%lld", &n);
        printf("%lld\n", solve(n));
    }
}

The third method:
It's the traditional digital dp. At that time, it was so bad that I couldn't think of it..

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll dp[30][30][2], n;
int data[30];

ll dfs(int pos, int pre, bool sta, bool limit)
{
     if(pos == -1 && sta) return 1;
     if(pos == -1 && !sta) return 0;

     if(!limit && dp[pos][pre == 4][sta]) return dp[pos][pre == 4][sta];
     int up = limit ? data[pos] : 9;
     ll ans = 0;

     for(int i = 0; i <= up; i++)
     {
         if(pre == 4 && i == 9) ans += dfs(pos - 1, i, true, limit && i == data[pos]);
         else ans += dfs(pos - 1, i, sta/*notesHere it is. sta,Instead of false, There was a mistake before.*/, limit && i == data[pos]);
     }

     if(!limit) return dp[pos][pre][sta] = ans;
     return ans;
}

ll solve(ll k)
{
    int pos = 0;
    memset(dp, 0, sizeof(dp));
    while(k)
    {
        data[pos++] = k % 10;
        k /= 10;
    }
    return dfs(pos - 1, -1, false, true);
}

int main()
{
    int t, i;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%lld", &n);
        printf("%lld\n", solve(n));
    }
}