BZOJ 1833 count 数字计数

sb数位dp.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long a,b,dp[][],tab[],ans[],bit[],ret=;
void get_table()
{
tab[]=;
for (long long i=;i<=;i++) tab[i]=tab[i-]*;
for (long long i=;i<=;i++) dp[][i]=;
for (long long i=;i<=;i++)
for (long long j=;j<=;j++)
dp[i][j]=dp[i-][j]*+tab[i-];
}
void get_bit(long long x)
{
ret=;
while (x) {bit[++ret]=x%;x/=;}
}
void work(long long x,long long val)
{
if (!x) return;
get_bit(x);
for (long long i=;i<=ret-;i++)
for (long long j=;j<=;j++)
{
ans[j]+=tab[i-]*val;
for (long long k=;k<=;k++) ans[k]+=dp[i-][k]*val;
}
for (long long i=ret;i>=;i--)
{
for (long long j=(i==ret);j<bit[i];j++)
{
ans[j]+=tab[i-]*val;
for (long long k=;k<=;k++) ans[k]+=dp[i-][k]*val;
}
ans[bit[i]]+=(x-bit[i]*tab[i-]+)*val;x%=tab[i-];
}
}
int main()
{
scanf("%lld%lld",&a,&b);get_table();
work(b,);work(a-,-);
for (long long i=;i<=;i++) printf("%lld ",ans[i]);printf("%lld\n",ans[]);
return ;
}
上一篇:YII框架安装步骤(yii框架版本1.1.20,时间是2018/11)


下一篇:HTML实体字符转化为HTML标签