题解 | C 不加密

C 不加密
解法：矩阵快速幂
$n=1 , 答案为sum(1,1,...,1,1) = 9$
$n=2 , 答案为sum(9,8,...,2,1] = 45$
$n=3 , 答案为sum(45,36,...,3,1) = 165$

$...$
经过分析(肉眼观察/计算)，发现[注： $a(n,i)$ 代表第 $n$ 项，以 $i$ 结尾的答案]
$a(n,9) = a(n-1,1) + a(n-1,2) + ... + a(n-1,9)$
... $a(n,1) = a(n-1,1)$
很明显，就是矩阵快速幂的板子
构造矩阵 $A_n = [a(n,9) , a(n,8) ,..., a(n,1)]^T$
$T=$ [
[1 1 1 1 1 1 1 1 1],
[0 1 1 1 1 1 1 1 1],
[0 0 1 1 1 1 1 1 1],
[0 0 0 1 1 1 1 1 1],
[0 0 0 0 1 1 1 1 1],
[0 0 0 0 0 1 1 1 1],
[0 0 0 0 0 0 1 1 1],
[0 0 0 0 0 0 0 1 1],
[0 0 0 0 0 0 0 0 1]
]
$A_n = T^{n-1} * A_{n-1}$
然后对 $A_n$ 求和，答案就出来了