数位DP学习笔记

文章目录

数位DP
- 大量例题
- - P4999 - 烦人的数学作业
  - HDU2089 - 不要62
  - P6218 - [USACO06NOV] Round Numbers S
  - P2602 - [ZJOI2010]数字计数
  - P2657 - [SCOI2009] windy 数
  - P4317 - 花神的数论题
  - CF855E Salazar - Slytherin's Locket
  - SP10606 - BALNUM - Balanced Numbers
  - P4124 - [CQOI2016]手机号码
  - CF1073E - Segment Sum
  - CF55D - Beautiful numbers
  - P4127 - [AHOI2009]同类分布
  - P3413 - SAC#1 - 萌数
  - - ！！

数位DP

大量例题

P4999 - 烦人的数学作业

题目描述：

给出 $L, R$ ，求在 $[L, R]$ 中的所有整数的数位和的和（例如 $123$ 的数位和= $1 + 2 + 3 = 6$ ）

$\leq L \leq R \leq 10^{18}$

思路： 板子
我们搜的话只需要记录当前位数位 $p o s$ 和数位和 $s u m$ 即可，因为这道题我们不在乎数的具体组成结构，只在乎某一段在值域上的总体情况。比如我们当前这一段数位和为 $s u m$ ，我们最后变成 $a n s$ ，中间加了一段数位和为 $a n s - s u m$ 的，显然前后两端不管构造如何，都不影响，只有值域（数位和）能影响

code:

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int p=1e9+7;

int a[25],len=0;
ll dp[200][25];


ll dfs(bool limit,int sum,int pos){
    if(pos>len) return sum;
    if(!limit&&~dp[sum][pos]) return dp[sum][pos];
    int cur=limit?a[len-pos+1]:9;
    ll res=0;
    for(int i=0;i<=cur;i++){
        res=(res+dfs(i==cur&&limit,sum+i,pos+1))%p;
    }
    if(!limit) dp[sum][pos]=res;
    return res;
}

ll part(ll x){
    len=0;
    while(x) a[++len]=x%10,x/=10;
    memset(dp,-1,sizeof dp);
    return dfs(1,0,1);
}

int main(){
    int t;
    cin>>t;
    while(t--){
        ll l,r;
        cin>>l>>r;
        cout<<(part(r)-part(l-1)+p)%p<<endl;
    }
    return 0;
}

HDU2089 - 不要62

题目描述：

定义包含 $4$ 或 $62$ （其中 $62$ 必须为连号）为不吉利的数字，给出多组 $n$ 和 $m$ ，求 $[n, m]$ 中吉利的数字个数

$\leq n \leq m \leq 10^6$

思路：
这里我选择搜不吉利的数个数然后减掉，实际上直接搜吉利个数更简单，只需要对 $4$ 和 $62$ 的情况剪枝即可，接着就是求数的个数。。

code:

int n,m;
int len=0,a[15];
int dp[20][25][2];

int dfs(int pre,int pos,int sum,bool vis,bool limit){    
    if(pos>len) return sum;
    if(!limit&&~dp[pre][pos][vis]) return dp[pre][pos][vis];
    int cur=limit?a[len-pos+1]:9;
    int res=0;
    for(int i=0;i<=cur;i++){
        bool f=0;
        int add=0;
        if((i==4)||(pre==6&&i==2)) f=1;
        if((!vis)&&f) add=1; 
        res+=dfs(i,pos+1,sum+add,vis||add,limit&&i==cur);
    }
    if(!limit) dp[pre][pos][vis]=res;
    return res;
}

int part(int x){
    memset(dp,-1,sizeof dp);
    len=0;
    while(x) a[++len]=x%10,x/=10;
    return dfs(0,1,0,0,1);
}

int main(){ 
    while(cin>>n>>m){
        if(n==0&&m==0) return 0;
        cout<<m-n+1-part(m)+part(n-1)<<endl;
    }
    return 0;
}

P6218 - [USACO06NOV] Round Numbers S

题目描述：

