[数据结构与算法] DP小题单【1】

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> DP小题单【1】 -> 正文阅读

[数据结构与算法]DP小题单【1】

很适合掌握基础DP板子之后的新手练习。
DP题单：DP.beginner
DP题单：DP.middle
题目顺序打乱，按类型排序。

P1280 尼克的任务——状态划分为时间轴

尼克链接
题意 : 给定时间轴为 n 中选 k 个任务，每个任务有起始和持续时间。 k 个任务到达后，同一个起始时间尼克可以挑选一个任务，其他任务交由别人处理，通过合理选择任务就可以得到一些任务之间的空隙——闲暇时间。求闲暇时间的最大值。

状态表示: $f [i] 表示 i ? n 的时间内得到的闲暇时间最大值$
状态定义反向的原因是我们枚举左端点方便枚举，而且最终状态f[1]方便表示，如果正向枚举还要考虑最后的任务持续时间超过 n 的一些状态。

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int N = 1e4 + 10;
vector<vector<int>> a(N);
bool st[N];
int f[N];
int n, m;
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int aa, b;
        cin >> aa >> b;
        a[aa].push_back(b);
        st[aa] = 1;
    }
    for (int i = n; i >= 1; i--) {
        if (st[i]) {
            for (int j = 0; j < a[i].size(); j++) {
                int x = a[i][j];
                f[i] = max(f[i], f[i + x]);
            }
        } else {
            f[i] = f[i + 1] + 1;
        }
    }
    cout << f[1] << endl;
}

其他划分时间轴题目+题解：饥饿的奶牛
编辑距离 这道题以前发过：动态规划
加分二叉树 ：加分二叉树
类似于递归和区间dp的。

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int N = 1e2+10;
#define int long long
int ans=-1;
int a[N],f[N],n,m;
int score[N][N],num[N][N];
int dfs(int l,int r)
{
    if(l>r)  return 1;
    if(l==r) {num[l][l]=l;return a[l];}
    if(score[l][r]) return score[l][r];
    int sum=1;
    for(int i=l;i<=r;i++)
    {
        if(dfs(l,i-1)*dfs(i+1,r)+a[i]>sum)
        {
            sum=dfs(l,i-1)*dfs(i+1,r)+a[i];
            num[l][r]=i;
        //    cout<<"sum = "<<sum<<" i = "<<i<<endl;
        }
    }
    ans=max(ans,sum);
    return score[l][r]=sum;
    
}
void print(int l,int r)
{
    if(l>r) return ;
    cout<<num[l][r]<<' ';
    print(l,num[l][r]-1);
    print(num[l][r]+1,r);
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    dfs(1,n);
    cout<<ans<<endl;
    print(1,n);
}

P1077 [NOIP2012 普及组] 摆花
完全背包求方案数：

#include <algorithm>
#include<cstring>
#include <iostream>
using namespace std;
const int mod = 1e6 + 7;
const int N = 110;
int n, m;
int v[N], w[N], s[N];
int f[N][N];
int main() {
    cin >> n >> m;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
    }  
    memset(f,0,sizeof f); 
    for(int i =0;i<=n;i++) f[i][0] =1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            for(int k = 0 ; k <= s[i]&&k<=j;k++)
            {
                f[i][j] = (f[i][j] + f[i-1][j-k])%mod; 
                //cout<<" f[i][j] = "<<f[i][j]<<" i = "<<i<<" j = "<<j<<" k = "<<k<<endl; 
            }
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

木棍加工——dp+单调栈+二分

~~简单但很重要~~
题意：
在这里插入图片描述

题目链接：木棍加工
思路：如果按左端点排序，该问题就可以转化为求上升子序列个数问题，准备时间恰好是这个个数。
类似题目：
acwing友好城市
 合唱队形
