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)...)) = fn(c) = c, an important terminating consideration when recursively computing f. For example, if f is defined on the real numbers by f(x) = x2 - 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 32-bit integer, that is x's binary representation only has 32 bits.
The 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 < 232, 0 ≤ c < 232, 0 ≤ k ≤ 32), separated by spaces.
For 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.
3 1 10 1 32 1 100 43 32 1 200 43 20
Case 1: 1 0 5 Case 2: 15 0 4 Case 3: 0 0 7
Author: LIN, Xi
Source: ZOJ Monthly, January 2015