Digital dp trampling

Preface

What is digital DP? I used to think that this concept is very big. Recently, I've been doing nothing. It's amazing to learn it for a while.

Start with a simple question

hdu 2089 "Don't 62"

A number that contains'4'or'62' is unlucky. Given m,n, 0 < m < n < 10 ^ 6, the number of Geely numbers in the range of [m,n] is counted.

The data range of is relatively small, only 1 e6. Violence can also be solved theoretically. However, the range of subject data of digital dp is usually large, often reaching 1e18 or even larger. Violence law O(n) obviously has TLE. At this time, a time complexity approximation O(logn) algorithm is needed. If you think about it carefully, you can actually use exclusion. From high to low, the unqualified numbers in 0-1e6 are excluded in turn.
For example, the number of 4 is not included in 1-9999. The steps are as follows:
1. First exclude the number of the highest position in the six digits is 4, that is, 400000-499999. Only need to judge the highest position, it excludes 100,000 numbers.
2. Then exclude the number of Sub-high bits that are 4 (the default maximum bit is not 4), such as the highest bit is 140000-149999, a total of 10,000. Note that the first place can be 0, which is equivalent to considering 000000-099999 (beginners may not understand, after reading some questions that do not consider the leading 0 will understand).
3. Similarly, continue to exclude 4-digit, 3-digit, until the end.

Digital DP is a DP related to the number of bits. Each bit of a number is called a digit. A number has one digit, ten digits, one hundred digits and one thousand digits. Digital DP is used to solve problems related to digital operations, such as the sum of numbers in a certain interval, specific number problems, etc. The number range of these problems is usually too large to be solved violently, and an algorithm close to O(logn) must be used. Through DP pair of "digit" operations, the state of the calculated interval is recorded, which can be used for fast screening of numbers for subsequent calculation.
How can we solve this problem with digital DP? Digital DP generally has two methods, one is DP pretreatment mess, the other is memory DFS. The former is not suitable for template, while the latter is efficient, easy to remember and can be quickly started.

Digital DP Template

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[20][20];
int a[20];
ll n,m;
// pos: Currently to the next pre: what lead is the last digit: whether there is a leading 0 limit: whether there is an upper limit (parameters usually have pos and limit, whether there is lead to see the title requirements, in addition to other parameters may be added)
ll dfs(int pos,int pre,bool lead,bool limit){
    if(pos == 0) return 1; //After searching, return 1. Here is usually return 1, but there are some questions with restrictions. When returning, we should judge whether the restrictions are met or not.
    if(!lead && !limit && dp[pos][pre] != -1) return dp[pos][pre]; //Memorization
    int up = limit? a[pos] : 9;  //If there is an upper bound, then it cannot exceed it.
    ll ans = 0;
    for(int i = 0;i <= up;i++){
        if(lead) ans += dfs(pos - 1,i,lead && i == 0,limit && i == a[pos]);
        else{
            if() continue;
            ans += dfs(pos - 1,i,lead && i == 0,limit && i == a[pos]);
        }
    }
    if(!lead && !limit) dp[pos][pre] = ans;
    return ans;
}
ll solve(ll x){
    int len = 0;
    while(x){   //Dismantling, a[i] denotes the number's number I
        a[++len] = x % 10;
        x /= 10;
    }
    memset(dp,-1,sizeof(dp)); //Initialize dp arrays
    return dfs(len,0,true,true); //Enumeration from High to Low
}
int main()
{
    cin >> n >> m;
    cout << solve(m) - solve(n - 1) << endl;
    return 0;
}

Here are some common questions for beginners

  • Why do we have to control the upper bound in dfs?
    To give a simple example, we require the number of numbers satisfying certain conditions in this interval [25,628], so that the number we enumerate must not exceed 628, because 628 is the upper bound. We enumerate from high to low, and all of the 100 places may be 0, 1, 2, 3, 4, 5, 6. When 100 digits enumerate 1 and 10 digits can enumerate 0-9, the enumeration equivalent to 10 digits is unrestricted (up to 9). However, if the 100-digit enumeration is 6, then the 10-digit enumeration can only be 0-2, because it cannot exceed 628. Similarly, if a hundred places enumerate 6 and ten places enumerate 2, then only 0-8 places can be enumerated.
  • Lead?
    Why can one hundred people enumerate zero? The reason is very simple. When a hundred digits equals zero, the number we enumerate is a double digit. Similarly, both a hundred digits and ten digits equals zero, which is equivalent to enumerating a single digit. However, this will bring about the influence of leading 0. In some topics, such as: windy number, which considers the relationship between two adjacent numbers, memory search will make mistakes. At this time, the parameter lead is very important. We can eliminate the influence by adding parameters.

Let's use the template to get rid of this topic in seconds.

Don't be 62

