首页算法

# 动态规划

动态规划（英语：Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划常常适用于有重叠子问题 [1] 和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。

通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

# 概述

动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费不必要的时间。

动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解（对有些问题这个要求并不能完全满足，故有时需要引入一定的近似）。简单地说，问题能够分解成子问题来解决。

# 适用情况

  1. 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。
  2. 无后效性。即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。
  3. 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率，降低了时间复杂度。

（以上全是废话）

# 单调队列优化多重背包

6. 多重背包问题 III - AcWing 题库

# 问题描述

​ 你有 nn 个物品，每个物品重量为 wiw_i，价值为 viv_i，数量为 kik_i。你有一个承重上限为 WW 的背包，现在要求你在不超过重量上限的情况下选取价值和尽可能大的物品放入背包。求最大价值。

不了解背包 DP 的请先阅读 背包 DP。设 fi,jf_{i,j} 表示前 ii 个物品装入承重为 jj 的背包的最大价值，朴素的转移方程为

fi,j=max⁡k=0ki(fi−1,j−k×wi+vi×k)f_{i,j}=\max_{k=0}^{k_i}(f_{i-1,j-k\times w_i}+v_i\times k)

时间复杂度 O(W∑ki)O(W\sum k_i)。

# 思考过程

考虑优化 fif_i 的转移。为方便表述，设 gx,y=fi,x×wi+y,gx,y′=fi−1,x×wi+yg_{x,y}=f_{i,x\times w_i+y},g'_{x,y}=f_{i-1,x\times w_i+y}，则转移方程可以表示为：

gx,y=max⁡k=0ki(gx−k,y′+vi×k)g_{x,y}=\max_{k=0}^{k_i}(g'_{x-k,y}+v_i\times k)

设 Gx,y=gx,y′−vi×xG_{x,y}=g'_{x,y}-v_i\times x。则方程可以表示为：

gx,y=max⁡k=0ki(Gx−k,y)+vi×xg_{x,y}=\max_{k=0}^{k_i}(G_{x-k,y})+v_i\times x

这样就转化为一个经典的单调队列优化形式了。Gx,yG_{x,y} 可以 O(1)O(1) 计算，因此对于固定的 yy，我们可以在 O(⌊Wwi⌋)O\left( \left\lfloor \dfrac{W}{w_i} \right\rfloor \right) 的时间内计算出 gx,yg_{x,y}。因此求出所有 gx,yg_{x,y} 的复杂度为 O(⌊Wwi⌋)×O(wi)=O(W)O\left( \left\lfloor \dfrac{W}{w_i} \right\rfloor \right)\times O(w_i)=O(W)。这样转移的总复杂度就降为 O(nW)O(nW)。

# solution

/*
 * @author: yihang_01
 * @Date: 2024-04-25 21:31:58
 * @LastEditailime: 2024-04-25 22:00:00
 * QwQ 加油加油
 */
#include <bits/stdc++.h>
using std::cin;
using std::cout;
#ifdef ONLINE_JUDGE
    constexpr int N = 1e5+7;
#else
    constexpr int N = 1e3+7;
#endif
int n,V,v,s,w,q[N],tail,head;
std::vector<int> dp1(N),dp2(N);
void solve(){
    cin>>n>>V;
    for(int i=1;i<=n;i++){
        cin>>v>>w>>s;
        for (int r = 0; r < v; ++ r)
        {
            int head = 0, tail = -1;
            for (int j = r; j <= V; j += v)
            {
                while (head <= tail && j - q[head] > s * v) head ++ ;
                while (head <= tail && dp2[q[tail]] + (j - q[tail]) / v * w <= dp2[j]) -- tail;
                q[ ++ tail] = j;
                dp1[j] = dp2[q[head]] + (j - q[head]) / v * w;
            }
        }
        dp2=dp1;
    }
    cout<<dp1[V]<<'\n';
}
signed main(){
    std::ios::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
    int T=1;
    //cin>>T;
    while(T--){  solve();  }
    //system("pause");
    return 0;
}
# 例题


# 树形 dp


没有上司的舞会


# 问题描述


​    某大学有 nn 个职员，编号为 1∼N1 \sim N。他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 aia_i，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。


# 思考过程


我们设 f(i,0/1)f(i,0/1) 代表以 ii 为根的子树的最优解（第二维的值为 0 代表 ii 不参加舞会的情况，1 代表 ii 参加舞会的情况）。


对于每个状态，都存在两种决策（其中下面的 xx 都是 ii 的儿子）：


    

  • 上司不参加舞会时，下属可以参加，也可以不参加，此时有 f(i,0)=∑max⁡{f(x,1),f(x,0)}f(i,0) = \sum\max \{f(x,1),f(x,0)\}；
    • 

  • 上司参加舞会时，下属都不会参加，此时有 f(i,1)=∑f(x,0)+aif(i,1) = \sum{f(x,0)} + a_i。
    • 



我们可以通过 DFS，在返回上一层时更新当前结点的最优解。


# solution


#include <bits/stdc++.h>
using std::cin;
using std::cout;
#ifdef ONLINE_JUDGE
    constexpr int N = 6e3+7;
#else
    constexpr int N = 1e3+7;
#endif
int n,r[N],l,k,dp[N][3],root,vis[N];
std::vector<int> g[N];
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>r[i];
    for(int i=1;i<n;i++){
        cin>>l>>k;
        g[k].emplace_back(l);
        vis[l]=1;
    }
    for(int i=1;i<=n;i++) if(!vis[i]) root=i;
    auto dfs=[&](int u,auto self)->void{
        dp[u][1]=r[u];
        for(auto v:g[u]){
            self(v,self);
            dp[u][0]+=std::max(dp[v][0],dp[v][1]);
            dp[u][1]+=dp[v][0];
        }
    };
    dfs(root,dfs);
    cout<<std::max(dp[root][0],dp[root][1])<<'\n';
}
signed main(){
    std::ios::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
    int T=1;
    // cin>>T;
    while(T--){  solve();  }
    //system("pause");
    return 0;
}
例题：Sasha and a Walk in the City


