题解：CF1513C Add One

· · 题解

第一点注意：当 9 变为 10 的时候是直接多出来一位，而不是进一位，这里翻译没有注意到这一点，但原题面中体现了。

既然如此，我们可以把每一位都拆分开，即把每一位都当成一个独立的数，最后计算每一位的答案总和即可。

对于每一位考虑的话，就只有 0\sim9 这 10 种情况，只需要对这 10 个数变换所有次数预处理下来即可。

容易发现，如果初始数字 x 加上变换次数 k 小于 10 则不会进位。进位后，由 9 变成 10，需要加上 1 变换 k-10 次和 0 变换 k-10 次的答案和。

这样的话就像一个动态规划问题了，设 f_{i,j} 表示 i 变换 j 次后的位数，则状态转移方程为：

f_{i,j} = \begin{cases} 1 & i+j\le9\\ f_{0,i+j-10}+f_{1,i+j-10} & i+j\ge10 \end{cases} [AC Code](https://codeforces.com/problemset/submission/1513/297375800)