牛客练习赛80 C题题解

C 题
我们发现，在一个不降数的后面加上一个合适的数字，就可以得到一个新的不降数。
考虑递推。设 $f_{i,j}$ 为长度为 $i$ ，最后一个数字为 $j$ 的不降数。就有 $f_{i,j}=\sum_{k=1}^jf_{i-1,k}$ 。
这是一个递推公式，初始条件 $f_{1,i}=1\left(1\leq i\leq 9\right)$ 。
那我们可以使用矩阵快速幂，时间复杂度 $O\left(\log n\right)$ 。~~暴锤标答~~
代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47415546