# 状压 dp


# 定义


状压 DP 是动态规划的一种，通过将状态压缩为整数来达到优化转移的目的。


「SCOI2005」互不侵犯


# 问题描述


在 N×NN\times N 的棋盘里面放 KK 个国王（1≤N≤9,1≤K≤N×N1 \leq N \leq 9, 1 \leq K \leq N \times N），使他们互不攻击，共有多少种摆放方案。


国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 $8$ 个格子。



# 解释


设 f(i,j,l)f(i,j,l) 表示前 ii 行，第 ii 行的状态为 jj，且棋盘上已经放置 ll 个国王时的合法方案数。


对于编号为 jj 的状态，我们用二进制整数 sit(j)sit(j) 表示国王的放置情况，sit(j)sit(j) 的某个二进制位为 00 表示对应位置不放国王，为 11 表示在对应位置上放置国王；用 sta(j)sta(j) 表示该状态的国王个数，即二进制数 sit(j)sit(j) 中 11 的个数。例如，如下图所示的状态可用二进制数 100101100101 来表示（棋盘左边对应二进制低位），则有 sit(j)=100101(2)=37,sta(j)=3sit(j)=100101_{(2)}=37, sta(j)=3。




/*
 * @author: yihang_01
 * @Date: 2023-10-15 21:40:19
 * @LastEditTime: 2024-04-27 23:25:59
 * QwQ 加油加油
 */
