裸的数位DP我还不会= =b
令f[i][j][k]表示长度为i的数，开头为j，数字k的个数，这个可以预处理出来
只要计算[0, b] - [0, a - 1]即可，稍微讨论一下什么的就好了
1 /************************************************************** 2 Problem: 1833 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:28 ms 7 Memory:828 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <cstring> 12 13 using namespace std; 14 typedef long long ll; 15 16 struct data { 17 ll a[10]; 18 inline ll& operator [] (int x) { 19 return a[x]; 20 } 21 inline data operator + (data x) { 22 data t; 23 int i; 24 for (i = 0; i < 10; ++i) 25 t.a[i] = a[i] + x.a[i]; 26 return t; 27 } 28 inline data operator += (data x) { 29 *this = *this + x; 30 return *this; 31 } 32 } p1, p2, f[25][10]; 33 34 ll a, b, t[25]; 35 36 void pre_work() { 37 int i, x, y; 38 for (t[1] = 1, i = 2; i <= 15; ++i) 39 t[i] = t[i - 1] * 10; 40 for (i = 0; i <= 9; ++i) 41 f[1][i][i] = 1; 42 for (i = 2; i <= 12; ++i) 43 for (x = 0; x <= 9; ++x) 44 for (y = 0; y <= 9; ++y) { 45 f[i][y] += f[i - 1][x]; 46 f[i][y][y] += t[i - 1]; 47 } 48 } 49 50 void work(data &p, ll x) { 51 int len = 15, i, j, now; 52 if (x == 0) { 53 p[0] = 1; 54 return; 55 } 56 while (t[len] > x) --len; 57 for (i = 1; i < len; ++i) 58 for (j = 1; j <= 9; ++j) 59 p += f[i][j]; 60 ++p[0]; 61 now = x / t[len]; 62 for (i = 1; i < now; ++i) 63 p += f[len][i]; 64 x %= t[len]; 65 p[now] += x + 1; 66 for (i = len - 1; i; --i) { 67 now = x / t[i]; 68 for (j = 0; j < now; ++j) 69 p += f[i][j]; 70 x %= t[i]; 71 p[now] += x + 1; 72 } 73 } 74 75 int main() { 76 int i; 77 pre_work(); 78 scanf("%lld%lld", &a, &b); 79 work(p1, a - 1); 80 work(p2, b); 81 for (i = 0; i < 9; ++i) 82 printf("%lld ", p2[i] - p1[i]); 83 printf("%lld", p2[9] - p1[9]); 84 return 0; 85 }