ZZY的宠物
Time Limit:1000MS
Description
ZZY领养了一对刚刚出生的不知名小宠物..巨萌巨可爱!!...小宠物的生命为5个单位时间并且不会在中间出意外翘辫子(如:从0出生能活到5但活不到6)..小宠物经过2个单位时间成熟..刚刚成熟的一对小宠物能立即生育6只新的小宠物(如:从0出生的一对在2时成熟并进行第一次生育)...小宠物是很忠诚的..不会在中途换伴侣..每对小宠物生育一次这一对的生育能力就会降低2个..也就是说一对小宠物在第二次生育时就只能生4个了..小宠物成熟后每个单位时间都会尽力的生育(例:从0出生的一对..2时间生6个..3时间生4个..4时间生2个...5时间生不出..6时间这一对已经挂了..)..生育出来的新小宠物会继续这个过程..
ZZY想知道从单位时间0开始..经过M个单位时间(时间为M时)将有多少只活着的小宠物(0时刻有2只小宠物)
因为ZZY隐隐地觉得什么地方怪怪的...所以请将这个数目mod10000
Input
多组数据读到EOF
每组数据一行:
M ( 0<=M<=2000000000 )
最多500组数据
Output
每组输出一行为Case 组号: 答案,即M时刻活着的小宠物个数%10000
SampleInput
0
1
2
3
4
8
SampleOutput
Case 1: 2
Case 2: 2
Case 3: 8
Case 4: 12
Case 5: 32
Case 6: 528
Source
ZZY原创的说..
解题报告:
这道题的灵感来自Fibonacci的那个兔子故事...思想是矩阵乘法解递推数列(应该找不到什么通项公式吧?反正我没试过...)
根据题意建立这样一种数列,数列从0号开始..代表第0个单位时间出生的小宠物...1代表在第1个单位时间出生的小宠物..以此类推..将这个数列某项称作Z[x]
显然..当x>=5时..在第x天活着的小宠物数量sum[x] = z[x-5] + z[x-4] + z[x-3] +z[x-2] +z[x-1] + z[x]
再看根据题意 z[x] = z[x-2]/2*6 + z[x-3]/2*4 + z[x-4]/2*2 = z[x-2]*3 + z[x-3]*2 + z[x-4]
显然这个式子是一个递推的公式...那么就可以用矩阵乘法来求解这个递推公式的第x项是多少...观察数列建立关于这个递推数列的"特征“矩阵..
M = 0 1 0 0 0 0
0 0 1 0 0 0
0 0 0 1 00
0 0 0 0 1 0
0 0 0 0 0 1
0 0 1 2 3 0
而初始值为0单位时间的出生情况...可以自己递推出来...为 A = { 0 , 0 , 0 ,0 ,0 ,2 }
要求第x天出生了多少就用z[x] = A*(M^x)...矩阵乘法用递归2分来求解...
要求sum(x)...就分别求出z[x-5] ,z[x-4] ,z[x-3] ,z[x-2] ,z[x-1] ,z[x]再将这几个值加起来就行了....
标程:
分享到:
相关推荐
2013暑假多校训练7标程+解题报告,复旦大学ACM集训队友情命题。
2013多校训练6标程,解题报告,由麻省理工命题。
ACM 2013暑假 多校训练8标程+解题报告,由电子科技大学ACM集训队友情命题。
ACM 2013暑假 多校训练9标程+解题报告 由watashi命题。
13MU_10标程+解题报告,学习使用。
hdoj 2013 多校训练3标程+解题报告
hdoj 2013 多校训练3标程+解题报告
hdoj 2013 多校训练2标程+解题报告
2013 hdoj 暑假多校训练5标程+解题报告
ACM 2013 暑假 多校训练7标程+解题报告,由电子科技大学ACM集训队友情命题。
acm 解题报告,强烈推荐acm 解题报告
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
tjoi2014一试试题、测试数据、选手程序、解题报告、标程
tjoi2014二试试题、测试数据、选手程序、解题报告、标程
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
从一道题看奥赛所涉及的解题方法和技巧.pdf
北大POJ初级题-数据结构:解题报告+AC代码
2013年武汉科技大学“蓝桥杯”校内选拔赛的 标程及测试数据+解题报告 题目在www.wustacm.com上的"Contest"栏内 欢迎大家来wustoj上刷题
13年3月30日多校第二场解题报告+标程
NOIP2011普及组试题,测试数据,题解报告,报告很详细的引导初学导解题