类似的最长上升子序列问题有很多，但是比如这个合唱队形和y总讲的友好城市的话做法是 $n^2$ 的，单调栈和二分可以把时间复杂度控制在 $n ? l o g (n)$ ，所以就不展示 $n^2$ 求最长上升子序列的代码了。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5e3+10;
#define int long long
struct node
{
    int a,b;
}e[N];
int n;
int f[N],b[N];
int a[100];
bool cmp(node a,node b){return a.b<b.b;}
int check(int ll,int rr,int x)//小于等于x的第一个数
{
    int l=ll,r=rr;
    while(l<r)
    {
        int mid=l+r>>1;
        if(b[mid]>x) l=mid+1;
        else r=mid;
    }
    return l;
}
signed main()
{   
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int a,b;
        cin>>a>>b;
        e[i]={a,b};
    }
    sort(e+1,e+1+n,cmp);
    int ct=1;
    b[1]=e[1].a;
    for(int i=2;i<=n;i++)
    {   
        int j=check(1,ct,e[i].a);
        if(b[j]<=e[i].a) b[j]=e[i].a;
        else b[++ct]=e[i].a;
    }
    cout<<ct<<endl;
}

P1273 有线电视网——树形DP之树上背包

P1273链接
题意：如图，给定一个信号点 1 ，然后发送信号，叶子结点是观众，观众会给此次观影交钱，而每一条边都有一定的传输费用，我们希望电视台不亏本的情况下拥有的观众尽可能多。
思路：不亏本的话只要最后的盈利 > 0 即可，也就是说我们定义 $f [i] [j] 表示以 i 为根的子树中，选择 j 个用户的最大盈利$ ，最后我们遍历 $f [1] [i]$ ，只要它大于0，我们就可以增加 i ，找到盈利为正的最大人数即可。
$对于 f [i] [j] 的状态转移就是基础的树上背包板子。$
在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
const int N = 3010;
int n,m,ne[N],e[N],w[N],h[N],f[N][N],idx;
int val[N];//val表示叶子结点用户交的钱
int dfs(int u)
{
    if(u>=n-m+1)
    {
        f[u][1]=val[u];
        return 1;
    }
    int size=0;//当前树的用户个数
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        int now=dfs(j);//当前子树的用户个数
        size+=now;
        for(int k=size;k>=1;k--)
        {
            for(int s=0;s<=now;s++)
            {
                if(s<=k)
                f[u][k]=max(f[u][k],f[j][s]+f[u][k-s]-w[i]);
            }
        }
    }
    return size;
}
void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int main()
{
    memset(f,-0x3f,sizeof f);
    memset(h, -1, sizeof h);
    cin>>n>>m;
    for(int i=1;i<=n-m;i++)
    {
        int kk;  cin>>kk;
        while(kk--)
        {
            int b,ww;
            cin>>b>>ww;
            add(i,b,ww);
        }
    }
    for(int i=1;i<=n;i++)  f[i][0]=0;
    for(int i=n-m+1;i<=n;i++) cin>>val[i];
    //for(int i=n-m+1;i<=n;i++) cout<<val[i]<<endl;
    dfs(1);
    for(int i=m;i>=1;i--)
    {
     //   cout<<f[1][i]<<endl;
        if(f[1][i]>=0)  {cout<<i<<endl;return 0;}
    }
}

树上背包——有依赖板子题

选课链接
把必选的空间提前预处理出来，状态转移的时候只更新总空间减掉必选空间即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 700;
int n, m, idx, f[N][N], ne[N], w[N], e[N], h[N];
void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; }
void dfs(int u) {
    for(int i = 1;i <= m; i++)  f[u][i] = w[u];
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        dfs(j);
        for (int k = m; k >= 1; k--) {
            for (int s = 0; s <= k - 1; s++) {
                f[u][k] = max(f[u][k], f[j][s] + f[u][k - s]);
            }
        }
    }
}
int main() {
    memset(h, -1, sizeof h);
    cin >> n >> m;
    m++;// 0 号点相当于必选
    for (int i = 1; i <= n; i++) {
        int k, ww;
        cin >> k >> ww;
        add(k, i);
        w[i] = ww;
    }
    // for(int i=0;i<=n;i++) cout<<w[i]<<endl;
    dfs(0);
    cout << f[0][m] << endl;
}

