Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:这题的公式怎么推出来的?

Posted by coolheart at 2006-09-09 18:41:52 on Problem 1067
In Reply To:Re:这题的公式怎么推出来的? Posted by:uni at 2004-05-14 11:05:09
> 这道题的算法很复杂
> 首先...存在一个比输序列
> 如果是比输序列的数对..那么则比输
> 否则比赢
> 比输序列的规则是
> 第N号序列的两数差为N
> 小的那个数的值是最先的前面数列不出现的整数
> 1 2  1号
> 3 5  2号
> 4 7  3号
> 
> 所以只要记录N号序列的差和最小数就可以了(序列A)
> 1 1
> 2 3
> 3 4
> 4 6
> 5 8
> 
> 然后计算最小数的逐相差有序列
> 2 1 2 2 1 2...........
> 
> 然后可以发现
> 
> 此序列有递推关系
> 2 1 2 2 1 2.....
> 1 0 1 1 0 1 (都减1)
> 2 1 2 0 2 1 2 1 2 0 2 1 2(中间插入2)
> 2 1 2 2 1 2 1 2 2 1 2.....(不写0)
> 变成原来的序列
> 
> 由此可以推出 
> 
> 序列A的第7号是11的话
> 那么由于(7+1),(11+2)是费波那切数列
> 所以(12+1),(19+2)也是费数列
> 所以第12号是19
> 
> 又由于
> 
> 上面的序列变换中
> 是对称的...
> 
> 所以可以知道
> 12+1=11+2=10+3=....
> 19+1=17+3=16+4=....
> 
> 所以
> 如果想知道11 17是不是A序列里的
> 只要知道 2 3是不是就可以了
> (12 19 这个序列可以用菲薄那切法推算出来)
> 
> 这样...不到23次运算就可以知道100000000000量级的数是不是A序列里的了
> 当然...也可以由此确定比输序列
> 

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator