1265: 数位DP
题目
题目描述
数位DP 是一种计数用的算法，一般就是要统计一个区间 $[l,r]$ 内满足一些条件数的个数。聪明的 cxy 发现这道题是一道数位DP 的练习题，他决定拿来考考你。
我们定义 $f(x)$ 代表了 $x$ 在十进制下各个位置的数字之和，求 $f(x) ^ a \times b + c = x$ 所有在 $[0, k]$ 范围内的整数解。
输入格式
第一行一个整数 $T$，代表数据组数 接下来 $T$ 行每行四个整数 $a, b, c, k$
输出格式
对于每组数据，输出两行 - 第一行代表解的个数 - 第二行按照所有解从小到大依次输出，若没有解，则第二行输出−1
样例输入
text
3
3 2 8 10000
1 2 -18 1000
2 2 -1 100
样例输出
text
2
10 2008
0
-1
2
1 31
数据范围
时间限制：1000 ms 空间限制：256 mb
无捆绑测试
全局限制
- $1 \leq T \leq 20$
- $1 \leq a \leq 5$
- $1 \leq b \leq 10^4$
- $-10^4 \leq c \leq 10^4$
- $0 \leq k \leq 10^9$
部分限制
- $(\text{40 points})~k\leq 100$
- $(\text{20 points})~a=1,c=0$
- $(\text{20 points})~b=1,c=0$
Oops! 本题目还没有解答！
助教老师们编题的速度，已经超过了解题的速度！
OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。
如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！