注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2173]整数的lqp拆分  

2014-07-20 20:58:42|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
【题目描述】
  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+7输出即可。
【输入格式】
  输入的第一行包含一个整数N。
【输出格式】
  输出一个整数,为对于N的整数lqp拆分的权值和mod 109+7。
【样例输入】
3
【样例输出】
5
【样例说明】
  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
【试题来源】
  2011中国国家集训队命题答辩
 
Solution
  hta:当年LQP在集训队作业中给出了O(NlogN)的算法,需要用到生成函数并且推导较为复杂。有兴趣的同学可以参考LQP2011年的作业。
  其实打表找规律才是正解= =
  G[n]=2G[n-1]+G[n-2],G[0]=0,G[1]=1
  连矩阵快速幂都不要多良心~
  
  暴力显然有G[n]=ΣG[i]*F[n-i]+F[n],O(n^2)
[BZOJ2173]整数的lqp拆分 - Trinkle - n+e
 
  《论出题人犯逗的危害》233
#include<cstdio>
int n;long long mod=1e9+7,g[1000010];
int main()
{
scanf("%d",&n);g[1]=1;
for(int i=2;i<=n;i++)g[i]=(2*g[i-1]+g[i-2])%mod;
printf("%lld\n",g[n]);
}


  评论这张
 
阅读(28)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018