数位DP学习（一）

数位DP学习

我是参考Pecco大佬的这篇文章学习的：算法学习笔记(68): 数位DP - 知乎 (zhihu.com)，可以先看看，或者复习后再看看下面的题。

题单是这个：（提高）『数位DP』从入门到入土 - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)，目前写了十多道，会慢慢补的。

也许以后会再补充一些其他OJ上的题目？

---

数位DP文章例题

先附上文章里的题目吧~~~

不要62 - HDU 2089 - Virtual Judge (vjudge.net)

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
const double PI=acos(-1);
int a[10],dp[8][12][2];
int cnt;    //记录原来的数字中的位数
//dp[pos][last][limit]
//dp[pos][last][limit] 表示在第pos位时 所有符合要求的方案数
//limit是用来限制当前位最多可以枚举到哪一位
//true 说明只能枚举到原来的数字中这一位的值 否则就是0-9
//last是用来记录上一位的数字 判断当前解是否合法
//一般来说pos 和 limit是必要的 其他根据题目要求增加维度
int dfs(int pos,int last,bool limit)
{
    int ans=0;
    if(pos==cnt)return 1;   //终点
    if(dp[pos][last][limit]!=-1)return dp[pos][last][limit];
    for(int i=0;i<=(limit?a[pos]:9);i++)
    {
        if(last==6&&i==2 || i==4)   continue;
        ans+=dfs(pos+1,i,limit&&i==a[pos]);
    }
    dp[pos][last][limit]=ans;
    return ans;
}
int f(int x)
{
    cnt=0;
    memset(a,0,sizeof(a));
    memset(dp,-1,sizeof(dp));   //初始化dp数组为-1
    while(x)
    {
        a[cnt++]=x%10;
        x/=10;
    }
    std::reverse(a,a+cnt);
    return dfs(0,11,true);  //last设置为11 表示不存在上一位
}
void solve()
{
    int x,y;
    while(std::cin>>x>>y,(x||y))
    {
        int l=f(x-1),r=f(y);
        std::cout<<r-l<<"\n";
    }
}
int main() {
    std::ios::sync_with_stdio(false);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

P2602 [ZJOI2010] 数字计数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

//#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
const double PI=acos(-1);
ll a[10],dp[15][12][2][2];
//dp[pos][cntd][limit][lead]
//pos 和 limit就不介绍了 前面已经知道了
//cntd 表示的是到目前为止找到了多少个digit
//lead 表示记录在当前位之前所有位是否都是0
//除了for循环内容和pos==cnt 外 其他的基本上都是板子
ll cnt,digit;
ll dfs(int pos,int cntd,bool limit,bool lead)
{
    ll ans=0;
    auto &d=dp[pos][cntd][limit][lead];
    if(pos==cnt)    return d;
    if(dp[pos][cntd][limit][lead]!=-1)  return dp[pos][cntd][limit][lead];
    for(int i=0;i<=(limit?a[pos]:9);i++)
    {
        if(lead && i==0)    ans+=dfs(pos+1,cntd,limit && i==a[pos],true);
        else ans+=dfs(pos+1,cntd+(i==digit),limit && i==a[pos],false);
    }
    dp[pos][cntd][limit][lead]=ans;
    return ans;
}
ll f(ll x)
{
    cnt=0;
    memset(a,0,sizeof(a));
    memset(dp,-1,sizeof(dp));   //初始化dp数组为-1
    while(x)
    {
        a[cnt++]=x%10;
        x/=10;
    }
    std::reverse(a,a+cnt);
    return dfs(0,0,true,true);
}
void solve()
{
    ll x,y; std::cin>>x>>y;
    for(int i=0;i<10;i++)
    {
        digit=i;
        ll l=f(x-1),r=f(y);
        std::cout<<r-l<<" ";
    }
}
int main() {
    std::ios::sync_with_stdio(false);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

Little Girl and Maximum XOR - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
const double PI=acos(-1);
ll a[64],b[64],dp[64][2][2][2][2];
//这里注意一下数组大小 因为是二进制 所以原本的20需要装换成对应的二进制数有几位
//dp[pos][limitl1][limitr1][limitl2][limitr2]
//pos含义一样 limitl1 表示当前位是否有下限制 limitr1 表示当前位是否有上限制
//limitl2 limitr2 同理
//因为是枚举2个数 并且不是计数 所以一个数需要设置上下限 总共4个limit
ll cnt1,cnt2,cnt;
//cnt1 表示的是a数组的各位
//cnt2 表示的是b数组的各位
//cnt=max(cnt1,cnt2)
ll dfs(int pos,bool limitl1,bool limitr1,bool limitl2,bool limitr2)
{
    if(pos==cnt)    return 0;   //这里不太理解wsm是return 0;
    auto &d=dp[pos][limitl1][limitr1][limitl2][limitr2];
    if(d!=-1)
    {
        return d;
    }
    ll ans=0;
    for(ll i=(limitl1?a[pos]:0);i<=(limitr1?b[pos]:1);i++)
    {
        for(ll j=(limitl2?a[pos]:0);j<=(limitr2?b[pos]:1);j++)
        {
            ans=std::max(ans,((i^j)<<(cnt-pos-1))+dfs(pos+1,limitl1 && i==a[pos],limitr1 && i==b[pos],limitl2 && j==a[pos], limitr2 && j==b[pos]));
        }
    }
    d=ans;
    return ans;
}
ll f(ll x,ll y)
{
    cnt1=0;
    cnt2=0;
    memset(dp,-1,sizeof(dp));   //初始化dp数组为-1
    while(x)
    {
        a[cnt1++]=x&1;
        x>>=1;
    }
    while(y)
    {
        b[cnt2++]=y&1;
        y>>=1;
    }
    cnt=std::max(cnt1,cnt2);
    std::reverse(a,a+cnt);
    std::reverse(b,b+cnt);
    return dfs(0,true,true,true,true);
}
void solve()
{
    ll x,y; std::cin>>x>>y;
    std::cout<<f(x,y)<<"\n";
}
int main() {
    std::ios::sync_with_stdio(false);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

这道题的正解做法其实是贪心，后面会写一篇文章来介绍。

---

（提高）『数位DP』从入门到入土

P4999 烦人的数学作业 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

//#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
const double PI=acos(-1);
int cnt=0;
ll a[22];
ll dp[22][200][2];
ll dfs(int pos,ll sum,bool limit)
{
    ll ans=0;
    auto &d=dp[pos][sum][limit];
    if(pos==cnt)    return sum;
    if(d!=-1)   return d;
    for(int i=0;i<=(limit?a[pos]:9);i++)
    {
        ans+=dfs(pos+1,sum+i,limit && i==a[pos]);
        ans+=mod;
        ans%=mod;
    }
    return d=ans;
}
ll f(ll x)
{
    cnt=0;
    memset(dp,-1,sizeof(dp));
    memset(a,0,sizeof(a));
    while(x)
    {
        a[cnt++]=x%10;
        x/=10;
    }
    std::reverse(a,a+cnt);
    return dfs(0,0,true);
}
void solve()
{
    ll x,y;     std::cin>>x>>y;
    ll l=f(x-1),r=f(y);
    //需要注意最后+mod 再%mod
    std::cout<<(r-l+mod)%mod<<"\n";
}
int main() {
    std::ios::sync_with_stdio(false);
    int t=1;
    std::cin>>t;
    while(t--)solve();
    return 0;
}

P6218 [USACO06NOV] Round Numbers S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

//#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
const double PI=acos(-1);
ll a[64],dp[64][64][64][2][2];
//dp[pos][cnt0][cnt1][limit]
//pos limit 含义一样 cnt0记录当前有多少个0  cnt1同理 lead 考虑当前位之前是否全为0
//奇怪的问题 多加了一维就过了??? 原来一直WA
//大概明白什么原因了 如果是原来直接减 里面会包含前导0 所以就错了
ll cnt;
ll dfs(ll pos,ll cnt0,ll cnt1,bool limit,bool lead)
{
    ll ans=0;
    if(pos==cnt)
    {
        return cnt0>=cnt1;
    }
    auto &d=dp[pos][cnt0][cnt1][limit][lead];
    if(d!=-1)    return d;
    for(int i=0;i<=(limit?a[pos]:1);i++)
    {
        if(lead && i==0)    ans+=dfs(pos+1,cnt0,cnt1,limit && i==a[pos],true);
        else if(lead) ans+=dfs(pos+1,cnt0,cnt1+1,limit && i==a[pos],false);
        else    ans+=dfs(pos+1,cnt0+(i==0),cnt1+(i==1),limit && i==a[pos],false);
    }
    d=ans;
    return ans;
}
ll f(ll x)
{
    cnt=0;
    memset(dp,-1,sizeof(dp));   //初始化dp数组为-1
    memset(a,0,sizeof(a));
    while(x)
    {
        a[cnt++]=x&1;
        x>>=1;
    }
    std::reverse(a,a+cnt);
    return dfs(0,0,0,true,true);
}
void solve()
{
    ll x,y; std::cin>>x>>y;
    ll l=f(x-1),r=f(y);
    std::cout<<r-l<<"\n";
}
int main() {
    std::ios::sync_with_stdio(false);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

P2657 [SCOI2009] windy 数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
const double PI=acos(-1);
int cnt=0;
ll a[12];
ll dp[20][12][12][2][2];
//数据出水了 这份码是有问题的
//加上特判应该就没问题了 可能是算重的问题
//有一个地方不太理解 1 200000 --> 46859
//第二维度上限是10100
//大致明白了 ans+=----       d=ans
//得到的ans 和 sum 没有直接的关系 sum是一个底层的基本情况 ans是由底层dp来的
//因为其实只是0-9之间 所以底层实际上sum的数目只有0-9之间而已(也许有10)
ll dfs(int pos,ll sum,int last,bool limit,bool lead)
{
    ll ans=0;
    auto &d=dp[pos][sum][last][limit][lead];
    if(pos==cnt)
    {
        //发现了一件奇怪的事情 sum改成d 恰好是答案的负数
        return sum;
    }
    if(d!=-1)   return d;
    for(int i=0;i<=(limit?a[pos]:9);i++)
    {
        if(abs(i-last)>=2 || lead)
        {
            //比较恶心的一点 一位数也是windy数
            //所以这里得讨论一下 如果abs(i-last)>=2 或者 有前导0 都可能是windy数(个位数捣乱)
            //所以sum的更新需要判断 如果是个位数或者没有前导0 那么sum就+1 但是这样后面就得加上特判了
            ans+=dfs(pos+1,sum+((cnt==1)) || (i || !lead),i,limit && i==a[pos],lead && i==0);
        }
    }
    d=ans;
    return ans;
}
ll f(ll x)
{
    cnt=0;
    memset(dp,-1,sizeof(dp));
    memset(a,0,sizeof(a));
    while(x)
    {
        a[cnt++]=x%10;
        x/=10;
    }
    std::reverse(a,a+cnt);
    return dfs(0,0,0,true,true);
}
void solve()
{
    ll x,y;     std::cin>>x>>y;
    ll l=f(x-1),r=f(y);
    if(x<10&&y<10)    std::cout<<r-l-1<<"\n";
    else        std::cout<<r-l<<"\n";

}
int main() {
    std::ios::sync_with_stdio(false);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

P2602 [ZJOI2010] 数字计数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

看上面，这里不重复了。

P1836 数页码 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
const double PI=acos(-1);
int cnt=0;
ll a[12];
ll dp[12][90][2][2];
ll dfs(int pos,ll sum,bool limit,bool lead)
{
    ll ans=0;
    auto &d=dp[pos][sum][limit][lead];
    if(pos==cnt)
    {
        return sum;
    }
    if(d!=-1)   return d;
    for(int i=0;i<=(limit?a[pos]:9);i++)
    {
        if(lead && i==0)    ans+=dfs(pos+1,sum,limit && i==a[pos],true);
        else    ans+=dfs(pos+1,sum+i,limit && i==a[pos],false);
    }
    d=ans;
    return ans;
}
ll f(ll x)
{
    cnt=0;
    memset(dp,-1,sizeof(dp));
    memset(a,0,sizeof(a));
    while(x)
    {
        a[cnt++]=x%10;
        x/=10;
    }
    std::reverse(a,a+cnt);
    return dfs(0,0,true,true);
}
void solve()
{
    ll x,y;     std::cin>>y;
    x=1;
    ll l=f(x-1),r=f(y);
    std::cout<<r-l<<"\n";

}
int main() {
    std::ios::sync_with_stdio(false);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

P4317 花神的数论题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
const int P=1e7+7;
const double PI=acos(-1);
int cnt=0;
ll a[64];
ll dp[64][64][64][2];
ll ans[64];
ll dp2[64][64][2];
//一开始没搞懂wsm要用快速幂
//大概明白了 求的是sum(1)*sum(2)*------*sum(n)
//可以转化成对应的二进制数中 1个1的个数 * 2个1的个数 * 3个1的个数 * 4个1的个数 * ...
//这个时候就可以使用快速幂了
//直接算应该也是可行的 但是dp方程就需要改变了
/*引用一下
 * 我们可以用数位DP求出二进制数中含有1的个数为k的数的数目sum，
 * 这样k的贡献就是sum个k连乘，也就是k的sum次方，
 * 这样我们枚举每一个二进制表示中可能含有的1的个数就可以得到最终的贡献
 */

//答案涉及到取模，但是需要注意的是我们仅仅能在加法减法或者乘法过程中随意取模，
//但是我们不能在求指数的过程中取模，否则会出现错误

/*
 * 又犯了一堆错误
 * 1 取模的时候只能在快速幂的时候取 否则ans[i]改变了
 * 2 又默认拆分成十进制了 数组也开小了 a[]开小了 dp[]却开对了------
 * 3 dfs中 ans赋值成1了
 * 4 P是 1e7+7 写成1e9+7 或者1e7+9了
 * 5 最后答案取模时又忘记+P 再%P了
 */
ll dfs(int pos,int cnt1,int tot,bool limit)
{
    ll ans=0;
    auto &d=dp[pos][cnt1][tot][limit];
    if(pos==cnt)
    {
        return cnt1==tot;
    }
    if(d!=-1)   return d;
    for(int i=0;i<=(limit?a[pos]:1);i++)
    {
        ans+=dfs(pos+1,cnt1+(i==1),tot,limit && i==a[pos]);
    }
    d=ans;
    return ans;
}
ll qpower(ll a,ll n)
{
    ll ans=1;
    while(n)
    {
        if(n&1) ans=a*ans%P;
        a=a*a%P;
        n>>=1;
    }
    return ans;
}
void solve()
{
    ll x,y;     std::cin>>y;
    cnt=0;
    memset(a,0,sizeof(a));
    while(y)
    {
        a[cnt++]=y&1;
        y/=2;
    }
    std::reverse(a,a+cnt);
    for(int i=0;i<cnt;i++)
    {
        memset(dp,-1,sizeof(dp));
        ans[i]=dfs(0,0,i+1,true);
    }
    ll res=1;
    for(int i=0;i<cnt;i++)
    {
        res=res*qpower(i+1,ans[i])%P;
    }
    std::cout<<(res+P)%P<<"\n";
}

//还有第二种方法 第一种我们算的是含有k个1的数的个数，然后我们在函数外面进行求解k的贡献
//我们现在其实可以直接计算 就可以不用在外面再累乘计算了
ll dfs2(int pos,int cnt1,bool limit)
{
    ll ans=1;
    auto &d=dp2[pos][cnt1][limit];
    if(pos==cnt)
    {
        return std::max(cnt1,1);
    }
    if(d!=-1)   return d;
    for(int i=0;i<=(limit?a[pos]:1);i++)
    {
        ans=ans*dfs2(pos+1,cnt1+(i==1),limit && i==a[pos])%P;
    }
    return d=ans;
}
void solve2()
{
    ll x,y;     std::cin>>y;
    cnt=0;
    memset(a,0,sizeof(a));
    while(y)
    {
        a[cnt++]=y&1;
        y>>=1;
    }
    memset(dp2,-1,sizeof(dp2));
    std::reverse(a,a+cnt);
    std::cout<<(dfs2(0,0,true)+P)%P;
}
int main() {
    std::ios::sync_with_stdio(false);
    int t=1;
    //std::cin>>t;
    while(t--)solve2();
    return 0;
}

统计问题 The Counting Problem - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

//#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
const double PI=acos(-1);
ll a[10],dp[15][12][2][2];
//dp[pos][cntd][limit][lead]
//pos 和 limit就不介绍了 前面已经知道了
//cntd 表示的是到目前为止找到了多少个digit
//lead 表示记录在当前位之前所有位是否都是0
//除了for循环内容和pos==cnt 外 其他的基本上都是板子
ll cnt,digit;
ll dfs(int pos,int cntd,bool limit,bool lead)
{
    ll ans=0;
    if(pos==cnt)    return cntd;
    if(dp[pos][cntd][limit][lead]!=-1)  return dp[pos][cntd][limit][lead];
    for(int i=0;i<=(limit?a[pos]:9);i++)
    {
        if(lead && i==0)    ans+=dfs(pos+1,cntd,limit && i==a[pos],true);
        else ans+=dfs(pos+1,cntd+(i==digit),limit && i==a[pos],false);
    }
    dp[pos][cntd][limit][lead]=ans;
    return ans;
}
ll f(ll x)
{
    cnt=0;
    memset(a,0,sizeof(a));
    memset(dp,-1,sizeof(dp));   //初始化dp数组为-1
    while(x)
    {
        a[cnt++]=x%10;
        x/=10;
    }
    std::reverse(a,a+cnt);
    return dfs(0,0,true,true);
}
void solve()
{
    ll x,y;
    while(std::cin>>x>>y,x||y)
    {
        if(x>y)     std::swap(x,y);
        for(int i=0;i<10;i++)
        {
            digit=i;
            ll l=f(x-1),r=f(y);
            //毒瘤问题 不能输出多余的空格
            std::cout<<r-l<<(i<9?" ":"\n");
        }
    }
}
int main() {
    std::ios::sync_with_stdio(false);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

Salazar Slytherin's Locket - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

//#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
const double PI=acos(-1);
ll a[64],dp[64][1024][2][12];
//理解错题意了 题目要求得是这个数转化成b进制后 判断0---b-1得个数是否都为偶数 如果是 则统计
//其实有一个很莽的写法 因为b最大到10 所以直接开到13维度
//但是正解是状压+数位
//我们可以将每个数字出现的个数进行二进制状态压缩
//0 表示出现偶数次
//1 表示出现奇数次
//dp[pos][state][limit][lead]
//pos lead limit 分别表示位置 有无前导0 当前位有无限制
//state 状压表示集合
//状态转移 只需要state ^ (1<<i)即可

//最后再加一个维度 表示进制 这样dp数组只要初始化一次即可 否则会TLE
//注意要加在最前面 否则数组访问到其他非法元素
//好吧 不是这个原因 已经卡了两个多小时了 bzd为什么 已经无语了

/*
 * ok 大致理解原理了 非常好的题 使我“浪费”了三个小时时间(但是 数位dp也进化了)
 * 由于在不同数的limit是不同的 这会阻止我们复用dp数组
 * 注意到limit等于1的状态出现的频率远远小于limit等于0的状态，
 * 所以我们可以选择只记忆化limit为0的状态，
 * 这样每次dp数组的意义就完全相同了 (来自Pecco)
 */
ll cnt;
ll b;
ll dfs(ll pos,int state,bool limit,bool lead)
{
    ll ans=0;
    auto &d=dp[pos][state][lead][b];
    if(!pos)    return state==0;
    if(d!=-1 && !limit)  return d;
    for(int i=0;i<=(limit?a[pos]:b-1);i++)
    {
        if(lead && i==0)    ans+=dfs(pos-1,false,limit && i==a[pos],true);
        else    ans+=dfs(pos-1,state^(1<<i),limit && i==a[pos],false);
    }
    if(!limit)  d=ans;
    return ans;
}
ll f(ll x)
{
    cnt=0;
    while(x)
    {
        a[++cnt]=x%b;
        x/=b;
    }
    return dfs(cnt,false,true,true);
}
void solve()
{
    ll x,y;     std::cin>>b>>x>>y;
    ll l=f(x-1);
    ll r=f(y);
    std::cout<<r-l<<"\n";
}
int main() {
    std::ios::sync_with_stdio(false);
    int t=1;
    memset(dp,-1,sizeof(dp));
    std::cin>>t;
    while(t--)solve();
    return 0;
}

MDIGITS - Counting Digits - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

//#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
const double PI=acos(-1);
ll a[10],dp[15][12][2][2];
//dp[pos][cntd][limit][lead]
//pos 和 limit就不介绍了 前面已经知道了
//cntd 表示的是到目前为止找到了多少个digit
//lead 表示记录在当前位之前所有位是否都是0
//除了for循环内容和pos==cnt 外 其他的基本上都是板子
ll cnt,digit;
ll dfs(int pos,int cntd,bool limit,bool lead)
{
    ll ans=0;
    if(pos==cnt)    return cntd;
    if(dp[pos][cntd][limit][lead]!=-1)  return dp[pos][cntd][limit][lead];
    for(int i=0;i<=(limit?a[pos]:9);i++)
    {
        if(lead && i==0)    ans+=dfs(pos+1,cntd,limit && i==a[pos],true);
        else ans+=dfs(pos+1,cntd+(i==digit),limit && i==a[pos],false);
    }
    dp[pos][cntd][limit][lead]=ans;
    return ans;
}
ll f(ll x)
{
    cnt=0;
    memset(a,0,sizeof(a));
    memset(dp,-1,sizeof(dp));   //初始化dp数组为-1
    while(x)
    {
        a[cnt++]=x%10;
        x/=10;
    }
    std::reverse(a,a+cnt);
    return dfs(0,0,true,true);
}
void solve()
{
    ll x,y;
    while(std::cin>>x>>y,x||y)
    {
        if(x>y)     std::swap(x,y);
        for(int i=0;i<10;i++)
        {
            digit=i;
            ll l=f(x-1),r=f(y);
            //毒瘤问题 不能输出多余的空格
            std::cout<<r-l<<(i<9?" ":"\n");
        }
    }
}
int main() {
    std::ios::sync_with_stdio(false);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

Classy Numbers - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

//#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
const double PI=acos(-1);
ll a[22],dp[22][22][2];
int cnt;
ll dfs(int pos,int cntd,bool limit,bool lead)
{
    ll ans=0;
    auto &d=dp[pos][cntd][lead];
    if(pos==0)      return cntd<=3;
    if(!limit && d!=-1)   return d;
    for(int i=0;i<=(limit?a[pos]:9);i++)
    {
        ans+=dfs(pos-1,cntd+(i!=0),limit && i==a[pos],lead && i==0);
    }
    if(!limit)  d=ans;
    return ans;
}
ll f(ll x)
{
    cnt=0;
    while(x)
    {
        a[++cnt]=x%10;
        x/=10;
    }
    return dfs(cnt,0,true,true);
}
void solve()
{
    ll x,y;     std::cin>>x>>y;
    ll l=f(x-1);
    ll r=f(y);
    std::cout<<r-l<<"\n";
}
int main() {
    std::ios::sync_with_stdio(false);
    int t=1;
    memset(dp,-1,sizeof(dp));
    std::cin>>t;
    while(t--)solve();
    return 0;
}

P4127 [AHOI2009] 同类分布 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

//#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
const double PI=acos(-1);
ll a[22],dp[22][180][200];
int cnt;
int P;
//也是一道挺有意思的题目
//dp[pos][sum][num]表示pos是位，sum为和，num为原数
//但是由于范围太大 直接转移存在问题 所以不难想到取模
//但是取什么数 这是一个问题
//原来的要求就是sum%num==0 即可
//所以如果能够让num取模到最后为0 其实也就是sum为模数就好了
//这样其实看好像没啥区别(有一种废话做法的感觉，问题就在于范围太大了 可能会溢出 所以算的过程中取模)
//但是把又不知道是哪一个 所以可以暴力枚举(范围也很小 200内)
ll dfs(int pos,int sum,ll num,bool limit)
{
    ll ans=0;
    auto &d=dp[pos][sum][num];
    if(pos==0)      return num==0 && sum==P;    //最后结果 需要num==0 并且 sum==P (P是枚举的模数)
    if(!limit && d!=-1)   return d;
    for(int i=0;i<=(limit?a[pos]:9);i++)
    {
        //注意边算边取模
        ans+=dfs(pos-1,sum+i,(10ll*num+i)%P,limit && i==a[pos]);
    }
    if(!limit)  d=ans;
    return ans;
}
ll f(ll x)
{
    cnt=0;
    while(x)
    {
        a[++cnt]=x%10;
        x/=10;
    }
    ll ans=0;
    
    //暴力枚举模数
    for(P=1;P<=9*cnt;P++)
    {
        memset(dp,-1,sizeof(dp));   //这里还得memset一下
        ans+=dfs(cnt,0,0,true);
    }
    return ans;
}
void solve()
{
    ll x,y;     std::cin>>x>>y;
    ll l=f(x-1);
    ll r=f(y);
    std::cout<<r-l<<"\n";
}
int main() {
    std::ios::sync_with_stdio(false);
    int t=1;
    //memset(dp,-1,sizeof(dp));
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

PR003004 - Digit Sum - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
const double PI=acos(-1);
int cnt,digit;
ll a[20];
ll dp[20][20][2];
//dp[pos][cntd][lead]
//pos 表示位置 cntd 表示 统计到的digit的个数 lead 表示是否有前导0
//一开始的想法是对其进行取模运算 记录余数和倍数 但是后来发现这样搞也会MLE
//发现都是由0-9数字构成的 所以我们可以统计下0-9的数目 在加起来即可
ll dfs(int pos,int cntd,bool limit,bool lead)
{
    ll ans=0;
    auto &d=dp[pos][cntd][lead];
    if(pos==0)      return cntd;
    if(d!=-1 && !limit)      return d;
    for(int i=0;i<=(limit?a[pos]:9);i++)
    {
        if(lead && i==0)    ans+=dfs(pos-1,cntd,limit && i==a[pos],true);
        else    ans+=dfs(pos-1,cntd+(i==digit),limit && i==a[pos],false);
    }
    if(!limit)  d=ans;
    return ans;
}
ll f(ll x)
{
    memset(dp,-1,sizeof(dp));
    cnt=0;
    while(x)
    {
        a[++cnt]=x%10;
        x/=10;
    }
    return dfs(cnt,0,true,true);
}
void solve()
{
    memset(a,0,sizeof(a));
    ll ans=0;
    ll x,y;     std::cin>>x>>y;
    for(int i=0;i<10;i++)
    {
        digit=i;
        ll l=f(x-1),r=f(y);
        ans+=i*(r-l);
    }
    std::cout<<ans<<"\n";
}
int main() {
    std::ios::sync_with_stdio(false);
    int t=1;
    memset(dp,-1,sizeof(dp));
    std::cin>>t;
    while(t--)solve();
    return 0;
}

---

因为是保存在Typora上的，现在已经有5000多字了，已经开始卡了，所以会分多期。