Time Limit: 40 Sec Memory Limit: 259 MB
Description
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输出即可。
Input输入的第一行包含一个整数N。
Output输出一个整数,为对于N的整数lqp拆分的权值和mod 109(10的9次方)+7。
Sample Input3
Sample Output5
【样例说明】
F0=0,F1=1,F2=1,F3=2。
对于N=3,有这样几种lqp拆分:
3=1+1+1, 权值是1*1*1=1。
3=1+2,权值是1*2=2。
3=2+1,权值是2*1=2。
所以答案是1*1*1+1*2+2*1=5。
20%数据满足:1≤N≤25 50%数据满足:1≤N≤1000 100%数据满足:1≤N≤1000000
Source/**************************************************************
Problem: 2173
User: ictsing
Language: C++
Result: Accepted
Time:340 ms
Memory:9100 kb
****************************************************************/
//给出输出n。设一种拆分为n=x1+x2+x3,那么这种拆分的价值为F(x1)*F(x2)*F(x3),F为斐波那契额数列。求所有拆分的价值之和。
/*
稍微递推一下可以得出如下:
G(i)=∑[f(i)*G(n-i)]{1=<i<=n}
=f(1)*G(n-1)+∑[f(i)*G(n-i)]{2<=i<=n}
=G(n-1)+∑[f(i-1)*G(n-i)]{2<=i<=n}+∑[f(i-2)*G(n-i)]{2<=i<=n}
=2*G(n-1)+G(n-2)
*/
#include<iostream>
#include<cstdio>
using namespace std;
const int mt = 1000000+5;
typedef long long ll;
const ll mod = 1e9+7;
ll g[mt];
inline int read()
{
int num=0,flag=1;
char ch;
do{
ch=getchar();
if(ch=='-') flag=-1;
}while(ch<'0'||ch>'9');
do{
num=num*10+ch-'0';
ch=getchar();
}while(ch>='0'&&ch<='9');
return num*flag;
}
int main()
{
int n=read();
g[0]=0ll,g[1]=1ll;
for(int i=2;i<=n;i++)
g[i]=(((g[i-1]<<1)%mod+g[i-2])%mod+mod)%mod;
printf("%lld\n",g[n]);
return 0;
}
评论