以下计算时间复杂度时，认为 \(p,q,m,n\) 同阶。
做法 1：DP
观察到基底和奶油是相互独立的，每一种材料选一块插猫耳插饰。
在这里以计算基底为例，奶油同理，用乘法原理计算就行，注意要减去 \(1\)，因为都选 \(0\) 份是不合法的。
令 \(f_i\) 表示选择 \(i\) 份基底，不插猫耳插饰的方案数，\(g_i\) 表示选择 \(i\) 份基底，插猫耳插饰的方案数，则有转移：
\(f_i = f_{i-1} \times n\)
\(g_i = g_{i-1} \times n + f_{i-1} \times n\)。
基底方案数的答案就是 \(\sum \limits _{i=0}^p (f_i+g_i)\)。
时间复杂度 \(O(Tn)\)。
考虑矩阵优化。
令 \(s_i = \sum \limits _{j=0}^i (f_j+g_j)\)，构造一个 $3 \times 3 $ 的矩阵 \(A\)，使得 \((f_i,g_i,s_i) \times A = (f_{i+1},g_{i+1},s_{i+1})\)。
\[A = \begin{pmatrix} n&n&2n\\ 0&n&n\\ 0&0&1 \end{pmatrix} \]时间复杂度 \(O(T \log n)\)。
做法 2：推式子
可以直接考虑推出式子，这里仍然以基底的方案数（记为 \(S\)）为例。
\[S = \sum \limits_{i=0}^p n^i \times (i + 1) \]这个式子的意义是：对于选择 \(i\) 份基底的方案，每份基底都可以选择第 \(1 \sim n\) 种，一共 \(n^i\) 种可能；可以选择在第 \(1 \sim i\) 份上插猫耳插饰或不插，一共 \(i+1\) 种可能。
直接计算是 \(O(Tn)\) 的。
那么怎么快速计算这个式子呢？
做法 2.1：分治
在李煜东的《算法竞赛进阶指南》中有过“分治求等比数列前 \(n\) 项和” 的讲解，具体做法是先求出前 \(\frac{n}{2}\) 项的和，再根据这个和推出前 \(n\) 项和，比如计算：
\(a^0 + a^1 + a^2 + a^3 + a^4 + a^5\)
我们先计算出 \(a^0+a^1+a^2\)。
然后有 \(a^0 + a^1 + a^2 + a^3 + a^4 + a^5 = (a^0 + a^1 + a^2) \times (1 + a^3)\)
这样的时间复杂度是什么呢？考虑一次递归时只需要计算一次 \(a^k\)（快速幂，单次时间复杂度 \(O(\log n)\)），一共需要计算 \(\log n\) 次的 \(a^k\)，是 \(O(\log^2 n)\) 的。
而这题的式子其实也可以分治做。比如计算：
\(1 \times n^0 + 2 \times n^1 + 3 \times n^2 + 4 \times n^3 + 5 \times n^4 + 6 \times n^5\)
我们先计算出 \(lans = 1 \times n^0 + 2 \times n^1 + 3 \times n^2\)。
然后有 \(1 \times n^0 + 2 \times n^1 + 3 \times n^2 + 4 \times n^3 + 5 \times n^4 + 6 \times n^5 = lans + lans \times n^3 + 3 \times (n^3 + n^4 + n^5))\)。
而 \((n^3 + n^4 + n^5)= n^3 (n^0+n^1+n^2)\) 又可以使用等比数列前 \(n\) 项和求出。
总时间复杂度 \(O(T \times (\log n + (\log n + \log^2 n)) = O(T \log^2 n)\)。
标签：log,报告,复杂度,times,解题,计算,汉堡,基底,式子 From： https://www.cnblogs.com/Zeardoe/p/16596386.html