Xor Range without LOOP

This post is shamelessly lifted from http://topforces.blogspot.com/2011/06/xor-range-without-loop.html

I am lazy, and I wont be able to explain it more clearly than him. Hence, I lifted the content directly from there, to have all the coding tricks in my blog for my reference. 

----------------------

HOW to get Xor between numbers from 1 to 300000000

you will get TLE if you try to use Loop for all numbers
Question was asked on the codeforces site. Click Here to see the discussion 

jacob answer
Let's introduce
 f(x) = x ^ (x-1) ^ (x-2) ^ ... ^ 1
Then anwer would be  
f(end) ^ f(start - 1)


Let's now learn to calculate f(x) fast enough. First, notice that f(4*k - 1) = 0 (provable by induction). So to calculate f(x) you only need to take at most 4 last numbers and xor them.
Finally,
f(4*k) = 4*k
f(4*k + 1) = 1
f(4*k + 2) = 4*k + 3
f(4*k + 3) = 0 


Expressions "at most 4 last numbers" and "only last 4 numbers" are different. In fact, you need to take exactly (x+1)%4 last numbers.

Conclusion:Use this function 

int f(int n){  
switch(n%4){  
case 0: return n;  
case 1: return 1;  
case 2: return n+1;  
default: return 0;  
}  
}  

Iterative, recursive and heap algorithms to generate permutations

A very good article on iterative and recursive algorithms for generating permutations of an array is here:
http://www.cut-the-knot.org/do_you_know/AllPerm.shtml

I shall shamelessly lift the algorithms listed in the page, for my reference here in the blog.
(Just for reference, another good algorithm is described at http://introcs.cs.princeton.edu/java/23recursion/Permutations.java.html)
Recursive algorithm for Permutations

It's executed with a call visit(0). Global variable level is initialized to -1 whereas every entry of the array Value is initialized to 0.

  void visit(int k)
  {
    level = level+1; Value[k] = level;    // = is assignment
    if (level == N)  // == is comparison
      AddItem();     // to the list box
    else
      for (int i = 0; i < N; i++)
        if (Value[i] == 0)
          visit(i);
    
    level = level-1; Value[k] = 0;
  }

  void AddItem()
  {
  // Form a string from Value[0], Value[1], ... Value[N-1].
  // At this point, this array contains one complete permutation.
  // The string is added to the list box for display.
  // The function, as such, is inessential to the algorithms.
  }

Lexigraphic order to find the next permutation

Permutation f precedes a permutation g in the lexicographic (alphabetic) order iff for the minimum value of k such that f(k)≠ g(k), we have f(k) < g(k). Starting with the identical permutation f(i) = i for all i, the second algorithm generates sequentially permutaions in the lexicographic order. The algorithm is described in [Dijkstra, p. 71].

  
  void getNext()
  {
    int i = N - 1;
    while (Value[i-1] >= Value[i]) 
      i = i-1;

    int j = N;
    while (Value[j-1] <= Value[i-1]) 
      j = j-1;
  
    swap(i-1, j-1);    // swap values at positions (i-1) and (j-1)

    i++; j = N;
    while (i < j)
    {
      swap(i-1, j-1);
      i++;
      j--;
    }
  }

B. Heap's algorithm 
Heap's short and elegant algorithm is implemented as a recursive method HeapPermute [Levitin, p. 179]. It is invoked with HeapPermute(N).

  
void HeapPermute(int n)
{
  if (n == 1) 
    AddItem();
  else {
    for (int i = 0; i < n; i++) 
      HeapPermute(n-1);
      if (n % 2 == 1)  // if n is odd
        swap(0, n-1);
      else            // if n is even
        swap(i, n-1);
}