laekov

数位DP好麻烦啊不想写啊怎么办啊。

利用trie树思想直接做好了。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long qw;

#ifdef WIN32

#define lld "%I64d"

#else

#define lld "%lld"

#endif

const int maxn = 15;

qw p10[maxn];

qw x, y, ans[10], c[10];

int n;

char a[maxn];

void calc(qw val, int sgn) {

if (!val)

return;

sprintf(a + 1, lld, val);

int n = strlen(a + 1);

memset(c, 0, sizeof(c));

qw cz, cm, cr;

cz = 1;

cm = a[1] - 48 - 1;

cr = 1;

for (int i = 1; i < a[1] - 48; ++ i)

c[i] += p10[n - 1];

c[a[1] - 48] += val + 1 - p10[n - 1] * (cm + cz);

for (int i = 2; i <= n; ++ i) {

for (int j = 0; j < 10; ++ j)

c[j] += cm * p10[n - i];

for (int j = 1; j < 10; ++ j)

c[j] += cz * p10[n - i];

for (int j = 0; j < a[i] - 48; ++ j)

c[j] += cr * p10[n - i];

cm = cm * 10 + cz * 9 + cr * (a[i] - 48);

cr = 1;

c[a[i] - 48] += val + 1 - p10[n - i] * (cm + cz);

}

for (int i = 0; i < 10; ++ i)

ans[i] += c[i] * sgn;

}

int main() {

#ifndef ONLINE_JUDGE

freopen("in.txt", "r", stdin);

#endif

memset(ans, 0, sizeof(ans));

p10[0] = 1;

for (int i = 1; i < maxn; ++ i)

p10[i] = p10[i - 1] * 10;

scanf(lld lld, &x, &y);

calc(y, 1);

calc(x - 1, -1);

for (int i = 0; i < 10; ++ i)

printf(lld "%c", ans[i], (i == 9) ? 10 : 32);

}