论数位DP的食用方式

userId_undefined

不会C++的noah

荣耀黄金

2024-06-28 07:31:24

发布于：浙江

448阅读
0回复
0点赞
防剧透文本防剧透文本防剧透文本防剧透文本防剧透文本防剧透文本防剧透文本防剧透文本防剧透文本防剧透文本防剧透文本防剧透文本防剧透文本防剧透文本防剧透文本防剧透文本防剧透文本防剧透文本防剧透文本防剧透文本防剧透文本

-1-此文的诞生过程

在几个月的排位赛（#7）时，最后一题我在那想了半天，最后才想起来还有数位DP这一回事，于是提交，AC。
在比赛结束后，本来想着去题库找找题目练，结果却发现根本没有“数位DP”这一知识点，于是便有了这篇文章。

0-开始前的准备

本文须读者对一些普通的DP基础（如线性DP）有一定了解，并有一定基础。
如果连DP是什么都不知道，出门左转DP详解

1-数位DP解析

1.1- 数位DP的定义

"数位DP"，顾名思义就是一些关于数论，数位，运算的DP。
或者，你也可以理解为这是一种对一个整数位数的记忆化搜索。

1.2-数位DP的常用题型及时间复杂度

数位DP一般用于“给你一个[l,r][l,r]的区间，求此区间里有多少个符合条件的数（条件任意）/数和/数字出现数/平方……”，"对于一个（或多个）数字NN，求此数字的……（随机而变）"，这种题目的r,Nr,N一般都是≥1012\ge 10^{12}的，此时朴素的枚举不管是什么机子都会爆那当然，所以这就要用数位DP了。数位DP的主要思想大概是：

先采用前缀和思想，将求解[l,r][l,r]这个区间内的满足约束的数的数量，转化为[0,r][0,r]满足约束的数量 - 区间[0,l−1][0,l-1]满足约束的数量数位，然后将数字区间[l,r][l,r]中的数拆分为一个个数位，对于此数位进行数位上的dfsdfs。

数位：指如个位、十位、百位等，单个数码（比如十进制，此处就是指0−90-9）在数中所占据的一个位置。

时间复杂度大致为O(RN)O(RN)，这里的RR指的是进制，NN指的是数字的位数（一般情况下，R∈[2,10,16],12≤N≤1000R \in{[2,10,16]},12 \le N \le 1000）。

1.3-数位DP的流程

#include <bits/stdc++.h>
using namespace std;
int *[N],dp[N][N][2][……]……，……;//*:存n的数组，dp:记忆化/dp用(维数任意，但一般>=4;数字任意)
long long dfs(int pos,int cnt,bool limit,……){//pos:位数，cnt:题目限制数的数量/当前数的[按题目要求自定义]，limit:判断当前的极限（后边有用）
    long long ans=0;
    ……//自定义
    if (pos==len){
        ……//自定义
        return ……;//自定义
    }
    ……//自定义
    if (dp[pos][cnt][limit][……]……!=-1){
        return dp[pos][cnt][limit][……]……;//记忆化搜索
    }
    for (int i=0;i<=(limit?*[pos]:9);++i){//枚举当前位的所有可能数字
         ……//自定义
         ans+=dfs(pos+1,……,limit && ……,……);//自定义
    }
    dp[pos][cnt][limit][……]……=ans;//记忆
    return ans;//返回
}
long long f(long long x){//x一般代指r
    len=0;
    memset(dp,-1,sizeof dp);
    memset(*,0,sizeof *);//初始化
    while (x){
        *[len++]=x%10;
        x/=10;
    }//放入n
    reverse(*,*+len);//这里由于之前插入在*数组的n是倒序的，所以要反转一下
    ……//自定义
    return dfs(……);//自定义
}
int main(){
    ……//自定义
}

⋇:\divideontimes:如果以上内容还没有懂得话，那就多看几遍。

2-Problems

由于ACGO上没有题，所以选了一些洛谷题

2.1-洛谷P2602

数位DP模板题，注意要判断前导零的情况。
Code:

#include <bits/stdc++.h>
using namespace std;
long long *[101],dp[50][50][50][50],len,digit;//digit:判断的数字
long long dfs(int pos,int cnt,bool limit,bool lold){
    long long ans=0;
    if (pos==len){
        return cnt;
    }
    else if (dp[pos][cnt][limit][lold]!=-1){
        return dp[pos][cnt][limit][lold];
    }
    for (int i=0;i<=(limit?*[pos]:9);++i){
        if (lold && i==0){
            ans+=dfs(pos+1,cnt,limit && i==*[pos],1);//如果有前导零，则cnt不加
        }else{
            ans+=dfs(pos+1,cnt+(i==digit),limit && i==*[pos],0);
        }
    }
    dp[pos][cnt][limit][lold]=ans;
    return ans;
}
long long f(long long x){
    len=0;
    memset(dp,-1,sizeof dp);
    memset(*,0,sizeof *);
    while (x){
        *[len++]=x%10;
        x/=10;
    }
    reverse(*,*+len);
    return dfs(0,0,1,1);
}
int main(){
    long long x,y;
    cin>>x>>y;
    for (int i=0;i<=9;++i){
        digit=i;
        long long l=f(x-1),r=f(y);
        cout<<r-l<<" ";
    }
}

