[BZOJ 1833] [ZJOI2010] count 数字计数 【数位DP】

题目链接：BZOJ - 1833

题目分析

数位DP ..

用 f[i][j][k] 表示第 i 位是 j 的 i 位数共有多少个数码 k 。

然后差分询问...Get()中注意一下，如果固定了第 i 位，这一位是 t ，那么数码 t 的答案是要加一个值的（见代码）。

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

const int MaxBit = 15;

typedef long long LL;

struct ES
{
	LL A[11];
};

ES operator + (const ES &a, const ES &b) {
	ES ret;
	for (int i = 0; i <= 9; ++i) ret.A[i] = a.A[i] + b.A[i];
	return ret;
}

LL A, B;
LL P10[MaxBit];
 
ES f[MaxBit][11];

ES Get(LL x) {
	ES ret;
	for (int i = 0; i <= 9; ++i) ret.A[i] = 0;
	if (x == 0) return ret;
	int l = 1;
	while (P10[l] <= x) ++l;
	for (int i = 1; i <= l - 1; ++i) {
		for (int j = 1; j <= 9; ++j) {
			ret = ret + f[i][j];
		}
	}
	//0没有被统计 
	++ret.A[0];
	LL t; 
	t = x / P10[l - 1];
	x %= P10[l - 1];
	//如果只有1位，下面这里也会不统计0，但是已经在上面补上了0 
	for (int i = 1; i <= t - 1; ++i) ret = ret + f[l][i];
	ret.A[t] += x;
	for (int i = l - 1; i >= 1; --i) {
		t = x / P10[i - 1];
		x %= P10[i - 1];
		for (int j = 0; j <= t - 1; ++j) ret = ret + f[i][j];
		ret.A[t] += x;
	}
	return ret;
}

int main() 
{
	P10[0] = 1ll; 
	for (int i = 1; i <= 13; ++i) P10[i] = P10[i - 1] * 10ll;
	for (int i = 1; i <= 13; ++i) {
		for (int j = 0; j <= 9; ++j) {
			for (int k = 0; k <= 9; ++k) {
				f[i][j] = f[i][j] + f[i - 1][k];
			}
			f[i][j].A[j] += P10[i - 1];
		}
	}
	scanf("%lld%lld", &A, &B);
	ES TA, TB;
	TA = Get(A); TB = Get(B + 1);
	for (int i = 0; i <= 9; ++i) {
		printf("%lld", TB.A[i] - TA.A[i]);
		if (i == 9) printf("
");
		else printf(" ");
	}
	return 0;
}