P2602 [ZJOI2010]数字计数

文章目录

$Result$$Hyperlink$$Description$$Solution$$Code$

$Result$

---

$Hyperlink$

https://www.luogu.com.cn/problem/P2602

---

$Description$

求$[L,R]$中各个数字出现的次数

数据范围：$L\le R\le 10^{12}$

---

$Solution$

数位$dp$ 首先枚举我们要求的数字，设$f_{rest,sum}$表示剩余$rest$位，这个数字出现了$sum$次的个数 考虑前导0和最高位的限制即可

---

$Code$

#include<cctype> #include<cstdio> #include<cstring> #include<algorithm> #define LL long long using namespace std;LL L,R; int a[20],m; LL f[20][20]; inline LL read() { char c;LL d=1,f=0; while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48; while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48; return d*f; } inline LL dfs(int rest,int sum,int x,bool lead,bool limit)//没有前导0时lead为True { if(rest==0) return sum; if(lead&&limit==0&&f[rest][sum]!=-1) return f[rest][sum]; int cancse=limit?a[rest]:9; LL res=0; for(register int i=0;i<=cancse;i++) res+=dfs(rest-1,sum+((lead||i)&&(i==x)),x,lead||i,limit&&i==cancse); if(lead&&limit==0) f[rest][sum]=res; return res; } inline LL solve(LL x,int y) { m=0; while(x) a[++m]=x%10,x/=10; memset(f,-1,sizeof(f)); return dfs(m,0,y,0,1); } signed main() { L=read();R=read(); for(register int i=0;i<=9;i++) printf("%lld ",solve(R,i)-solve(L-1,i));