P2602

发表于 2022-03-13 更新于 2022-03-14 分类于 PTS

[ZJOI2010]数字计数

显然作差，这个很好理解。

然后就是要求出 $f (x)$ 这个东西。

我们考虑数位 DP。

有一个显然的性质，满 $i$ 位的数字，所有数码出现的次数都是一样的（当然除了前导 0，我们后面再讨论），设这个次数为 $d p (i)$ ，那么就会有 $d p (i) = 10 d p (i - 1) + 10^{i - 1}$ 。

简单来说，第 $i$ 位从 0 到 9 枚举的时候，前面的 $i - 1$ 位重复了 10 次相同的变换，那么就要加上 $10 d p (i - 1)$ 。

而第 $i$ 位本身又从 0 到 9 变换，当第 $i$ 位是个确定的数字的时候，后面 $i - 1$ 位有多少种可能这一数码就会增加多少出现次数，所以要加上 $10^{i - 1}$ 。

然后考虑如何求出 $f (x)$ 。我们利用 $d p (i)$ 。

从最高位到最低位捋一波。

比如说，最高位是 $a_{1}$ ，最低位是 $a_{l e n}$ 。假如这个上届现在这一位是 $a_{i}$ ，当这一位为 $[0, a_{i} - 1]$ 的时候后面显然是随便取的，所以每一个数码都出现了 $a_{i} \times d p (i - 1)$ 次。

当这一位取到 $a_{i}$ 的时候就要小心一点，我们后面的数字只能取到上界。所以说 $a_{i}$ 这个数码的增加次数只有这一部分。（后面这一部分的数码如何计算我们根本不用管，因为我们后面是会算到的。。。）

然后就是处理前导零问题，假设 1 到 $i$ 都是 0，那么 0 这个数码就要减少 $10^{i - 1}$ 次的出现次数。

然后就寄算完了哈哈哈。

时间复杂度 $O (\log n)$ 。

代码：

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll N=15;

ll l,r;
ll ans1[N+5],ans2[N+5],dp[N+5],pw[N+5],a[N+5];

inline void Solve(ll x,ll *ans) {
  ll tmp=x,len=0;
  while(x) {a[++len]=x%10;x/=10;}
  for(ll i=len;i>=1;i--) {
    for(ll j=0;j<=9;j++) ans[j]+=dp[i-1]*a[i];
    for(ll j=0;j<a[i];j++) ans[j]+=pw[i-1];
    tmp-=pw[i-1]*a[i];ans[a[i]]+=tmp+1;ans[0]-=pw[i-1];
  }
}

inline void Init() {
  pw[0]=1ll;
  for(ll i=1;i<=13;i++) {dp[i]=dp[i-1]*10ll+pw[i-1];pw[i]=pw[i-1]*10ll;}
}

inline ll read() {
  ll ret=0,f=1;char ch=getchar();
  while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
  while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
  return ret*f;
}

inline void write(ll x) {
  static char buf[22];static ll len=-1;
  if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
  else {do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
  while(len>=0) putchar(buf[len--]);
}

inline void writes(ll x) {write(x);putchar(32);}

int main() {

  l=read();r=read();

  Init();
  Solve(r,ans1);Solve(l-1,ans2);

  for(ll i=0;i<=9;i++) {writes(ans1[i]-ans2[i]);}

  return 0;
}