设第\(n\)个人的礼物个数为\(F_n\), 那么显然\(F_n = 2 \times F_{n-1} + i^k\)
考虑矩阵快速幂
棘手的问题是：\(i^k\)不是可以直接用矩阵乘法可以递推的东西
有一个公式：\[a^k = \sum_{i = 1}^{k}(a-1)^i {k \choose i}\]
那么我们可以给\(\left( i-1, (i-1)^2, \cdots (i-1)^k, \right)\) 乘上一个类似杨辉三角的组合数矩阵， 就能得到\(\left(i, i^2, \cdots, i^k\right)\)
于是就做万了
原文：https://www.cnblogs.com/2016gdgzoi509/p/11148856.html