#include <bits/stdc++.h>
using namespace std;
#define int long long
int bit[2005], cbit[2005], cnt, dp[10][2005][30], n, k;
void dfs(int x, int num, int cur) {
    if (cur >= n) {
        bit[++cnt] = x;
        cbit[cnt] = num;
        return;
    }
    dfs(x, num, cur + 1);
    dfs(x + (1 << cur), num + 1, cur + 2);
}
bool check(int x, int y) {
    if (bit[x] & bit[y]) return false;
    if (bit[x] & (bit[y] << 1)) return false;
    if ((bit[x] << 1) & bit[y]) return false;
    return true;
}
void solve() {
    cin >> n >> k;
    dfs(0, 0, 0);
    for (int i = 1; i <= cnt; i++) dp[1][i][cbit[i]] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= cnt; j++) {      // 当前行
            for (int x = 1; x <= cnt; x++) {  // 上一行
                if (check(j, x)) {
                    for (int l = cbit[j]; l <= k; l++)
                        dp[i][j][l] += dp[i - 1][x][l - cbit[j]];
                }
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= cnt; i++) ans += dp[n][i][k];
    cout << ans << '\n';
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int T = 1;  // cin>>T;
    while (T--) {
        solve();
    }
    // system("pause");
    return 0;
}
# 例题：Keyi LIkes Reading


# 区间 dp


# 定义


区间类动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。


令状态 f(i,j)f(i,j) 表示将下标位置 ii 到 jj 的所有元素合并能获得的价值的最大值，那么 f(i,j)=max⁡{f(i,k)+f(k+1,j)+cost}f(i,j)=\max\{f(i,k)+f(k+1,j)+cost\}，costcost 为将这两组元素合并起来的价值。


# 性质


区间 DP 有以下特点：


合并：即将两个或多个部分进行整合，当然也可以反过来；


特征：能将问题分解为能两两合并的形式；


求解：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。


# 解释


# 例题：石子合并 


# 题目描述


​	在一个环上有 nn 个数 a1,a2,…,ana_1,a_2,\dots,a_n，进行 n−1n-1 次合并操作，每次操作将相邻的两堆合并成一堆，能获得新的一堆中的石子数量的和的得分。你需要最大化你的得分。


需要考虑不在环上，而在一条链上的情况。


令 f(i,j)f(i,j) 表示将区间 [i,j][i,j] 内的所有石子合并到一起的最大得分。


写出 状态转移方程：f(i,j)=max⁡{f(i,k)+f(k+1,j)+∑t=ijat} (i≤k<j)f(i,j)=\max\{f(i,k)+f(k+1,j)+\sum_{t=i}^{j} a_t \}~(i\le k<j)


令 sumisum_i 表示 aa 数组的前缀和，状态转移方程变形为 f(i,j)=max⁡{f(i,k)+f(k+1,j)+sumj−sumi−1}f(i,j)=\max\{f(i,k)+f(k+1,j)+sum_j-sum_{i-1} \}。


# 怎样进行状态转移


由于计算 f(i,j)f(i,j) 的值时需要知道所有 f(i,k)f(i,k) 和 f(k+1,j)f(k+1,j) 的值，而这两个中包含的元素的数量都小于 f(i,j)f(i,j)，所以我们以 len=j−i+1len=j-i+1 作为 DP 的阶段。首先从小到大枚举 lenlen，然后枚举 ii 的值，根据 lenlen 和 ii 用公式计算出 jj 的值，然后枚举 kk，时间复杂度为 O(n3)O(n^3)


# 怎样处理环


题目中石子围成一个环，而不是一条链，怎么办呢？


方法一：由于石子围成一个环，我们可以枚举分开的位置，将这个环转化成一个链，由于要枚举 nn 次，最终的时间复杂度为 O(n4)O(n^4)。


方法二：我们将这条链延长两倍，变成 2×n2\times n 堆，其中第 ii 堆与第 n+in+i 堆相同，用动态规划求解后，取 f(1,n),f(2,n+1),…,f(n−1,2n−2)f(1,n),f(2,n+1),\dots,f(n-1,2n-2) 中的最优值，即为最后的答案。时间复杂度 O(n3)O(n^3)。


# solution:


