题目
思路简析
正解是数位 dp，但是我不太会，所以我打分块。
考虑从 \(10^6\) 到 \(2\times10^6\) 和从 \(3\times10^6\) 到 \(4\times10^6\)，其中真正的区别只有
观察到数据范围是 \(10^{12}\)，分为一些块，每块长 \(10^6\) 会比较均衡，所以共有 \(10^6\) 个块。
最差情况是 \(n = 10^6+1\)，\(吗= 10^{12}-1\)，则总共约运算 \(10^6times12+10^6+10^6\times12 = 2.5\times10^7\) 次，理论上是通过的。
无论如何加个优化吧。
记忆化：将 \(x%10^6\) 存到一个数组里（但是每次只能省大约 \(5\) 次，其实没啥用。）。
那么考虑 \(10^6\) 正好是最长长度的一半，而且在 十亿位 上的 \(x\) 和 个位 上的 \(x\) 加和出来的效果相同，所以前 \(6\) 位和后 \(6\) 位都可以使用这个数组。
那就能省不少、、。
点击查看代码
#include <bits/stdc++.h>
namespace {
#define fiin(x) freopen(x".in", "r", stdin)
#define fiout(x) freopen(x".out", "w", stdout)
#define files(x) fiin(x), fiout(x)
using namespace std;
#define ll long long
#define db double
const int lob = 1e6;
}
ll a, b;
ll res[12];
void def (ll) ;
int main () {
#ifndef ONLINE_JUDGE
files("test");
#endif
scanf("%lld%lld", &a, &b);
while (a%lob && a<b) def(a++);
while (b%lob && a<b) def(b--);
for (int i = a/lob; i < b/lob; ++ i) {
int x = i;
while (x) res[x%10] += lob, x /= 10;
for (int j = 0; j < 10; ++ j) res[j] += 600000;
} def(b);
for (int i = 0; i < 10; ++ i) printf("%lld ", res[i]);
return 0;
}
// ---
void def (ll x) {
while (x) ++ res[x%10], x /= 10;
return ;
}