【Dream Counting, 2006 Dec-数数的梦】数位dp

题意:给定两个数,问区间[A,B]中0~9分别出现了多少次。A,B<=10^18

【Dream Counting, 2006 Dec-数数的梦】数位dp

题解:应该是最裸的数位dp吧。。一开始没有记忆化tle了TAT

我们可以求出区间[0,B]的,再减去区间[0,A]的。

用dfs实现,记录flag(填了的位是否和边界重合),zero(当前是否还在前缀0中)

 #include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<ctime>
#include<queue>
using namespace std; typedef long long LL;
const int N=;
int c[N][N][][],d[N],sum[N];
LL bit[N],ret[N]; LL g(int now,int x,int flag,int zero)
{
if(c[now][x][flag][zero]!=-) return c[now][x][flag][zero];
if(x==) return ;
LL ans=;
if(flag)
{
for(int i=;i<d[x];i++)
{
ans+=g(now,x-,,zero & (i==));
if(i==now && !(i== && zero)) ans+=bit[x-];
}
ans+=g(now,x-,,zero && (d[x]==));
if(now==d[x] && !(now== && zero)) ans+=ret[x-];
}
else
{
for(int i=;i<=;i++)
{
ans+=g(now,x-,,zero & (i==));
if(i==now && !(i== && zero)) ans+=bit[x-];
}
}
// printf("now %d x %d flag %d zero %d = %d\n",now,x,flag,zero,ans);
c[now][x][flag][zero]=ans;
return ans;
} void solve(LL x,LL tmp)
{
memset(d,,sizeof(d));
memset(c,-,sizeof(c));
int l=;LL y=x;
while(y)
{
d[++l]=(int)(y%);
y/=;
}
for(int i=;i<=;i++) ret[i]=x%bit[i]+;
for(int i=;i<=;i++) sum[i]+=g(i,,,)*tmp;
} int main()
{
// freopen("a.in","r",stdin);
freopen("dream.in","r",stdin);
freopen("dream.out","w",stdout);
LL A,B;int x;
scanf("%lld%lld",&A,&B);
memset(sum,,sizeof(sum));
bit[]=;
for(int i=;i<=;i++) bit[i]=bit[i-]*;
solve(A-,-);
solve(B,);
for(int i=;i<=;i++) printf("%d ",sum[i]);
return ;
}
上一篇:【Python】【亲测好用】安装第三方包报错:AttributeError:'module' object has no attribute 'main'


下一篇:不用的代码,存一份--用tornado实现的websocket