题目链接: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$。
题目链接:Luogu 1357
小 L 有一座环形花园,沿花园的顺时针方向,他把各个花圃编号为 $1$ 到 $n$。他的环形花园每天都会换一个新花样,但他的花园都不外乎一个规则,任意相邻 $m$ 个花圃中有不超过 $k$ 个 $C$ 形的花圃,其余花圃均为 $P$ 形的花圃。
请帮小 L 求出符合规则的花园种数,答案对 $10 ^ 9 + 7$ 取模。
数据范围:$2\le n\le 10 ^ {15}$,$2\le m\le 5$,$1\le k<m$。