如果一个正整数的二进制表示中， $0$ 的数目不小于 $1$ 的数目，那么它就被称为 「圆数」。
计算区间 $[l, r]$ 中有多少个 「圆数」。
$\leq l,r \leq 2 \cdot 10^9$

思路：
先把数拆分成二进制，然后记录 $0, 1$ 的个数即可，注意前导零
这里我没用用前导零标记，而是直接用 $c n t 1$ 的个数判断当前是不是前导零

code:

int l,r;
int len=0,a[15];
int dp[35][35][35];

int dfs(int pos,int cnt0,int cnt1,bool limit){
    if(pos>len) return cnt0>=cnt1;
    if(!limit&&~dp[pos][cnt0][cnt1]) return dp[pos][cnt0][cnt1];
    int cur=limit?a[len-pos+1]:1;
    int res=0;
    for(int i=0;i<=cur;i++){
        res+=dfs(pos+1,cnt0+(i==0&&(cnt1!=0)),cnt1+(i==1),limit&&i==cur);
    }
    if(!limit) dp[pos][cnt0][cnt1]=res;
    return res;
}

int part(int x){
    len=0;
    memset(dp,-1,sizeof dp);
    while(x) a[++len]=x&1,x>>=1;
    return dfs(1,0,0,1);
}

int main(){
    cin>>l>>r;
    if(l) cout<<part(r)-part(l-1)<<endl;
    else cout<<part(r)<<endl;
}

P2602 - [ZJOI2010]数字计数

题目描述：

给定两个正整数 $a$ 和 $b$ ，求在 $[a, b]$ 中的所有整数中，每个数码 $(d i g i t)$ 各出现了多少次

$\leq a \leq b \leq 10^{12}$

思路： 板子，每个数码分开搜就行

code:

int len,a[30];
ll dp[205][30];
int dig;

ll solve(int pos,bool limit,ll sum,bool lead){
    if(pos>len) return sum;
    if(!limit&&!lead&&~dp[sum][pos]) return dp[sum][pos];
    int cur=limit?a[len-pos+1]:9;
    ll res=0;
    for(int i=0;i<=cur;i++){
        if(lead&&!i) res+=solve(pos+1,limit&&i==cur,sum,1);
        else if(lead&&i) res+=solve(pos+1,limit&&i==cur,sum+(i==dig),0);
        else res+=solve(pos+1,limit&&i==cur,sum+(i==dig),0);
    }
    if(!lead&&!limit) dp[sum][pos]=res;
    return res;
}

ll part(ll x){
    memset(dp,-1,sizeof dp);
    len=0;
    while(x) a[++len]=x%10,x/=10;
    return solve(1,1,0,1);
}

int main(){
    ll l,r;
    cin>>l>>r;
    for(int i=0;i<=9;i++){
        dig=i;
        cout<<part(r)-part(l-1)<<" ";
    }
    puts("");
    return 0;
}

P2657 - [SCOI2009] windy 数

题目描述：

不含前导零且相邻两个数字之差至少为 $2$ 的正整数被称为 $w i n d y$ 数。
问在 $[L, R]$ 之间有多少 $w i n d y$ 数？

思路：
这题需要判断前导零，只有进入有效数位只有才开始前后数位差的统计

code:

int L,R;
int len=0,a[15];
int dp[15][10][15];

int dfs(int pos,int pre,int d,bool lead,bool limit){
    if(d<2) return 0;
    if(pos>len) return 1;
    if(!limit&&!lead&&~dp[pos][pre][d]) return dp[pos][pre][d];
    int cur=limit?a[len-pos+1]:9,res=0;
    for(int i=0;i<=cur;i++){
        if(lead&&!i) res+=dfs(pos+1,pre,d,1,limit&&(i==cur));
        else if(lead&&i) res+=dfs(pos+1,i,d,0,limit&&(i==cur));
        else res+=dfs(pos+1,i,min(d,abs(i-pre)),0,limit&&(i==cur));
    }
    if(!limit&&!lead) dp[pos][pre][d]=res;
    return res;
}   