P4933 大师——线性DP【升序求方案】

大师链接
题意：给定一个数列，让你求里面所有的等差序列的方案数，即左至右可以挑出一些数字 , 如果该序列是等差序列，则视为合法方案。
思路：~~这道题的难点都在状态的构造上，如果状态想对了这道题就很简单，作为一道蓝题比较水。~~
首先我们要知道一个性质，我们在做DP状态的递推式的时候经常用到。
就是当我们对一个升序序列求方案数 , 我们方案构造为前 i 个数，且当前 i 这个数字必选。我们很容易可以知道 $f [i] = f [i ? 1] + 1$ 比如给你一个序列 $[1, 2, 3]$ 已知以 3 结尾的递增子序列有三个 $[1, 2, 3], [2, 3], [3]$ 那么显然以 4 结尾的递增子序列有四个不多解释。
所以这个题的等差序列的递推关系也是这样表示。
状态设计： $f [i] [j]$ 表示前i个数，以 i 结尾，公差为d 的合法方案数，我们设计状态的时候要留意题目给的数据范围，这个公差和 n 的范围其实已经帮我们想好了一种可行的状态表示。
因为状态划分的依据是以 i 结尾的等差序列方案数，所以我们应该把 i 结尾的方案累加一遍，但是因为有重复, $f [j] [d] + 1$ 不一定是 $f [i] [d]$ 所以我们每次累加的答案相当于一条路径，每次只累加 $f [j] [d] + 1$ 即可。

#include<bits/stdc++.h>
using namespace std;
const int M=4e4+10;
const int N=1e3+10;
const int mod=998244353;
#define int long long
int f[N][M];
int a[N];
signed main()
{
    int n;
    cin>>n;
    int ans=n;//先把每个元素单独的贡献加起来
    for(int fi=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
    {   
        for(int j=1;j<i;j++)
        {       
            int d=a[i]-a[j];
            if(d<0) d+=4e4;
            int t=f[j][d]+1;//每一个之前的方案与当前字符新形成的贡献
            f[i][d]=(f[i][d]+f[j][d]+1)%mod;//因为有重复{1 2 3 3 4 5}。所以把重复的方案都记录到当前这个下标 i = 4 上
            ans=(ans+f[j][d]+1)%mod;//对于5来说，因为4已经把所有不重复的方案记录下来了，后边的{4 5}这个子序列对答案只有一个不重复的+1
        }
    }
    cout<<ans<<endl;
}

数位DP——dfs写法

数位dp的板子题很多，acwing上的几道题基本上都是板子题。
这里暂不详细讲解数位dp的细节。

1081. 度的数量
在这里插入图片描述

把一个数分解为 K 个互不相同的 B 的整数次幂之和。首先互不相同这四个字我们非常喜欢，因为这意味着把一个数按照B进制分解之后，它的每一位的次幂只能是 0 或者 1 （思考一下) 。所以我们就看它选择的 0 和 1 的数字的数量是不是等于K即可。

#include<bits/stdc++.h>
using namespace std;
int n,m,b,k;
const int N=200;
int a[N],dp[N][N],mod;
int dfs(int pos,int cnt,int limit)
{
    if(!pos) return cnt==k;
    if(!limit && dp[pos][cnt]!=-1) return dp[pos][cnt];
    int res=0, up = limit ? min(a[pos],1) : 1;
    for(int i=0;i<=up;i++)
    {
        if(cnt+i>k) continue;
        res+=dfs(pos-1,cnt+i,limit && i== a[pos]);
    }
    return limit ? res : dp[pos][cnt] =  res ; 
}
int cul(int x)
{
    memset(dp,-1,sizeof dp);
    int len=0;
    while(x)
    {
        a[++len]=x%b;
        x/=b;
    }
    return dfs(len,0,1);
}
int main()
{
    while(cin>>n>>m>>k>>b)
    {
        cout<<cul(m)-cul(n-1)<<endl;
    }
}