2.2-洛谷-P4999

这题简单求总数，算是双倍经验了
正解我就不贴了（前边改改就行），还是看一下我同机房大神写的偏解吧（也能AC,原理？鬼才知道）
Code

#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
unsigned long long run(unsigned long long x)
{
    unsigned long long ret=0;
    unsigned long long M = 1e9 + 7;
    unsigned long long m=1;
    while (m<=x) {
        unsigned long long l=x%m;
        int k=(x/m)%10;
        for(long long i=1;i<=9;++i){
            ret += (x/(m*10))*m*i;
           // cout<<"B"<<ret<<endl;
            ret %= M;
        }
       // cout<<"*"<<ret<<endl;
        for(int i=1;i<=k-1;++i){
            ret += m*i;
            ret %= M;
        }
        ret += (l+1)*k;
        ret %= M;
        m *= 10;
        //cout<<m<<" "<<ret<<endl;
    }
    return ret;
}
int main(){
    int t;
    // cout<<run(1e5)<<endl;
    unsigned long long M = 1e9 + 7;
    cin>>t;
    while (t--){
        unsigned long long x,y,sum=0;
        cin>>x>>y;
        unsigned long long l=run(x-1),r=run(y);
        cout<<(M+r-l)%M<<endl;
    }
}

(作者说：看不懂？问kimi/chat GPT4去)

2.3-洛谷P1831

我们可以枚举支点的位置，对于每个满足条件的数，它所对应的支点是唯一的，原因是如果将支点右移，左边减去右边的差将严格单调增加。statestate表示力矩和（支点左边加支点右边），所以当state<0state<0时，当前这个数不满足以ii为支点成为杠杆数的情况，返回00。但当state=0state=0时并不能就ans+1ans +1了，因为当前枚举的位置可能还没枚举完。
枚举好支点，问题就转化为：求[1,x][1,x]中，以第ii位为支点的杠杆数的个数。
Code:

#include <bits/stdc++.h>
using namespace std;
long long *[101],dp[50][50][2500],len;
long long dfs(int pos,int pront,int mos,bool limit){
    long long tmp=0;
    if (pos==0){
        return mos==0;
    }
    if (mos<0){
        return 0;
    }
    if (!limit && dp[pos][pront][mos]!=-1){
        return dp[pos][pront][mos];
    }
    for (int i=0;i<=(limit?*[pos]:9);i++){
        tmp+=dfs(pos-1,pront,mos+(i*(pos-pront)),limit && (i==(limit?*[pos]:9)));
        //cout<<tmp<<endl;
    }
    if (!limit){
        dp[pos][pront][mos]=tmp;
    }
    return tmp;
}
long long f(long long x){
    len=0;
    long long ans=0;
    memset(dp,-1,sizeof dp);
    memset(*,0,sizeof *);
    while (x){
        *[++len]=x%10;
        x/=10;
    }
    for (int i=1;i<=len;i++){
        ans+=dfs(len,i,0,1);
    }
    return ans-len;
}
int main(){
    long long x,y;
    cin>>x>>y;
    long long l=f(x-1),r=f(y);
    cout<<r-l<<endl;
}

2.4-ACGO-(排位赛#7)T6

很简单，cnt记录此数有多少个非零位，等pos到len时在判断
Code:

#include <bits/stdc++.h>
using namespace std;
const int MOD=998244353;
long long dp[111][111][3][3],len;
int *[111];
int k;
long long dfs(int pos,int cnt,bool limit,bool lold){
    long long ans=0;
    //cout<<pos<<" "<<cnt<<" "<<limit<<" "<<lold<<" "<<*[pos]<<" "<<len<<" "<<k<<" "<<(limit?*[pos]:9)<<endl;
    if (pos==len && cnt==k){
        return 1;
    }else if (pos==len){
    	return 0;
	}else if (dp[pos][cnt][limit][lold]!=-1){
        return dp[pos][cnt][limit][lold]%MOD;
    }
    for (int i=0;i<=(limit?*[pos]:9);++i){
    	//cout<<i<<endl;
        if (lold && i==0){
            ans+=dfs(pos+1,cnt,limit && i==*[pos],1)%MOD;
        }else{
            ans+=dfs(pos+1,cnt+(i!=0),limit && i==*[pos],0)%MOD;
        }
    }
    dp[pos][cnt][limit][lold]=ans;
    return ans%MOD;
}
long long f(string n){
	len=0;
	memset(dp,-1,sizeof dp);
    memset(*,0,sizeof *);
    len=n.size();
    for (int i=0;i<len;++i){
    	*[i]=n[i]-'0';
	}
    return dfs(0,0,1,1)%MOD;
}
int main(){
    int t;
    cin>>t;
    while (t--){
    	k=0;
    	string n;
    	cin>>n>>k;
    	cout<<f(n)%MOD<<endl;
	}
}

（注：代码部分的*是a,望周知）

3-结尾

数位DP的讲解到此结束了，很高兴大家能听我讲解。
下次再会（别走，我写了这么多，能否给个精选/赞/回复）
最后，打个我们团的链接：
中国团，大佬都在里边

userId_undefined
去预览
0/2000

全部评论 11

热门讨论