Skip to content

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了,可以的话,请您参考添加页面,与大家一起分享你的题解!