~~先介绍几个板子水一水~~
数字游戏
在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=20;
int a[N],dp[N][N];
int dfs(int pos,int pre,int limit)
{
    if(!pos) return 1;
    if(!limit&&dp[pos][pre]!=-1)  return dp[pos][pre];
    int res=0,up = limit ? a[pos] : 9;
    for(int i=0;i<=up;i++)
    {
        if(pre>i)  continue;
        res+=dfs(pos-1,i,limit&&i==up);
    }  
    return limit ? res : dp[pos][pre]=res;
}
int cul(int x)
{
    memset(dp,-1,sizeof dp);
    int len=0;
    while(x)
    {
        a[++len]=x%10;
        x/=10;
    }
    return dfs(len,-1,1);
}
int main()
{
    while(cin>>n>>m)
    {
        cout<<cul(m)-cul(n-1)<<endl;
    }
}

Windy数
记前驱
在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
const int N=15;
int a[N],dp[N][N];
int dfs(int pos,int pre,int limit,int lead)
{
    if(!pos) return 1;
    if(!limit&&!lead&&dp[pos][pre]!=-1)  return dp[pos][pre];
    int res=0, up = limit ? a[pos]:9;
    for(int i=0;i<=up;i++)
    {
        if(abs(pre- i)<2) continue;
        if(lead&&!i)
        res+=dfs(pos-1,-2,limit&&i==up,1);
        else 
        res+=dfs(pos-1,i,limit&&i==up,0);
    }
    return limit||lead ? res:dp[pos][pre]=res;
}
int cul(int x)
{
    memset(dp,-1,sizeof dp);
    int len=0;
    while(x)
    {
        a[++len]=x%10;
        x/=10;
    }
    return dfs(len,-2,1,1);
}
int main()
{
    int n,m;
    cin>>n>>m;
    cout<<cul(m)-cul(n-1)<<endl;
}

数字游戏二
统计求和

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=200;
int a[N],dp[N][N],mod;
int dfs(int pos,int sum,int limit)
{
    if(!pos)   return sum%mod ==0;
    if(!limit && dp[pos][sum] != -1 ) return dp[pos][sum];
    int res=0,up = limit ? a[pos] : 9;
    for(int i=0;i<=up;i++)
    {
        res=res+dfs(pos-1,sum+i,limit&&i==up);   
    }
    return limit ? res : dp[pos][sum] = res;
}
int cul(int x)
{
    memset(dp,-1,sizeof dp);
    int len=0;
    while(x)
    {
        a[++len]=x%10;
        x/=10;
    }
    return dfs(len,0,1);
}
int main()
{
    while(cin>>n>>m>>mod)
    {
        cout<<cul(m)-cul(n-1)<<endl;
    }

}

不要62

#include<bits/stdc++.h>
using namespace std;
const int N=15;
int a[N],dp[N][N];
int dfs(int pos,int pre,int limit)
{
    if(!pos) return 1;
    if(!limit&&dp[pos][pre]!=-1)  return dp[pos][pre];
    int res=0, up = limit ? a[pos]:9;
    for(int i=0;i<=up;i++)
    {
        if(i==4||(i==2&&pre==6))  continue;
        res+=dfs(pos-1,i,limit&&i==up);
    }
    return limit ? res:dp[pos][pre]=res;
}
int cul(int x)
{
    memset(dp,-1,sizeof dp);
    int len=0;
    while(x)
    {
        a[++len]=x%10;
        x/=10;
    }
    return dfs(len,-1,1);
}
int main()
{
    int n,m;
    while(cin>>n>>m,n||m)
    {
        cout<<cul(m)-cul(n-1)<<endl;
    }
}

~~OK，当我们把这些板子练熟之后，再来展示几道落谷的紫（水）题。~~
Classy Numbers
这确实是道水题，开个玩笑。
看一下这一道：同类分布
在这里插入图片描述

