042.md

042 - Multiple of 9 (★4)

解答

#include <iostream>
#include <vector>
#include <algorithm> // std::min()

int main()
{
	// X を 10 進法で表したときの各桁の数字の和が K
	int K;
	std::cin >> K;

	constexpr int MOD = 1'000'000'007;

	if (K % 9 != 0) // 9 の倍数であれば, K が 9 の倍数でなければならない
	{
		std::cout << 0 << '\n';
	}
	else
	{
		// dp[各桁の数字の和] = 通り数
		std::vector<int> dp(K + 1);
		dp[0] = 1;

		for (int i = 1; i <= K; ++i)
		{
			for (int j = 1; j <= std::min(i, 9); ++j)
			{
				dp[i] += dp[i - j];

				if (MOD <= dp[i])
				{
					dp[i] %= MOD;
				}
			}
		}

		// 解答を出力
		std::cout << dp[K] << '\n';
	}
}