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

Problem

【ZJOI2010】count 数字计数

Time Limit:
Memory Limit:

Description

给定两个正整数和，求在中的所有整数中，每个数码各出现了多少次。

Input

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

Output

输出文件中包含一行个整数，分别表示在中出现了多少次。

Sample Input

1 99

Sample Output

1	9 20 20 20 20 20 20 20 20 20

HINT

的数据中，
的数据中，

标签：数位DP

Solution

上最简单的数位，比数还水。
预处理数组，其中表示第i位为的数共多少个。
对于每次查询，找和中出现的次数，按位在数组上查，相减即可。
可以用结构体重载运算符，这样一个算式不用写十遍。

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;
}