快速幂-矩阵快速幂-线性dp优化
快速幂说明：当求某一正整数 aaa 的 nnn 次幂 ana^nan 时，常用的做法是将 aaa 连续乘以 nnn 次，其时间复杂度为 O(n)O(n)O(n) 。 事实上，该问题有时间复杂度为 O(logn)O(logn)O(logn) 的解法。其核心思想是：an={an/2 ∗ an/2,n 为偶数an/2 ∗ an/2 ∗a,in 为奇数 a^n= \begin{cases} a^{n/2}\,*\,a^{n/2}, & \text {