这道题看起来就正常多了，在数字游戏二中最后判断 sum % N 是否成立，在这个题中我们如果像这样把原数递归下去会爆数组：

因为我们数字的位数不长，所以我们可以枚举它的个位数字之和，一定小于等于9倍的数字长度！
所以我们要在外边枚举模数+在过程中取模。
如果一个数的个位数字和恰好是此次枚举的mod,且底层sum==0，说明方案合法。

#include<bits/stdc++.h>
using namespace std;
const int N=200;
#define int long long 
int a[N],dp[20][N][N];
int n,m,l,r,t,mod;
int dfs(int pos,int cnt,int limit,int sum)//cnt为各位数之和，sum为当前原数取mod后为谁
{
    if(!pos)  
    {
        if(cnt==mod&&sum==0) return 1;
        return 0;
    }
    if(!limit && dp[pos][cnt][sum] != -1) return dp[pos][cnt][sum];
    int res=0 , up = limit ? a[pos] : 9 ;
    for(int i = 0 ; i <= up ; i++)
    {
        res+=dfs(pos-1,cnt+i,limit&&i==up,(sum*10+i)%mod);
    }
    return limit ? res : dp[pos][cnt][sum]=res;
}
int cul(int x)
{
    int len=0;
    while(x) a[++len]=x%10,x/=10;
    int ret=0;
    for(mod=1;mod<=9*len;mod++)//外面枚举模数
    {
        memset(dp,-1,sizeof dp);
        ret+=dfs(len,0,1,0);
    }
    return ret;
}
signed main()
{
    cin>>l>>r;
    cout<<cul(r)-cul(l-1)<<endl;
}

P4317 花神的数论题
在这里插入图片描述
sum[i]表示二进制中1的个数，如果我们正着做，枚举区间中的每个数，返回二进制1的个数再相乘是行不通的。
这道题和上道题思路一样。
因为二进制表示的数中，上限和下限范围很小，所以我们可以枚举二进制中 1 的个数，看看有哪些数符合条件，把它们乘起来就行了！

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=55;
const int mod=10000007;
int a[N],dp[N][N];//前 i 个数，二进制 1 的个数， 
int ans=1;
int qmi(int a,int k)
{
    int res=1;
    while(k)
    {
        if(k&1)  res=res*a%mod;
        a=a*a%mod;
        k>>=1;
    }
    return res;
}
int dfs(int pos,int cnt,int limit,int num)//找二进制个数为 num 的数有几个
{
    if(!pos) return cnt==num;
    if(!limit&&dp[pos][cnt]!=-1)  return  dp[pos][cnt];
    int res = 0,up = limit ?  a[pos] : 1;
    for(int i=0;i<=up;i++)
    {
        if(i==1)  res=(res+dfs(pos-1,cnt+1,limit&&i==a[pos],num));
        else  res=(res+dfs(pos-1,cnt,limit&&i==a[pos],num));
    }
    return  limit ? res : dp[pos][cnt] = res;
}
int cul(int x)
{
    int len=0;
    while(x)
    {
        a[++len]=x%2;
        x/=2;
    }
    for(int j=1;j<=50;j++)
    {
        memset(dp,-1,sizeof dp);
        ans=(ans*qmi(j,dfs(len,0,1,j)))%mod;
    }
    return ans%mod;
}
signed main()
{
    int n;
    cin>>n;
    cout<<cul(n)<<endl;
}

再来一道紫（水）题：P4124 [CQOI2016]手机号码
在这里插入图片描述

