082.md

082 - Counting Numbers (★3)

解答

#include <iostream>
#include <vector>
#include <boost/multiprecision/cpp_int.hpp>

// 1 ～ n の合計を計算
boost::multiprecision::cpp_int SumFrom1To(boost::multiprecision::cpp_int n)
{
	return (n * (n + 1) / 2);
}

int main()
{
	constexpr int MOD = 1'000'000'007;

	// PowOf10s = { 10^0, 10^1, 10^2, ... 10^19 };
	// long long では 10^19 を表現できないため unsigned long long
	std::vector<unsigned long long> PowOf10s(20);
	{
		PowOf10s[0] = 1;

		for (int i = 1; i <= 19; ++i)
		{
			PowOf10s[i] = (PowOf10s[i - 1] * 10);
		}
	}

	// 黒板に L ～ R の整数を書く
	unsigned long long L, R;
	std::cin >> L >> R;

	// 文字の合計個数 (mod M)
	long long a = 0;

	// それぞれの個数桁の整数について
	for (int i = 1; i <= 19; ++i) // i 桁の整数
	{
		// 黒板に書かれる最小値
		// i = 2, L = 4 のとき std::max(4, 10) -> 10
		// i = 2, L = 40 のとき std::max(40, 10) -> 40
		// i = 2, L = 400 のとき std::max(400, 10) -> 400
		const unsigned long long left = std::max(L, PowOf10s[i - 1]);

		// 黒板に書かれる最大値
		// i = 2, R = 6 のとき std::min(6, 100 - 1) -> 6
		// i = 2, R = 60 のとき std::min(60, 100 - 1) -> 60
		// i = 2, R = 600 のとき std::min(600, 100 - 1) -> 99
		const unsigned long long right = std::min(R, PowOf10s[i] - 1);

		// right < left なら, 現在の個数桁の整数について, 黒板に書かれる数はない
		if (right < left)
		{
			continue;
		}

		// i 桁の整数は何回書かれるか
		const auto e_i = (SumFrom1To(right) - SumFrom1To(left - 1));

		// i 桁の整数は何文字書かれるか (書かれる整数の個数 × 整数の文字数）
		auto eLength = (e_i * i);

		a += static_cast<long long>(eLength % MOD);

		a %= MOD;
	}

	// 解答を出力
	std::cout << a << '\n';
}