首页 > 代码库 > BZOJ2173: 整数的lqp拆分
BZOJ2173: 整数的lqp拆分
2173: 整数的lqp拆分
Time Limit: 40 Sec Memory Limit: 259 MBSubmit: 328 Solved: 215
[Submit][Status]
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 Input
Sample Output
【样例说明】
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。
HINT
20%数据满足：1≤N≤25 50%数据满足：1≤N≤1000 100%数据满足：1≤N≤1000000
Source
题解：
简单题。只是样例比较sb，误人子弟，f[2]==1?呵呵
这种数学题，考虑递推公式：
n的拆分怎么来？
1.n-1的拆分中某个数+1
2.n-1的拆分中加上一个1
这样的话 g[n]=g[n-1]+g[n-2]+g[n-1]=2*g[n-1]+g[n-2]
因为 f[x]=f[x-1]+f[x-2]所以相当于多出来个 g[n-2]，应该很好理解。
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 500+10014 #define maxm 500+10015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define mod 100000000723 using namespace std;24 inline int read()25 {26 int x=0,f=1;char ch=getchar();27 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}28 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}29 return x*f;30 }31 int n,t,x,y;32 int main()33 {34 freopen("input.txt","r",stdin);35 freopen("output.txt","w",stdout);36 n=read();37 if(n==1)y=1;38 else39 {40 x=1;y=2;41 for1(i,n-2)t=x,x=y,y=((2*y)%mod+t)%mod;42 }43 printf("%d\n",y);44 return 0;45 }
话说n这么小什么情况，到long long还可以写个矩乘，我没那么无聊就不写了23333
因为 t=(2*y+x)%mod 爆了int WA了几次
必须这样 t=((2*y)%mod+x)%mod
T_T
这里推导写的不详细，想看具体的戳这里：http://www.cnblogs.com/Trinkle/p/3851811.html
BZOJ2173: 整数的lqp拆分