int part(int x){
    memset(dp,-1,sizeof dp);
    len=0;
    while(x) a[++len]=x%10,x/=10;
    return dfs(1,0,10,1,1);
}

int main(){
    scanf("%d %d",&L,&R);
    printf("%d\n",part(R)-part(L-1));
    return 0;
}

P4317 - 花神的数论题

题面描述：

定义 $s u m (i)$ 代表 $i$ 的二进制表示中 $1$ 的个数，计算 $\prod_{i=1}^nsum(i)$ 对 $1 e 7 + 7$ 取模的结果

$\leq n \leq 10^{15}$

思路：

做法 $1$ ：分别计算二进制中 $1$ 的个数为 $i$ 的数的个数，然后用快速幂计算答案 $\prod i^{cnt_i}$ ，注意模数是非质数，在统计 $cnt_i$ 不可取模

做法 $2$ ：直接搜答案，返回的是定义状态下的乘积

code1:

const int p=10000007;

ll n,k;
int len=0,a[60];
ll dp[65][65];

ll dfs(int pos,int cnt,bool limit){
    if(cnt>k) return 0;
    if(pos>len) return cnt==k;
    if(!limit&&~dp[pos][cnt]) return dp[pos][cnt];
    int cur=limit?a[len-pos+1]:1;
    ll res=0;
    for(int i=0;i<=cur;i++){
        res+=dfs(pos+1,cnt+(i==1),limit&&(i==cur));
    }
    if(!limit) dp[pos][cnt]=res;
    return res;
}


ll solve(){
    memset(dp,-1,sizeof dp);
    return dfs(1,0,1);
}

ll qpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}

int main(){ 
    cin>>n;
    while(n) a[++len]=n&1,n>>=1;
    ll ans=1;
    for(int i=1;i<=60;i++){
        k=i;
        ll tmp=solve();
        ans=ans*qpow(i,tmp)%p;
    }
    cout<<ans<<endl;
    return 0;
}

code2:

ll dfs(int pos,int cnt,bool limit){
    if(pos>len) return max(1,cnt);
    if(!limit&&~dp[pos][cnt]) return dp[pos][cnt];
    int cur=limit?a[len-pos+1]:1;
    ll res=1;
    for(int i=0;i<=cur;i++){
        res=res*dfs(pos+1,cnt+(i==1),limit&&(i==cur))%p;
    }
    if(!limit) dp[pos][cnt]=res;
    return res;
}

CF855E Salazar - Slytherin’s Locket

题目描述：
存在 $q$ 组询问
每次给出 $l, r$ ，求 $[l, r]$ 之间转成 $b$ 进制后，所有数码都出现偶数次的数的个数

$\leq l \leq r \leq 10^{18},1 \leq q \leq 10^5$

思路：
怎么搜很显然，用一个 $m a s k$ 变量记录每个数码出现的奇偶即可，注意前导零。

但是对于 $q$ 组询问，每次都清空显然复杂度高达 $\cdot2^b logn)$ ，这里可以使用一个小优化，就是数组多一维来记录每个进制下的状态的方案数。复杂度 $\cdot 2^bb logn)$

这里要注意这种记录方式 $p o s$ 这一位初始要赋值为 $l e n$ 而不是 $1$ .
举个例子 $12123$ 和 $12$ ，如果用第一种方式去搜，显然搜到两者搜到第二位是状态完全相同，记忆化的东西也相同，而实际上后面的东西完全不同。因此我们必须要从高到底记录长度

可以按照按 $b$ 排序，然后每次 $b$ 变了就清空 $d p$ 数组，这样空间省一个 $b$ ，时间上多一个小常数，非常划算

code:

int q,b,len=0;
int a[65];
ll l,r,dp[15][65][1<<12];

