
ZOJ Problem Set  3845
In mathematics, a fixed point (sometimes shortened to fixpoint, also known as an invariant point) of a function is an element of the function's domain that is mapped to itself by the function. A set of fixed points is sometimes called a fixed set. That is to say, c is a fixed point of the function f(x) if and only if f(c) = c. This means f(f(...f(c)...)) = f^{n}(c) = c, an important terminating consideration when recursively computing f. For example, if f is defined on the real numbers by f(x) = x^{2}  3x + 4, then 2 is a fixed point of f, because f(2) = 2. Bob has three funtions define on nonegative integers, A(x) = c ∧ x, E(x) = c ⊕ x, and O(x) = c ∨ x, where ∧ means bitwise AND operation, ⊕ means bitwise XOR operation, ∨ means bitwise OR operation and c is an integer constant. Bob wants to know the number of fixed points for each function which satisfy the following conditions:
You are given three integers L, R and k, please tell Bob the answer. Note: x is a 32bit integer, that is x's binary representation only has 32 bits. InputThe first line of input contain an integer T (T ≤ 10000), which is the number of cases. Then next T line, each line contain four integers L, R, c and k (0 ≤ L ≤ R < 2^{32}, 0 ≤ c < 2^{32}, 0 ≤ k ≤ 32), separated by spaces. OutputFor each test case, print a line containing the test case number (beginning with 1) followed by three integers, indicating the number of fixed points for function A(x), E(x) and O(x), separated by one space. Sample Input3 1 10 1 32 1 100 43 32 1 200 43 20 Sample OutputCase 1: 1 0 5 Case 2: 15 0 4 Case 3: 0 0 7 Author: LIN, Xi Source: ZOJ Monthly, January 2015 