题目链接:数字计数

  没啥好说的,裸裸的数位\(dp\)。

  先枚举当前是算数字\(x\)出现的次数,设\(f_{i,j}\)表示从高位往低位\(dp\),\(dp\)完了前\(i\)位之后\(x\)出现了\(j\)次的方案数。然后再加一维,表示当前这一位能否自由选数(也就是说之前是否是一路选最大值过来的)。转移分情况讨论一下就好了。

  注意这种写法还有一点情况,就是算\(0\)出现的次数时需要减去区间内前导\(0\)的个数。

  下面贴代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) using namespace std;
typedef long long llg; llg l,r,f[21][21][2],mi[21];
int a[21],b[21],l1,l2; void divide(llg x,int *s,int &len){
llg y=x; while(y) len++,y/=10;
for(int i=len;i;i--) s[i]=x%10,x/=10;
} llg work(int *s,int n,int x){
f[0][0][1]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=i;j++){
f[i][j][0]=f[i-1][j][0]*9;
if(j) f[i][j][0]+=f[i-1][j-1][0];
if(s[i]>x){
f[i][j][0]+=f[i-1][j][1]*(s[i]-1);
if(j) f[i][j][0]+=f[i-1][j-1][1];
}
else f[i][j][0]+=f[i-1][j][1]*s[i];
if(s[i]==x){
if(j) f[i][j][1]=f[i-1][j-1][1];
else f[i][j][1]=0;
}
else f[i][j][1]=f[i-1][j][1];
}
llg now=0;
for(int i=1;i<=n;i++) now+=i*(f[n][i][0]+f[n][i][1]);
if(!x){
mi[0]=1; now-=n;
for(int i=1;i<n;i++) mi[i]=mi[i-1]*10;
for(int i=1;i<n;i++) now-=(mi[i]-mi[i-1])*(n-i);
}
return now;
} int main(){
File("a");
scanf("%lld %lld",&l,&r); l--;
divide(l,a,l1); divide(r,b,l2);
for(int i=0;i<=9;i++){
if(i) printf(" ");
printf("%lld",work(b,l2,i)-work(a,l1,i));
}
return 0;
}

最新文章

  1. 在文件夹中 的指定类型文件中 查找字符串(CodeBlocks+GCC编译,控制台程序,仅能在Windows上运行)
  2. SQL(触发器)
  3. IT菜鸟的第2天(输入输出,数据类型,运算符的使用)
  4. vs代码段快捷键设置
  5. xcode6中如何添加pch文件
  6. arm-none-eabi-gcc,makefile,stm官方库构建stm32f4xx工程
  7. 编译SASS
  8. vue项目,axios请求图片接口,接口返回的是文件流的形式,如何转换成图片?
  9. Hadoop高可用集群
  10. [原创]基于Zynq Linux环境搭建(二)
  11. (Beta)Let&#39;s-M2后分析报告
  12. Java 实现String语句的执行(Jexl)
  13. java.lang.NoSuchMethodException: .&lt;init&gt;()
  14. Nuxt.js部署应用的方式
  15. BZOJ 3745: [Coci2015]Norma(分治)
  16. linux每日命令(8):mv命令
  17. 1-1-linux环境搭建
  18. 人工智能-机器学习之numpy方法
  19. go 编译问题
  20. AI入门课程资源

热门文章

  1. C# 验证码生成
  2. android去除Spinner的分割线
  3. 如何判断SharedPreferences 记录存在
  4. postgresql----SELECT
  5. 08.Curator缓存
  6. opencv学习笔记——FileStorage类的数据存取操作
  7. 使用 Sonar 进行代码质量管理
  8. 洛谷P3939 数颜色 二分查找
  9. IOS #ifdef 的那些事儿
  10. (转) SpringBoot非官方教程 | 第二十四篇: springboot整合docker