dp[pos][sta] denotes the number of numbers that satisfy the conditions when the first place of POS is 6(sta = 1), or not 6(sta = 0). Since whether the first place of the number is 6 will affect the answer, it is only necessary to divide the answer into two categories in statistics.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
ll dp[20][2];
int a[20];
int dfs(int pos,int pre,int sta,bool limit){
    if(pos == 0) return 1;
    if(!limit && dp[pos][sta] != -1) return dp[pos][sta];
    int up = limit?a[pos] : 9;
    int sum = 0;
    for(int i = 0;i <= up;i++){
        if(i == 4) continue;
        if(pre == 6 && i == 2) continue;
        sum += dfs(pos - 1,i,i == 6,limit && i == a[pos]);
    }
    if(!limit) dp[pos][sta] = sum;
    return sum;
}
int solve(int x){
    int len = 0;
    while(x){
        a[++len] = x % 10;
        x /= 10;
    }
    return dfs(len,-1,0,true);
}
int main(){
    memset(dp,-1,sizeof(dp));
    while(~scanf("%d %d",&m,&n) && n && m){
        cout << solve(n) - solve(m - 1) << endl;
    }
    return 0;
}

Blue Bridge Cup k Good Number

This problem defines a concept called "k good number", that is, the number of any two adjacent digits in the k-ary system can not be adjacent (that is, the difference can not be equal to 1), and then the number of K good numbers in the k-ary system of L-bit should be counted. The pitfall of this problem is to consider the influence of leading 0, such as the two digits in Quaternary system, 11,20 is good for k, but 32 is not good for K. But if we ask for a digit in the Quaternary system, the problem will arise. If there is no lead parameter, the number 1 will not be counted, because the default preamble is 0, and 0 and 1 are adjacent, at this time only need to add a judgment.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod = 1e9 + 7;
ll dp[105][105];
int k,l;
ll dfs(int pos,int pre,bool lead,bool limit){
    if(pos == 0) return 1;
    if(!lead && !limit && dp[pos][pre] != -1) return dp[pos][pre];
    int up = k - 1;
    ll ans = 0;
    for(int i = 0;i <= up;i++){
        if(lead) ans += dfs(pos - 1,i,lead && i == 0,limit && i == k - 1);
        else{
            if(abs(i - pre) == 1) continue;
            ans = (ans + dfs(pos - 1,i,lead && i == 0,limit && i == k - 1)) % mod;
        }
    }
    if(!lead && !limit) dp[pos][pre] = ans;
    return ans;
}
ll solve(int len){
    memset(dp,-1,sizeof(dp));
    return dfs(len,0,true,true);
}
int main()
{
    cin >> k >> l;
    cout << (solve(l) - solve(l - 1) + mod ) % mod << endl;
    return 0;
}

B-number hdu3652

This problem defines something called B number, which contains the string of "13" and can be divisible by 13. The difficulty is how to save the state divided by 13. In fact, it is very simple. Add a parameter tot to record the remainder, enumerate% 13 every time, and judge when pos=0.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[15][10][13][2];
int a[15];
ll n;
ll dfs(int pos,int pre,int tot,int ok,bool limit){
    if(pos == 0) return ok == 1 && tot == 0;
    if(!limit && dp[pos][pre][tot][ok] != -1) return dp[pos][pre][tot][ok];
    int up = limit? a[pos] : 9;
    ll ans = 0;
    for(int i = 0;i <= up;i++){
        if(pre == 1 && i == 3) ans += dfs(pos - 1,i,(tot * 10 + i) % 13,1,limit && i == a[pos]);
        else ans += dfs(pos - 1,i,(tot * 10 + i) % 13,ok,limit && i == a[pos]);
    }
    if(!limit) dp[pos][pre][tot][ok] = ans;
    return ans;
}
ll solve(ll x){
    int len = 0;
    while(x){
        a[++len] = x % 10;
        x /= 10;
    }
    return dfs(len,0,0,false,true);
}
int main()
{
    memset(dp,-1,sizeof(dp));
    while(~scanf("%lld",&n)) cout << solve(n) << endl;
    return 0;
}

The Number Thesis of Flower God

