-递推- [BZOJ 2173]整数的lqp拆分

题目描述

lqp在为出题而烦恼，他完全没有头绪，好烦啊… 他首先想到了整数拆分。整数拆分是个很有趣的问题。给你一个正整数N，对于N的一个整数拆分就是满足任意m>0，a1 ,a2 ,a3…am>0，且a1+a2+a3+…+am=N的一个有序集合。通过长时间的研究我们发现了计算对于N的整数拆分的总数有一个很简单的递推式，但是因为这个递推式实在太简单了，如果出这样的题目，大家会对比赛毫无兴趣的。

然后lqp又想到了斐波那契数。定义F0=0，F1=1，Fn=Fn-1+Fn-2 (n>1)，Fn就是斐波那契数的第n项。但是求出第n项斐波那契数似乎也不怎么困难… lqp为了增加选手们比赛的欲望，于是绞尽脑汁，想出了一个有趣的整数拆分，我们暂且叫它：整数的lqp拆分。和一般的整数拆分一样，整数的lqp拆分是满足任意m>0，a1 ,a2 ,a3…am>0，且a1+a2+a3+…+am=N的一个有序集合。但是整数的lqp拆分要求的不是拆分总数，相对更加困难一些。对于每个拆分，lqp定义这个拆分的权值Fa1Fa2…Fam，他想知道对于所有的拆分，他们的权值之和是多少？简单来说，就是求由于这个数会十分大，lqp稍稍简化了一下题目，只要输出对于N的整数lqp拆分的权值和mod 109（10的9次方）+7输出即可。

输入

输入的第一行包含一个整数N。

输出

输出一个整数，为对于N的整数lqp拆分的权值和mod 109（10的9次方）+7。

样例输入

样例输出

说明

$ F_0 = 0, F_1 = 1, F_2 = 1, F_3 = 2 $。

对于$ N = 3 $，有这样几种lqp拆分：

$ 3 = 1 + 1 + 1 $, 权值是$ 1 \times 1 \times 1=1 $。

$ 3 = 1 + 2 $，权值是$ 1 \times 2 = 2 $。

$ 3 = 2 + 1 $，权值是$2 \times 1 = 2 $。

所以答案是 $ 1 \times 1 \times 1+1 \times 2+2 \times 1 = 5 $。
提示

20%数据满足：$ 1 ≤ N ≤ 25 $ $ 50% $数据满足：$ 1 ≤ N ≤ 1000 $ $ 100% $数据满足：$ 1 ≤ N ≤ 1000000$

Solution

首先这道题我读懂它就花了一个小时，明白了其实说明是错的，应该是这样：

对于 $ 3 $ 对于 $ N = 3 $，有这样几种lqp拆分：

$ 3 = 1 + 1 + 1 $, 权值是$1 \times 1 \times 1=1$。

$ 3 = 1 + 2 $ ，权值是 $ 1 \times 1 = 1 $。

$ 3 = 2 + 1 $ ，权值是 $ 1 \times 1 = 1 $。

$3=3$，权值是$2$。

所以答案是 $ 1 \times 1 \times 1+1 \times 1+1 \times 1 + 2 = 5 $。

然后，由于我没有学过生成函数，所以硬推公式花了我一个晚上+一个上午。。。。

然而我还是没推出来，于是人工在纸上打表，又花了好长时间。。。。

最后，终于从打表上找出了规律！

公式是：

$F_i = 2 \times F_{i-1} + F_{i-2}$

真的是堪比小凯的疑惑啊！

代码十分短小。

Code

#include<iostream>
#define MOD 1000000007
using namespace std;
long long f[1000005];
int main(){
    int n;
    cin>>n;
    f[0]=0;
    f[1]=1;
    for(int i=2;i<=n;i++){
        f[i]=(f[i-1]*2+f[i-2])%MOD;
    }
    cout<<f[n]<<endl;
}

~~据说这是国家集训队的题~~