#include <bits/stdc++.h>
using std::cin;
using std::cout;
#ifdef ONLINE_JUDGE
constexpr int N = 4e2 + 7;
#else
constexpr int N = 4e2 + 7;
#endif
int dp1[N][N], n, a[N], sum[N],dp2[N][N];
void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i], a[i + n] = a[i], sum[i] = sum[i - 1] + a[i];
    for(int i=n+1;i<=2*n;i++) sum[i]=sum[i-1]+a[i];
    
    for(int len = 2; len<=n; len++){
        for(int i=1;i<=2*n-len-1;i++){
            int j=i+len-1;
            dp1[i][j]=INT_MAX;
            for(int k=i;k<j;k++){
                dp1[i][j]=std::min(dp1[i][j],dp1[i][k]+dp1[k+1][j]+sum[j]-sum[i-1]);
                dp2[i][j]=std::max(dp2[i][j],dp2[i][k]+dp2[k+1][j]+sum[j]-sum[i-1]);
            }
        }
    }
    int ans1=INT_MAX,ans2=INT_MIN;
    for(int i=1;i<=n;i++){
        if(dp1[i][i+n-1]) ans1=std::min(ans1,dp1[i][i+n-1]);
        ans2=std::max(ans2,dp2[i][i+n-1]);
    }
    cout<<ans1<<'\n'<<ans2<<'\n';
}
signed main() {
    std::ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
    
    // system("pause");
    return 0;
}
例题：The Sports Festival


# 概率 dp


# 引入


概率 DP 用于解决概率问题与期望问题，建议先对 概率 & 期望 的内容有一定了解。一般情况下，解决概率问题需要顺序循环，而解决期望问题使用逆序循环，如果定义的状态转移方程存在后效性问题，还需要用到 高斯消元 来优化。概率 DP 也会结合其他知识进行考察，例如 状态压缩，树上进行 DP 转移等。


# DP 求概率


这类题目采用顺推，也就是从初始状态推向结果。同一般的 DP 类似的，难点依然是对状态转移方程的刻画，只是这类题目经过了概率论知识的包装。


# 例题 Codeforces 148 D Bag of mice


# 题目描述：


​	袋子里有 ww 只白鼠和 bb 只黑鼠，公主和龙轮流从袋子里抓老鼠。谁先抓到白色老鼠谁就赢，如果袋子里没有老鼠了并且没有谁抓到白色老鼠，那么算龙赢。公主每次抓一只老鼠，龙每次抓完一只老鼠之后会有一只老鼠跑出来。每次抓的老鼠和跑出来的老鼠都是随机的。公主先抓。问公主赢的概率。


# 过程


设 fi,jf_{i,j} 为轮到公主时袋子里有 ii 只白鼠，jj 只黑鼠，公主赢的概率。初始化边界，f0,j=0f_{0,j}=0 因为没有白鼠了算龙赢，fi,0=1f_{i,0}=1 因为抓一只就是白鼠，公主赢。

考虑 fi,jf_{i,j} 的转移：


    

  • 公主抓到一只白鼠，公主赢了。概率为 ii+j\frac{i}{i+j}；
    • 

  • 公主抓到一只黑鼠，龙抓到一只白鼠，龙赢了。概率为 ji+j⋅ii+j−1\frac{j}{i+j}\cdot \frac{i}{i+j-1}；
    • 

  • 公主抓到一只黑鼠，龙抓到一只黑鼠，跑出来一只黑鼠，转移到 fi,j−3f_{i,j-3}。概率为 ji+j⋅j−1i+j−1⋅j−2i+j−2\frac{j}{i+j}\cdot\frac{j-1}{i+j-1}\cdot\frac{j-2}{i+j-2}；
    • 

  • 公主抓到一只黑鼠，龙抓到一只黑鼠，跑出来一只白鼠，转移到 fi−1,j−2f_{i-1,j-2}。概率为 ji+j⋅j−1i+j−1⋅ii+j−2\frac{j}{i+j}\cdot\frac{j-1}{i+j-1}\cdot\frac{i}{i+j-2}；
    • 



考虑公主赢的概率，第二种情况不参与计算。并且要保证后两种情况合法，所以还要判断 i,ji,j 的大小，满足第三种情况至少要有 3 只黑鼠，满足第四种情况要有 1 只白鼠和 2 只黑鼠。