The question of is interesting. It is to count the sum(i) of 1 under each number binary, and then calculate the cumulative multiplication of sum(1) to sum(n).
We need to change our thinking. The upper limit of n is 1e18, which means that there are at most 50 digits in the binary system, that is to say, 50 digits at most. We count 1, 2 digits, 3 digits under the binary system, respectively. The number of fifty-one numbers is then optimized with a fast power, and the problem is solved.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e7 + 7;
ll dp[51][51][51];
int a[51];
ll ans[51];
ll n;
ll poww(ll x,ll y,ll p){
    ll ans = 1;
    while(y){
        if(y & 1) ans = ans * x % p;
        x = x * x % p;
        y >>= 1;
    }
    return ans;
}
//The upper bound of the number of 1 to be counted
ll dfs(int pos,int tmp,int tot,bool limit){
    if(pos == 0) return tmp == tot;
    if(!limit && dp[pos][tmp][tot] != -1) return dp[pos][tmp][tot];
    int up = limit? a[pos] : 1;
    ll sum = 0;
    for(int i = 0;i <= up;i++){
        sum += dfs(pos - 1,tmp + (i == 1),tot,limit && a[pos] == i);
    }
    if(!limit) dp[pos][tmp][tot] = sum;
    return sum;
}
ll solve(ll x){
    int len = 0;
    ll sum = 1;
    while(x){ //Take out each bit of the binary
        a[++len] = x & 1;
        x >>= 1;
    }
    memset(dp,-1,sizeof(dp));
    //Here's a clever optimization that counts the number of 1 in binary as i, and then fast power optimization.
    for(int i = 1;i <= len;i++){
        ans[i] = dfs(len,0,i,true);
        sum = sum * poww(i,ans[i],mod) % mod;
    }
    return sum;
}
int main()
{
    cin >> n;
    cout << solve(n) << endl;
    return 0;
}

Number Counting of Luogu 2602

The main idea of this question is to find the number of numbers 0-9 appearing in an interval. My general idea is that there are 1,2,1,3,1... The number of numbers, there are 1 2, 2 2,... One 9, two 9,... Number of numbers, and then cumulative, of course, there is a better way to solve the problem, the following is for reference only (pay attention to the treatment of leading 0, otherwise statistics 0 will be wrong)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[15][15][15];
int a[15];
ll ans[10][15];
ll total[10];
ll n,m;
int num;
//Leader 0 is the key!!
ll dfs(int pos,int now,int tot,bool lead,bool limit){
    if(pos == 0) return now == tot;
    if(!limit && !lead && dp[pos][now][tot] != -1) return dp[pos][now][tot];
    int up = limit? a[pos] : 9;
    ll sum = 0;
    for(int i = 0;i <= up;i++){
        if(lead && i == 0) sum += dfs(pos - 1,now,tot,true,limit && i == a[pos]);
        else sum += dfs(pos - 1,now + (i == num),tot,lead && i == 0,limit && i == a[pos]);
    }
    if(!limit && !lead) dp[pos][now][tot] = sum;
    return sum;
}
ll solve(ll x,bool ok){
    int len = 0;
    while(x){
        a[++len] = x % 10;
        x /= 10;
    }
    memset(dp,-1,sizeof(dp));
    memset(ans,0,sizeof(ans));
    for(int i = 0;i < 10;i++){
        num = i;
        for(int j = 1;j <= len;j++){
            ans[i][j] = dfs(len,0,j,true,true);
            if(ok) total[i] += ans[i][j] * j;
            else total[i] -= ans[i][j] * j;
        }
    }
}
int main()
{
    cin >> n >> m;
    solve(m,1);
    solve(n - 1,0);
    for(int i = 0;i < 10;i++) cout << total[i] << " ";
    return 0;
}

Logu 4999's annoying math homework

The purpose of the title is to find the sum of the numbers of each number in the l-r interval. Assuming that the number of len digits is total, the number of len digits will not exceed 9*len. We just need to enumerate statistics from small to large. The idea is the same as the above topic.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
int t;
ll n,m;
ll dp[20][180][180],ans[180];
int a[20];
//Location Current Members and Objectives and Upper Limits
ll dfs(int pos,int now,int tot,bool limit){
    if(pos == 0) return now == tot;
    if(!limit && dp[pos][now][tot] != -1) return dp[pos][now][tot];
    int up = limit? a[pos] : 9;
    ll sum = 0;
    for(int i = 0;i <= up;i++){
        sum += dfs(pos - 1,now + i,tot,limit && a[pos] == i);
    }
    if(!limit) dp[pos][now][tot] = sum;
    return sum;
}
ll solve(ll x){
    int len = 0;
    ll sum = 0;
    while(x){
        a[++len] = x % 10;
        x /= 10;
    }
    //Statistical data for each person and 1-9*len
    for(int i = 1;i <= 9 * len;i++){
        ans[i] = dfs(len,0,i,true);
        sum = (sum + i * (ans[i] % mod)) % mod;
    }
    return sum;
}
int main()
{
    scanf("%d",&t);
    memset(dp,-1,sizeof(dp));
    while(t--){
        scanf("%lld %lld",&n,&m);
        //Here subtraction to deal with!!!
        cout << (solve(m) - solve(n - 1) + mod) % mod << endl;
    }
    return 0;
}

The first blog of Burdock, if there is any mistake, please point it out.~~

Tags: C++

Posted on Wed, 21 Aug 2019 06:42:37 -0700 by NightCoder