我们有一个数字 N 和成本 C,(范围 N<10^18 ,C<100) 现在我们必须花费最多 C 卢比来将这个数字转换成另一个数字。
一个数字转换成另一个数字的规则如下：
1）一个数字可以转换为其他数字相同的数字，并且没有前导零。2）一个数字转换成另一个数字的成本是对应数字的绝对差之和。例如，将 235 转换为 331 的成本为 5（因为对应数字的绝对差为 |3−2|+|3−3|+|1−5| ，即 |1|+0+|−4| =5. 现在我们需要找出在最大预算（C 卢比）范围内有多少个是 3 的倍数的数字。
我的方法：我首先尝试使用 3 的可除性规则并找到 N 的数字总和，如果成本只是数字差的总和，那么我们可以简单地做的就是使总和成为 3 的倍数，如 2+3+5 = 10成本是 2 我们可以使它成为 12 这可以通过将任何数字 2 、 3 或 5 增加 2 435,255, 237 来实现，这是正确的吗？当c是绝对和时，在这种情况下如何解决它
令cost(a,b)表示将a转换为b的成本并定义
N(a,c) = # { b | cost(a,b) = c }
即，N(a,c)是从a的成本正好是c的数字的数量。
让我们进一步假设 _a_ 可以被 3 整除。那么我们感兴趣的数字是：
answer = N(a,0) + N(a,3) + N(a,6) + N(a,9) + ... + N(a,99)
如果a是 1 mod 3 我们想要总和N(a,2) + N(a,5) + ... + N(a,98)。
要计算N(a,c) ，对于 a中的每个数字d，构造一个多项式P(d) ，其中x^k的系数是 [0..9] 中 距离d正好k的数字的数量。这些系数将始终为 0、1 或 2。
例如，对于a = 3496，多项式为：
d 1 x x^2 x^3 x^4 x^5 x^6 x^7 x^8 x^9
-- --- --- --- --- --- --- --- --- --- ---
3 1 2 2 1 1 1 1 0 0 0
4 1 2 2 2 2 1 0 0 0 0
9 1 1 1 1 1 1 1 1 1 1
6 1 2 2 2 1 1 1 0 0 0
注意：数字 3 的x^3系数是 1 而不是 2，因为不允许使用前导零。
现在将多项式相乘，N(a,c)是 结果乘积中x^c的系数。