#786. #6059. 「2017 山东一轮集训 Day1」Sum

#6059. 「2017 山东一轮集训 Day1」Sum

题目描述

求有多少 nn 位十进制数是 pp 的倍数且每位之和小于等于 mi(mi=0,1,2,…,m−1,m)m_i (m_i = 0, 1, 2, \ldots, m - 1, m),允许前导 00,答案对 998244353998244353 取模。

输入格式

一行三个整数 n,p,mn, p, m。

输出格式

输出一行 m+1m + 1 个正整数,分别表示 mi=0,1,2,…,m−1,mm_i = 0, 1, 2, \ldots, m - 1, m 时的答案。

2 3 3
1 1 1 5

数据范围与提示

对于测试点 1,1≤n≤1000,1≤p≤50.1≤m≤51 \leq n \leq 1000, 1 \leq p \leq 50.1 \leq m \leq 5;
对于测试点 2、3,1≤n≤109,1≤p≤50.1≤m≤51 \leq n \leq 10^9, 1 \leq p \leq 50.1 \leq m \leq 5;
对于测试点 4、5、6,1≤n≤109,1≤p≤50.1≤m≤501 \leq n \leq 10^9, 1 \leq p \leq 50.1 \leq m \leq 50;
对于测试点 7、8、9、10,1≤n≤109,1≤p≤16.1≤m≤10001 \leq n \leq 10^9, 1 \leq p \leq 16.1 \leq m \leq 1000。