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:这题N的取小有可行性证明吗?

Posted by Tornado at 2011-12-29 17:22:05 on Problem 1322
In Reply To:这题N的取小有可行性证明吗? Posted by:flyingpiggy at 2007-04-19 17:48:31
这就是个典型的markov链:q(t+1)=P*q(t) -> q(n)=(P^n)*q(0)=Q'*D^n*Q*q(0)
P包含1、-1以及其他绝对值小于1的特征值,所以D的偶次方和奇次方会分别收敛到不同对角阵
所以n要区分奇偶

n的上界可以这么估计:
c=100的时候,可以得到绝对值小于1且最大的特征值0.98,那么由0.98^n<0.001可得n>342


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