ll dfs(int pos,int mask,bool lead,bool limit){
    if(!pos) return mask==0;
    if(!lead&&!limit&&~dp[b][pos][mask]) return dp[b][pos][mask];
    int cur=limit?a[pos]:b-1;
    ll res=0;
    for(int i=0;i<=cur;i++){
        if(lead&&!i) res+=dfs(pos-1,0,1,limit&&(i==cur));
        else res+=dfs(pos-1,mask^(1<<i),0,limit&&(i==cur));
    }
    if(!lead&&!limit) dp[b][pos][mask]=res;
    return res;
}

ll solve(ll x){
    len=0;
    while(x) a[++len]=x%b,x/=b;
    return dfs(len,0,1,1);
}

int main(){
    memset(dp,-1,sizeof dp);
    scanf("%d",&q);
    while(q--){
        scanf("%d %lld %lld",&b,&l,&r);
        printf("%lld\n",solve(r)-solve(l-1));
    }
    return 0;
}

SP10606 - BALNUM - Balanced Numbers

题目描述：
定义平衡数：当且仅当对于所有出现过的数位（即 $0 - 9$ ），每个偶数出现奇数次，每个奇数出现偶数次。

给定 $L, R$ ，请统计出 $[A, B]$ 内所有平衡数的个数。

$\leq L \leq R \leq 10^{19}$

思路：
搜的时候用两个变量分别表示各个数码有没有出现过，出现了奇数次还是偶数次，这样我们就可以很轻易的 $c h e c k$ 最后这个数是否为平衡数。

由于两个数乘积过大，我们显然可以将两个数 $h a s h$ 成一个数。并且可以发现这样大约 $10^6$ 个数对有很多都是不合法的，比如某个数码可能没有出现过，那么它在第二个状态中对应位置就不可能为 $1$ ，我们可以做预处理去筛选，实际上大约只有 $\cdot 10^4$ 个合法状态

code:

#include <bits/stdc++.h>

using namespace std;

typedef long long unsigned ll;
typedef pair<int,int> pii;

ll L,R;
int len=0;
int a[25];
ll dp[25][60000];

map<pii,int> mp;
int tot=0;

inline bool check(int x,int mask){
    for(int i=0;i<=9;i++){
        if((x&1)==0){
            x>>=1;mask>>=1;
            continue;
        }
        if(i%2==0&&!(mask&1)) return false;
        if(i%2==1&&(mask&1)) return false;
        x>>=1,mask>>=1;
    }
    return true;
}

ll dfs(int pos,int x,int mask,bool lead,bool limit){
    if(!pos) return check(x,mask);
    if(!limit&&!lead&&~dp[pos][mp[pii(x,mask)]]) return dp[pos][mp[pii(x,mask)]];
    int cur=limit?a[pos]:9;
    ll res=0;
    for(int i=0;i<=cur;i++){
        bool f=lead&&(i==0);
        res+=dfs(pos-1,f?x:x|(1<<i),f?mask:mask^(1<<i),f,limit&&(i==cur));
    }

    if(!limit&&!lead) dp[pos][mp[pii(x,mask)]]=res;
    return res;
}

ll solve(ll x){
    len=0;
    while(x) a[++len]=x%10,x/=10;
    return dfs(len,0,0,1,1);
}

int main(){
    for(int i=0;i<(1<<10);i++){
        for(int j=0;j<(1<<10);j++){
            bool f=1;
            for(int k=0;k<=9;k++){
                if(!(i>>k&1)&&(j>>k&1)){
                    f=0;break;
                }
            }
            if(f) mp[pii(i,j)]=++tot;
        }
    }
    memset(dp,-1,sizeof dp);
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%llu %llu",&L,&R);
        printf("%llu\n",solve(R)-solve(L-1));
    }
    return 0;
}

P4124 - [CQOI2016]手机号码

题目描述：

现在定义手机号码为满足以下条件的 $11$ 位数

号码中要出现至少 $3$ 个相邻的相同数字；
号码中不能同时出现 $8$ 和 $4$ 。

求 $[L, R]$ 中手机号码的个数

$10^{10} \leq L \leq R \leq 10^{11}$