# solution


#include <bits/stdc++.h>
using namespace std;
 
#ifdef ONLINE_JUDGE
    constexpr int N = 1e3+7;
#else
    constexpr int N = 1e3+7;
#endif
int w,b;
long double dp[N][N];
 
void solve(){
    cin>>w>>b;
    for(int i=1;i<=w;i++)   dp[i][0]=1;
    for(int i=1;i<=w;i++){
        for(int j=1;j<=b;j++){
            dp[i][j]=1.0*i/(i+j);
            if(j>=3)    dp[i][j]+=1.0*j/(i+j)*1.0*(j-1)/(i+j-1)*1.0*(j-2)/(i+j-2)*dp[i][j-3];
            if(i>=1&&j>=2)  dp[i][j]+=1.0*j/(i+j)*1.0*(j-1)/(i+j-1)*1.0*i/(i+j-2)*dp[i-1][j-2];
        }
    }
    cout<<dp[w][b]<<'\n';
}
 
signed main(){
    ios::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
    cout<<fixed<<setprecision(10);
    int T=1;//cin>>T;
    while(T--){  solve();  }
    //system("pause");
    return 0;
}
例题：Club


# 数位 dp


# 引入


数位是指把一个数字按照个、十、百、千等等一位一位地拆开，关注它每一位上的数字。如果拆的是十进制数，那么每一位数字都是 0~9，其他进制可类比十进制。


数位 DP：用来解决一类特定问题，这种问题比较好辨认，一般具有这几个特征：


    

  1. 

    要求统计满足一定条件的数的数量（即，最终目的为计数）；
    

    2. 

  2. 

    这些条件经过转化后可以使用「数位」的思想去理解和判断；
    

    3. 

  3. 

    输入会提供一个数字区间（有时也只提供上界）来作为统计的限制；
    

    4. 

  4. 

    上界很大（比如 101810^{18}），暴力枚举验证会超时。
    

    5. 



数位 DP 的基本原理：


考虑人类计数的方式，最朴素的计数就是从小到大开始依次加一。但我们发现对于位数比较多的数，这样的过程中有许多重复的部分。例如，从 7000 数到 7999、从 8000 数到 8999、和从 9000 数到 9999 的过程非常相似，它们都是后三位从 000 变到 999，不一样的地方只有千位这一位，所以我们可以把这些过程归并起来，将这些过程中产生的计数答案也都存在一个通用的数组里。此数组根据题目具体要求设置状态，用递推或 DP 的方式进行状态转移。


数位 DP 中通常会利用常规计数问题技巧，比如把一个区间内的答案拆成两部分相减（即 ans[l,r]=ans[0,r]−ans[0,l−1]\mathit{ans}_{[l, r]} = \mathit{ans}_{[0, r]}-\mathit{ans}_{[0, l - 1]}）


那么有了通用答案数组，接下来就是统计答案。统计答案可以选择记忆化搜索，也可以选择循环迭代递推。为了不重不漏地统计所有不超过上限的答案，要从高到低枚举每一位，再考虑每一位都可以填哪些数字，最后利用通用答案数组统计答案。


接下来我们具体看几道题目。


# 例题：数字计数


# 题目描述：


​	给定两个正整数 a,ba,b，求在 [a,b][a,b] 中的所有整数中，每个数码（digit）各出现了多少次。


# 方法一


# 解释


发现对于满 i\mathit{i} 位的数，所有数字出现的次数都是相同的，故设数组 dpi\mathit{dp}_i 为满 ii 位的数中每个数字出现的次数，此时暂时不处理前导零。则有 dpi=10×dpi−1+10i−1\mathit{dp}_i=10 \times \mathit{dp}_{i−1}+10^{i−1}，这两部分前一个是来自前 i−1i-1 位数字的贡献，后一个是来自第 ii 位的数字的贡献。


