XOR is associative and commutative. So it's similar as "+" operator. First turn the array into a n*1 vector. Each round of the operation could be interpreted as a transition matrix A*vector. For example, suppose you have a 4 elements array (a,b,c,d )intially, then one round of operation could be interpreted as:
|1 1 0 1 | | a | |1 1 1 0 | | b | |0 1 1 1 | * | c | |1 0 1 1 | | d | When doing the matrix multiply, replace + as XOR replace value multiply as exponential. For example, a+b in the matrix operation should be a XOR b. while 3*a should be interpreted as a XOR a XOR a. Thus the question is equivalent to find out A^k * (initial vector). You can compute A^k easily in logk time. Thanks Yq On Tue, Jan 4, 2011 at 12:16 PM, juver++ <[email protected]> wrote: > There may be long periods. So another approach should be applied. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
