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:O(N*L*logS)

Posted by ziliang at 2007-10-23 22:06:49 on Problem 3423
In Reply To:Re:O(N*L*logS) Posted by:xming at 2007-10-23 11:57:28 
第S个状态的i位置,只受第S-1个状态的i-1位置和i+1位置影响,即第S-2的i-2位置和i+2位置...以此类推.  第S个状态的i位置,受到第1个状态的某些位置影响,这些位置恰好是杨辉三角第S行的奇数位置.

我们对第S个状态的每个位b,检查给出的第1个状态的每个1的位置是否会影响b的值.这样将所有有影响的1值异或,就得到b的值. 

其中枚举状态O(L),枚举初始1 O(N),检测log(S)
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