[国家集训队]整数的lqp拆分

我们的目标是求$\sum\prod_{i=1}^m F_{a_i}$

设$f(i) = \sum\prod_{j=1}^i F_{a_j}$
那么$f(i - 1) = \sum\prod_{j=1}^{i - 1} F_{a_j}$
又有递推式$f(i) = \sum_{j = 1}^{i - 1}f(j) * F_{a_i - j}$

那么推吧
$$f(i) - f(i - 1)$$
$$=\sum_{j = 1}^{i - 1}f(j) * F_{a_i - j} - \sum_{j = 1}^{i - 2}f(j) * F_{a_i -1- j}$$
$$=f(i - 1) * F_{a_1} + \sum\prod_{i=1}^{i - 2} f(j) * (F_{a_i - j} - F_{a_i - 1 - j})$$
$$= f(i - 1) + \sum\prod_{i=1}^{i - 2} f(j) * F_{a_i - 2 - j}$$
$$= f(i - 1) + f(i - 2)$$

所以$$f(i) = 2 * f(i - 1) + f(i - 2)$$

法二：（我觉得巨妙）
设 g[i] 为i的lqp拆分的权值和，则 $g[i] = ∑f[j] * g[i-j] + f[i]$, 其中 $g[0] = 0, g[1] = 1$
设 $A = ∑f[i] * x^i , B = ∑g[i] * x^i$ ,那么 => $B = A*B + A$
解一下 B ，发现 $B = A/(1-A)$
又∵ A的闭形式是 $x/(1 - x - x^2)$ [斐波那契数的生成函数闭形式]
∴ $B = x/(1 - 2x - x^2)$ ，于是直接由B的特征根得出g[]的递推式 => $g[i] = 2*g[i-1] + g[i-2]$.
转自金爷爷哈哈的题解

巴特西

[国家集训队]整数的lqp拆分

最新文章

热门文章