245. 数位和

itdef / 2024-11-06 / 原文

// 22222.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

/*
http://oj.daimayuan.top/course/5/problem/245

读入 l,r，请求出 0...9 这些数字在 [l,r]的数位中分别出现了多少次。

输入格式
一行两个整数 l,r。

输出格式
一行 10 个数字，第 i个数字表示 i−1在 [l,r]的数位中出现的次数。

样例输入
1 100
样例输出
11 21 20 20 20 20 20 20 20 20
数据范围
对于 100%的数据，保证 1≤l≤r≤10^16。
*/

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

const int N = 20;
long long f[N][N][N];
long long g[N][N][N];
long long l, r;


long long powl(long long x, long long r)//x 底数 r指数
{
	long long out = 1;
	while (r)
	{
		if (r & 1)
		{
			out *= x;//out 答案
			//out %= 1;//p模数
		}
		x *= x;
		//x %= 1;
		r >>= 1;
	}
	return out;
}

void init() {
	for (int i = 0; i <= 9; i++) {
		f[0][i][i] = 1;
		g[0][i][i] = 1;
	}
	//g[0][0][0] = 0;

	for (int x = 1; x <= 16; x++) {
		for (int i = 0; i <= 9; i++) {
			for (int j = 0; j <= 9; j++) {
				for (int k = 0; k <= 9; k++) {
					f[x][i][j] += f[x - 1][k][j];
				}
				if (i == j) {
					f[x][i][j] += powl(10, 1LL * x);
				}
			}
		}
	}

	for (int x = 1; x <= 16; x++) {
		for (int i = 0; i <= 9; i++) {
			for (int j = 0; j <= 9; j++) {
				for (int k = 0; k <= 9; k++) {
					if (i == 0) {
						g[x][i][j] += g[x - 1][k][j];
					}
					else {
						g[x][i][j] += f[x - 1][k][j];
					}
				}
				if (i == j && i != 0) {
					g[x][i][j] += powl(10, 1LL * x);
				}
			}
		}
	}


	return;
}

vector<long long> solve(long long u) {
	vector<int> v; long long cu = u;
	while (cu != 0) {
		int t = cu % 10;
		cu /= 10;
		v.push_back(t);
	}
	vector<long long> ans(10, 0);
	if (u == 0) { ans[0] = 1; return ans; }
	for (int i = v.size() - 1; i >= 0; i--) {
		int t = v[i];
		for (int x = 0; x < t; x++) {
			for (int j = 0; j <= 9; j++) {
				if (j == 0) {
					if (i == v.size() - 1) {
						ans[j] += g[i][x][j];
					}
					else {
						ans[j] += f[i][x][j];
					}
				}
				else {
					ans[j] += g[i][x][j];
				}
			}
		}

		//t
		if (i >= 0) {
			u -= t * powl(10, 1LL*i);
			ans[t] += u + 1;
		}
	}

	return ans;
}


int main()
{
	init();
	cin >> l >> r;

	if (r < l) swap(l, r);
	vector<long long> a = solve(r);
	vector<long long > b = solve(l - 1);

	for (int i = 0; i <= 9; i++) {
		cout << a[i] - b[i] << " ";
	}
	cout << endl;
}