BZOJ1833【ZJOI2010】count数字计数 <数位DP>

Problem

【ZJOI2010】count 数字计数

Time Limit: $3 Sec$
Memory Limit: $64 MB$

Description

给定两个正整数$a$和$b$，求在$[a,b]$中的所有整数中，每个数码$(digit)$各出现了多少次。

Input

输入文件中仅包含一行两个整数$a$、$b$，含义如上所述。

Output

输出文件中包含一行$10$个整数，分别表示$0\sim 9$在$[a,b]$中出现了多少次。

Sample Input

1 99

Sample Output

9 20 20 20 20 20 20 20 20 20

HINT

$30\%$的数据中，$a\le b\le 10^6$
$100\%$的数据中，$a\le b\le 10^{12}$

标签：数位DP

Solution

$BZOJ$上最简单的数位$DP$，比$Windy$数还水。
预处理数组$f$，其中$f[i][j]$表示第i位为$j$的数共多少个。
对于每次查询，找$[1, a]$和$[1,b]$中$0\sim 9$出现的次数，按位在$f$数组上查，相减即可。
可以用结构体重载运算符，这样一个算式不用写十遍。

Code

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long lnt;
lnt a, b, pow[20];
struct node {lnt c[10];} f[20][10];
node operator + (node a, node b) {node ret;    for (int i = 0; i < 10; i++)	ret.c[i] = a.c[i]+b.c[i];	return ret;}
void init() {pow[1] = 1;    for (int i = 2; i <= 15; i++)	pow[i] = pow[i-1]*10;}
node calc(lnt x) {
    node ret;	for (int i = 0; i < 10; i++)	ret.c[i] = 0;
    if (!x) {ret.c[0] = 1;	return ret;}
    int len = 15;	while (x < pow[len])	len--;
    for (int i = 1; i < len; i++)	for (int j = 1; j < 10; j++)	ret = ret+f[i][j];	ret.c[0]++;
    int cur = x/pow[len];	for (int i = 1; i < cur; i++)	ret = ret+f[len][i];
    x %= pow[len], ret.c[cur] += x+1;
    for (int i = len-1; i; i--) {
        cur = x/pow[i];
        for (int j = 0; j < cur; j++)	ret = ret+f[i][j];
        x %= pow[i], ret.c[cur] += x+1;
    }
    return ret;
}
int main() {
    init(), scanf("%lld%lld", &a, &b);
    for (int i = 0; i < 10; i++)	f[1][i].c[i] = 1;
    for (int i = 2; i <= 12; i++)	for (int j = 0; j < 10; j++)	for (int k = 0; k < 10; k++)
        f[i][k] = f[i][k]+f[i-1][j], f[i][k].c[k] += pow[i-1];
    node ansa = calc(a-1), ansb = calc(b);
    for (int i = 0; i < 10; i++) {printf("%lld", ansb.c[i]-ansa.c[i]);	if (i != 9)	printf(" ");}
    return 0;
}