题意就是：求一个区间中，满足：要出现至少 3 个相邻的相同数字且号码中不能同时出现 8 和 4 的数有多少。
思路也非常简单，直接开两个前驱标记，然后再搞两个变量标记 8 和 4 的出现情况。
但是这道题的状态数组必须开到 6 维，有时候我偷懒会少开几维，但这个题就WA 了，因为状态有重叠，答案会重复加，所以在时间和空间允许的情况下，数位 dp 多开几维，维度尽可能接近状态转移的参数个数。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 30;
int l,r;
int dp[N][N][N][2][2][2];
int a[N];//sign用来标识是否存在连续三个相邻的相同数字
int dfs(int pos,int pre1,int pre2,int limit,int sign,int s4,int s8)
{
    if(s4&&s8)  return 0;
    if(!pos)    return sign;
    if(!limit&&dp[pos][pre2][pre1][sign][s4][s8]!=-1) return dp[pos][pre2][pre1][sign][s4][s8];
    int res=0,up = limit ? a[pos]:9;
    for(int i=0;i<=up;i++)
    {
        if(i==pre1&&i==pre2)
        {
            if(i==4)
            res+=dfs(pos-1,pre2,i,limit&&i==up,1,1,s8);
            else if(i==8)
            res+=dfs(pos-1,pre2,i,limit&&i==up,1,s4,1);
            else  res+=dfs(pos-1,pre2,i,limit&&i==up,1,s4,s8);
        }
        else
        {
            if(i==4)
            res+=dfs(pos-1,pre2,i,limit&&i==up,sign,1,s8);
            else if(i==8)
            res+=dfs(pos-1,pre2,i,limit&&i==up,sign,s4,1);
            else res+=dfs(pos-1,pre2,i,limit&&i==up,sign,s4,s8);
        }
    }
    return limit ? res:dp[pos][pre2][pre1][sign][s4][s8]=res;
}
int cul(int x)
{
    memset(dp,-1,sizeof dp);
    int len=0;
    while(x)
    {
        a[++len]=x%10;
        x/=10;
    }
    int ans=0;
    if(len!=11) return 0;//如果l=1e10,l-1就不是电话号码了
    for(int i=1;i<=a[len];i++)
    {
        if(i==4)
        ans+=dfs(len-1,-1,i,i==a[len],0,1,0);
        else if(i==8)
        ans+=dfs(len-1,-1,i,i==a[len],0,0,1);
        else ans+=dfs(len-1,-1,i,i==a[len],0,0,0);
    }
    return ans;
}
signed main()
{
    cin>>l>>r;
    cout<<cul(r)-cul(l-1)<<endl;
}

包括要考虑前导零的统计数位出现次数的这个题：P2602数字计数

#include<bits/stdc++.h>
using namespace std;
#define int long long
int mp[40];
int l,r,a[40],dp[40][40];
int dfs(int pos,int limit,int sign,int lead,int num,int cnt)
{
    //cout<<a[pos]<<endl;
    if (!pos) return cnt;
    if(!limit&&!lead&&dp[pos][cnt]!=-1) return dp[pos][cnt];
    int up=limit ? a[pos]: 9 , res=0;
    for(int i=0;i<=up;i++)
    {
     //   cout<<i<<endl;
       // cout<<" a[pos] = "<<a[pos]<<" a[pre] = "<<pre<<endl;
        if(lead&&!i)
        {
            res+=dfs(pos-1,limit&&i==up,sign,1,num,cnt);
        }
        else
        {
            res+=dfs(pos-1,limit&&i==up,sign,0,num,cnt+(i==num));
        }
    }
    return limit||lead ? res:dp[pos][cnt]=res;
}
void cul(int x,int sign)
{
   // memset(dp,-1,sizeof dp);
    int len=0;
    while(x)
    {
        a[++len]=x%10;
        x/=10;
    }
    for(int i=0;i<=9;i++)
    {
        memset(dp,-1,sizeof dp);
        if(sign)
        mp[i]+=dfs(len,1,sign,1,i,0);
        else mp[i]-=dfs(len,1,sign,1,i,0);
    }
}
signed main()
{
    int n,m;
    cin>>n>>m;
    cul(m,1);
    cul(n-1,0);
    for(int i=0;i<=9;i++)
    {
        cout<<mp[i]<<' ';
    }
}