显而易见,可以列出以下 DP 转移方程:
fi=fi−1×10lg(i)+1+i
显然,直接转移是 O(n) 的,由于涉及前面的状态较少,考虑矩阵快速幂优化,设转移矩阵为 T,则有:
fii+11=T×fi−1i1
根据转移方程,显然有:
T=10lg(i)+100110011
由于 10lg(i)+1 不是定值,但它满足线性性质,所以考虑枚举 10lg(i)+1 的值,在 [1,9] 时,快速幂指数为 9;在 [10,99] 时,快速幂指数为 90,以此类推,直到 [10x,n],此时快速幂指数为 n−10x+1。