Siyuan

「BZOJ 2173」整数的 lqp 拆分
「BZOJ 2173」整数的 lqp 拆分
扫描右侧二维码阅读全文
28
2019/06

「BZOJ 2173」整数的 lqp 拆分

题目链接:BZOJ 2173

lqp 在为出题而烦恼,他完全没有头绪,好烦啊……

他首先想到了整数拆分。整数拆分是个很有趣的问题。给你一个正整数 $n$,对于 $n$ 的一个整数拆分就是满足任意 $m > 0$,$a_1, a_2, a_3, \dots, a_m > 0$,且 $a_1 + a_2 + a_3 + \dots + a_m = n$ 的一个有序集合。通过长时间的研究我们发现了计算对于 $n$ 的整数拆分的总数有一个很简单的递推式,但是因为这个递推式实在太简单了,如果出这样的题目,大家会对比赛毫无兴趣的。

然后 lqp 又想到了斐波那契数。定义:

$$ f_n = \begin{cases} 0 & n = 0 \\ 1 & n = 1 \\ f_{i - 1} + f_{i - 2} & n > 1 \end{cases} $$

$f_n$ 就是斐波那契数的第 $n$ 项。但是求出第n项斐波那契数似乎也不怎么困难……lqp 为了增加选手们比赛的欲望,于是绞尽脑汁,想出了一个有趣的整数拆分,我们暂且叫它:整数的 lqp 拆分。

和一般的整数拆分一样,整数的 lqp 拆分是满足任意 $m > 0$,$a_1, a_2, a_3, \dots, a_m > 0$,且 $a_1 + a_2 + a_3 + \dots + a_m = n$​ 的一个有序集合。但是整数的 lqp 拆分要求的不是拆分总数,相对更加困难一些。

对于每个拆分,lqp 定义这个拆分的权值 $\prod_{i = 1} ^ m f_{a_i}$,他想知道对于所有的拆分,他们的权值之和是多少?

由于这个数会十分大,lqp 稍稍简化了一下题目,只要输出对于 $n$ 的整数 lqp 拆分的权值和模 $10 ^ 9 + 7$ 即可。

数据范围:$1 \le n \le 10 ^ 6$。


Solution

设 $g_i$ 表示 $i$ 的所有 lqp 拆分的权值总和,那么有转移:

$$ g_i = f_i + \sum_{j = 0} ^ i f_j \cdot g_{i - j} $$

我们考虑 $f_i$ 和 $g_i$ 的生成函数 $F(x)$ 和 $G(x)$,发现等式右边是一个卷机形式,得到:

$$ G = F + F \ast G \\ G = \frac{F}{1 - F} $$

此时已经可以直接 $\text{NTT}$ 求解了,时间复杂度为 $\mathcal O(n \log n)$,但是可以继续优化复杂度!

注意到 $F(x) = \frac{x}{1 - x - x ^ 2}$,可以计算出:

$$ G(x) = \frac{x}{1 - 2x - x ^ 2} $$

于是我们得到 $g_i$ 的递推式:

$$ g_i = 2 g_{i - 1} + g_{i - 2} $$

至此我们已经可以 $\mathcal O(n)$ 求解了。当然我们可以通过方程求出 $g_i$ 的通项公式,进一步优化为 $\mathcal O(\log n)$。由于笔者太懒了,只写了递推写法。

时间复杂度:$\mathcal O(n)$。


Code

#include <cstdio>

const int N = 1e6 + 5;
const int MOD = 1e9 + 7;

int n, g[N];

int main() {
    scanf("%d", &n);
    g[0] = 0, g[1]= 1;
    for (int i = 2; i <= n; i++) {
        g[i] = (2LL * g[i - 1] % MOD + g[i - 2]) % MOD;
    }
    printf("%d\n", g[n]);
    return 0;
}
最后修改:2019 年 06 月 28 日 09 : 39 AM

发表评论