思路：
前面几道题其实都差不多，只需要记录是否存在 $4, 8$ ，前两位数是谁，还有是否存在过连续三位数相同即可。

并且由于这题保证 $11$ 位数合法，我们可以直接省去前导零标记，直接从 $1 - 9$ 作为第一位开始搜

code:

ll l,r;
int len=0,a[15];
ll dp[15][15][15][2][2][2];

ll dfs(int pos,int ppre,int pre,bool f,bool four,bool eight,bool limit){
    if(four&&eight) return 0;
    if(pos>len) return f;
    if(!limit&&~dp[pos][ppre][pre][f][four][eight]) return dp[pos][ppre][pre][f][four][eight];
    int cur=limit?a[len-pos+1]:9;
    ll res=0;
    for(int i=0;i<=cur;i++){
        res+=dfs(pos+1,pre,i,f||((i==pre)&&(i==ppre)),four||(i==4),eight||(i==8),limit&&(i==cur));
    }
    if(!limit) dp[pos][ppre][pre][f][four][eight]=res;
    return res;
}

ll part(ll x){
    len=0;
    while(x) a[++len]=x%10,x/=10;
    if(len<11) return 0;
    memset(&dp,-1,sizeof dp);
    ll res=0;
    for(int i=1;i<=a[len];i++){
        res+=dfs(2,0,i,0,i==4,i==8,i==a[len]);
    }
    return res;
}

int main(){
    cin>>l>>r;
    cout<<part(r)-part(l-1)<<endl;
}

CF1073E - Segment Sum

题目描述：

给出 $L, R, k$ ，求 $[L, R]$ 之间数码个数不超过 $k$ 的数的和

思路：
显然必须用一个 $m a s k$ 表示当前状态下数码的出现情况，设 $c n t (x)$ 为 $x$ 的二进制数中 $1$ 的个数，那么显然 $c n t (x) > k$ 时我们可以直接剪枝退出。

$l i m i t, l e a d$ 标记照旧，如果当前数码为 $0$ ，我们只需要 $l e a d$ 前导零标记判断是否需要加入到 $m a s k$ 状态中

接着这题需要求的是所有数的和，发现我们无法利用现有的几个状态去记搜答案。
比如 $01$ x 和 $11$ x，这两个数在状态表示上相同，但是显然 $11$ x 没法用 $01$ x 搜出来的数，因为答案与前一部分 $01$ 与 $11$ 也有关，这两者在和上显然没有呈现一致性

所以我们按照每一位来算贡献，对于第 $p o s$ 位来说，我们将该位的值定为 $i$ ，则会产生 $10^{len-pos}*i*[往后搜出的数的个数]$ 的贡献，并且我们要加上往后搜出的贡献

code:

ll L,R;
int k;
int len=0,a[20];
pii dp[20][1<<11];
ll pw[20];

pii dfs(int pos,int mask,bool limit,bool lead){
    if(__builtin_popcount(mask)>k) return pii(0,0);
    if(pos>len) return pii(0,1);
    if(!lead&&!limit&&~dp[pos][mask].first) return dp[pos][mask]; 
    int cur=limit?a[len-pos+1]:9;
    pii res=pii(0,0);
    pii tmp;
    for(int i=0;i<=cur;i++){
        if(lead&&!i) tmp=dfs(pos+1,0,limit&&(i==cur),1);
        else if(lead) tmp=dfs(pos+1,mask|(1<<i),limit&&(i==cur),0);
        else tmp=dfs(pos+1,mask|(1<<i),limit&&(i==cur),0);
        ll dig=i;
        res.first=((pw[len-pos]*tmp.second%p*dig%p+res.first)%p+tmp.first)%p;
        res.second=(res.second+tmp.second)%p;
    }
    if(!lead&&!limit) dp[pos][mask]=res;
    return res;
}

ll part(ll x){
    memset(dp,-1,sizeof dp);
    len=0;
    while(x) a[++len]=x%10,x/=10;
    return dfs(1,0,1,1).first;
}