有了 dp\mathit{dp} 数组，我们来考虑如何统计答案。将上界按位分开，从高到低枚举，不贴着上界时，后面可以随便取值。贴着上界时，后面就只能取 00 到上界，分两部分分别计算贡献。最后考虑下前导零，第 ii 位为前导 00 时，此时 11 到 i−1\mathit{i-1} 位也都是 00，也就是多算了将 i−1i-1 位填满的答案，需要额外减去。


# solution


/*
 * @author: yihang_01
 * @Date: 2024-04-27 23:55:29
 * @LastEditTime: 2024-04-27 23:55:34
 * QwQ 加油加油
 */
#include <bits/stdc++.h>
using namespace std;
const int N = 15;
typedef long long ll;
ll l, r, dp[N], mi[N];
ll ans1[N], ans2[N];
int a[N];
void solve(ll n, ll *ans) {
    ll tmp = n;
    int len = 0;
    while (n) a[++len] = n % 10, n /= 10;
    for (int i = len; i >= 1; --i) {
        for (int j = 0; j < 10; j++) ans[j] += dp[i - 1] * a[i];
        for (int j = 0; j < a[i]; j++) ans[j] += mi[i - 1];
        tmp -= mi[i - 1] * a[i], ans[a[i]] += tmp + 1;
        ans[0] -= mi[i - 1];
    }
}
int main() {
    scanf("%lld%lld", &l, &r);
    mi[0] = 1ll;
    for (int i = 1; i <= 13; ++i) {
        dp[i] = dp[i - 1] * 10 + mi[i - 1];
        mi[i] = 10ll * mi[i - 1];
    }
    solve(r, ans1), solve(l - 1, ans2);
    for (int i = 0; i < 10; ++i) printf("%lld ", ans1[i] - ans2[i]);
    return 0;
}
# 方法二


# 解释


此题也可以使用记忆化搜索。dpi\mathit{dp}_i 表示不贴上限、无前导零时，位数为 ii 的答案。


详见代码注释


# solution


#include <cstdio>  //code by Alphnia
#include <cstring>
#include <iostream>
using namespace std;
#define N 50005
#define ll long long
ll a, b;
ll f[15], ksm[15], p[15], now[15];
ll dfs(int u, int x, bool f0,
       bool lim) {  //u 表示位数，f0 是否有前导零，lim 是否都贴在上限上
  if (!u) {
    if (f0) f0 = 0;
    return 0;
  }
  if (!lim && !f0 && (~f[u])) return f[u];
  ll cnt = 0;
  int lst = lim ? p[u] : 9;
  for (int i = 0; i <= lst; i++) {  // 枚举这位要填的数字
    if (f0 && i == 0)
      cnt += dfs(u - 1, x, 1, lim && i == lst);  // 处理前导零
    else if (i == x && lim && i == lst)
      cnt += now[u - 1] + 1 +
             dfs(u - 1, x, 0,
                 lim && i == lst);  // 此时枚举的前几位都贴在给定的上限上。
    else if (i == x)
      cnt += ksm[u - 1] + dfs(u - 1, x, 0, lim && i == lst);
    else
      cnt += dfs(u - 1, x, 0, lim && i == lst);
  }
  if ((!lim) && (!f0)) f[u] = cnt;  // 只有不贴着上限和没有前导零才能记忆
  return cnt;
}
ll gans(ll d, int dig) {
  int len = 0;
  memset(f, -1, sizeof(f));
  while (d) {
    p[++len] = d % 10;
    d /= 10;
    now[len] = now[len - 1] + p[len] * ksm[len - 1];
  }
  return dfs(len, dig, 1, 1);
}
int main() {
  scanf("%lld%lld", &a, &b);
  ksm[0] = 1;
  for (int i = 1; i <= 12; i++) ksm[i] = ksm[i - 1] * 10ll;
  for (int i = 0; i < 9; i++) printf("%lld ", gans(b, i) - gans(a - 1, i));
  printf("%lld\n", gans(b, 9) - gans(a - 1, 9));
  return 0;
}
# 例题：不要 62




# 祝大家五一快乐！