int main(){
    pw[0]=1;
    for(int i=1;i<=18;i++) pw[i]=pw[i-1]*10%p;
    scanf("%lld %lld %d",&L,&R,&k);
    printf("%lld\n",(part(R)-part(L-1)+p)%p);
    return 0;
}

CF55D - Beautiful numbers

题目描述：

定义一个能被其所有非零数位整除的数为 beautiful numbers

现在给出 $t$ 组询问，每次查询 $[L, R]$ 区间内的 beautiful numbers 个数

$\leq t \leq 10,1 \leq L \leq R \leq 9 \cdot 10^{18}$

思路：

很容易想到记录原数字 $x$ 与包含的数位种类去做数位dp，这显然无法开下记忆化数组。

想想我们记录 $x$ 的原因是为了判断这个数能不能整除它包含的数位。

也就说需要判断是否能被 ${1,2...9\}$ 的某个子集的 $l c m$ 整除，这个子集的最坏情况就是 $lcm\{1,2...9 \}=2520$ 本身，且由于任意子集的 $l c m$ 都是 $2520$ 的约数，因此我们只需要记录 $\mod 2520$ 的值。

但是此时我们发现状态 $20 \cdot 2520 \cdot 2520$ 仍然开不下数组，对于 $p o s$ 和数位种类显然已经无法再做优化，最多把数位种类用状压表示，依然不够。。

我们发现 $2520$ 的因子只有 $48$ 个，我们在记忆化时只需要在乎这 $48$ 个就行了，其他是谁都无所谓，所以我们可以直接 $h a s h$ 把这一维减少为 $50$ ，可以通过本题

在函数调用的使用就正常传递 $l c m$ 值代表数位种类就行，就记忆化调用数组下标时 $h a s h$ 进去就行

code:

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ll;

const int p=2520;

ll pw[25];
int a[25],len=0;
int fac[2550],o=0;
ll dp[25][50][2550];

int LCM(int a,int b){
    return a*b/__gcd(a,b);
}

ll dfs(int pos,int mod,int lcm,bool limit){
    if(!pos) return (mod%lcm==0)?1:0;
    if(!limit&&~dp[pos][fac[lcm]][mod]) return dp[pos][fac[lcm]][mod];
    int cur=limit?a[pos]:9;
    ll res=0;
    for(int i=0;i<=cur;i++){
        res+=dfs(pos-1,(mod+pw[pos-1]*i%p)%p,i?LCM(i,lcm):lcm,limit&&(i==cur));
    }
    if(!limit) dp[pos][fac[lcm]][mod]=res;
    return res;
}


ll solve(ll x){
    len=0;
    while(x) a[++len]=x%10,x/=10;
    return dfs(len,0,1,1);
}

int main(){
    memset(dp,-1,sizeof dp);
    for(int i=1;i<=p;i++){
        if(p%i==0) fac[i]=++o;
    }
    pw[0]=1;
    for(int i=1;i<=18;i++) pw[i]=pw[i-1]*10%p;
    int t;
    cin>>t;
    ll l,r;
    while(t--){
        cin>>l>>r;
        cout<<solve(r)-solve(l-1)<<endl;
    }
    return 0;
}

P4127 - [AHOI2009]同类分布

题目描述：

给出两个数 $L, R$ ，求出 $[L, R]$ 中各位数字之和能整除原数的数的个数

$\leq L \leq R \leq 10^{18}$

思路：

还是和前几题差不多，参数设置为原数和数位和，然后原数由于过大显然无法直接搜，想想怎么去取模表示。

我们最理想的模数当然是把每次搜到最后得到的数字各个位数之和，但是我们发现在这个过程中这个数位和是发生变化的，所以我们就应该以一个定值作为模数，考虑枚举模数 $[1, l e n * 9]$ 这个范围即可

code:

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=1e5+10;


int len=0,a[25],p;
ll L,R,dp[20][200][200];


ll dfs(int pos,int mod,int sum,bool limit){
    if(!pos) return mod==0&&sum==p;
    if(!limit&&~dp[pos][mod][sum]) return dp[pos][mod][sum];
    int cur=limit?a[pos]:9;
    ll res=0;
    for(int i=0;i<=cur;i++){
        res+=dfs(pos-1,(mod*10+i)%p,sum+i,limit&&(i==cur));
    }
    if(!limit) dp[pos][mod][sum]=res;
    return res;
}

ll solve(ll x){
    len=0;
    while(x) a[++len]=x%10,x/=10;
    ll res=0;
    for(int i=1;i<=len*9;i++){
        p=i;
        memset(dp,-1,sizeof dp);
        res+=dfs(len,0,0,1);
    }
    return res;
}


int main(){
    scanf("%lld %lld",&L,&R);
    printf("%lld\n",solve(R)-solve(L-1));
    return 0;   
}

P3413 - SAC#1 - 萌数

题目描述：

定义存在长度至少为 $2$ 的回文子串的数是萌数，求区间 $l$ 到 $r$ 内萌数的个数

$\leq n \leq 1000$ ，其中 $n$ 代表 $l, r$ 十进制下的位数

思路：

如果直接找萌数个数，那么只需要记录前两个数是什么，并且记录一个历史状态代表是否出现过子回文串即可。

code:

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int p=1e9+7;
const int maxn=1005;

string l,r;
int a[maxn];
int len=0;
ll dp[maxn][12][12][2];

ll dfs(int pos,int ppre,int pre,bool f,bool lead,bool limit){ 
    if(!pos) return f;
    if(!lead&&!limit&&~dp[pos][ppre+1][pre+1][f]) return dp[pos][ppre+1][pre+1][f];
    int cur=limit?a[pos]:9;
    ll res=0;
    for(int i=0;i<=cur;i++){
        if(lead&&!i) res=(res+dfs(pos-1,ppre,pre,f,lead,limit&&(i==cur)))%p;
        else if(lead) res=(res+dfs(pos-1,pre,i,f,0,limit&&(i==cur)))%p; 
        else res=(res+dfs(pos-1,pre,i,f||(i==pre)||(i==ppre),0,limit&&(i==cur)))%p ;
    }
    if(!limit&&!lead) dp[pos][ppre+1][pre+1][f]=res;
    return res;
}   

bool check(string s){
    for(int i=0;i<s.size();i++){
        if(s[i]==s[i-1]&&i) return true;
        if(i>=2&&s[i]==s[i-2]) return true;
    }
    return false;
}

ll solve(string s){
    len=s.size();
    for(int i=0;i<len;i++) a[len-i]=s[i]-'0';
    return dfs(len,-1,-1,0,1,1);
}   

int main(){
    memset(dp,-1,sizeof dp);
    cin>>l>>r;
    int ans=0;
    if(check(l)) ans=1;
    printf("%lld\n",(solve(r)-solve(l)+ans+p)%p);
    return 0;
}

！！

这里留了一个思考，就是我看到一篇题解前前一个数在数组里的参数可以省略，想了想好像是有点道理，因为当你解除 $l i m i t$ 限制后取值都是 $[0, 9]$ 必然能取到回文，但是又没法去论证什么的，自己试了几种方法也不行。

看看有没有大佬能解决这个问题，或者等再过段时间看看自己的想法有没有变化

秒客网

数位DP学习笔记

文章目录

数位DP

大量例题

P4999 - 烦人的数学作业

HDU2089 - 不要62

P6218 - [USACO06NOV] Round Numbers S

P2602 - [ZJOI2010]数字计数

P2657 - [SCOI2009] windy 数

P4317 - 花神的数论题

CF855E Salazar - Slytherin’s Locket

SP10606 - BALNUM - Balanced Numbers

P4124 - [CQOI2016]手机号码

CF1073E - Segment Sum

CF55D - Beautiful numbers

P4127 - [AHOI2009]同类分布

P3413 - SAC#1 - 萌数

！！

相关文章